Divide and conquer

Vocabulaire

English	Sens
merge sort/mɜːdʒ sɔːt/	Sorting by recursively sorting parts and merging the sorted parts.
quicksort	Sorting by partitioning values around a pivot and recursively sorting the partitions.

English

Split, solve, combine

Merge sort splits in half, recurses, merges in $\Theta(n)$: $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$. Quicksort moves the work into the partition — the pivot quality decides everything.

{exercise:uni-cs1002-skeleton}

Pratique

Binary search recurrence is —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

Balanced pivots: $\Theta(n\log n)$. Sorted input with first-element pivots: $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$.
Course measurements on the 64-element array: merge 310 comparisons, quicksort 356, sorted-input worst 2080. Randomised pivots make the expected count $2n\ln n \approx 1.39\,n\log_2 n$.

{exercise:uni-cs1002-quicksort}

Pratique

Sorted input with first-element pivots costs quicksort —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

Maximum subarray by divide and conquer: left best, right best, or the best crossing the middle — the crossing scan is a full pass, so $\Theta(n\log n)$. On $[-2, 1, -3, 4, -1, 2, 1, -5, 4]$ the answer is 6.
Binary search is the degenerate case: one recursive call, constant combine, $\Theta(\log n)$ — the pattern survives with one branch.

{exercise:uni-cs1002-subarray}

Pratique

The maximum subarray of [-2, 1, -3, 4, -1, 2, 1, -5, 4] sums to —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui