Please enable JavaScript.
Coggle requires JavaScript to display documents.
Brute Force and Exaustive Search, Decrease-and-Conquer, Divide-and-Conquer…
Brute Force and Exaustive Search
Selection Sort
O(n²) complexity, O(n) key swaps
Iterate through the array looking for the smallest element. Swap it with an element on the start of the array.
for i ← 0 to n − 2 do
for j ← i + 1 to n − 1 do
if A[j ] < A[min] min ← j
swap A[i] and A[min]
min ← i
Bubble Sort
O(n²) complexity and key swaps
Do n² passes on the array comparing adjacent elements
for i ← 0 to n − 2 do
for j ← 0 to n − 2 − i do
if A[j + 1] < A[j ] swap A[j ] and A[j + 1]
Decrease-and-Conquer
Insertion Sort
O(n²) complexity and O(n²) key swaps at worse
Same way we sort a deck of cards, put each element in its correct place and repeat
for i ← 1 to n − 1 do
j ← i − 1
while j ≥ 0 and A[j ] > v do
A[j + 1]← A[j ]
j ← j − 1
v ← A[i]
A[j + 1] ← v
Divide-and-Conquer
Merge Sort
O(n logn) complexity
Divide into sub-arrays and merge them later when the smallest arrays possible are sorted
Merge Sort
pseudocode
if n > 1
copy A[0..floor(n/2) − 1] to B[0..floor(n/2) − 1]
copy A[floor(n/2)..n − 1] to C[0..ceil(n/2) − 1]
Mergesort(B[0..floor(n/2) − 1])
Mergesort(C[0..ceil(n/2) − 1])
Merge(B, C, A) //see below
Merge
pseudocode
← 0; j ← 0; k ← 0
while i<p and j<q do
if B[i] ≤ C[j ]
A[k]← B[i]; i ← i + 1
else A[k]← C[j ]; j ← j + 1
k ← k + 1
if i = p
copy C[j..q − 1] to A[k..p + q − 1]
else copy B[i..p − 1] to A[k..p + q − 1]