Sorting
REVIEW
QUADRATIC – executes in n2 time
IN-PLACE – sorts without using extra space outside the container itself
Selection sort: QUADRATIC, IN-PLACE Bubble sort: QUADRATIC, IN-PLACE
Find smallest element and move it to position 0. Find next smallest element, and Swap adjacent elements if they are out of order and repeat swapping until you reach
move it to position 1 … Repeat (size – 1) times end of container. Go back to the start of container and do it all over again … Repeat
(size – 1) times.
Swap!
Find smallest element (3) and Initial Array
Initial Array
place at correct position 0
after 1st pass Find next smallest element (5)
and place at correct position 1 Swap!
after 2nd pass Find next smallest element (7)
and place at correct position 2
after 1st pass
after 3rd pass Swap!
Worst = O(n2)
Average = O(n2)
Best = O(n2)
Best case is O(n) because
Space = O(1) there is an optimization
technique you can use in
the algorithm to check if
the array is already
Insertion sort: QUADRATIC, IN-PLACE sorted
after 2nd pass
There is a sorted, and an unsorted region. Initially, sorted region has only one This means for a
element (the first element). sorted array,
Bubble sort will
Grab the first element from the unsorted region and insert it into its correct place execute in O(n)
within the sorted region. Repeat until there are no more elements in unsorted time
region.
Initial Array
Worst = O(n2)
Average = O(n2)
after 1st pass Grab first element in Best = O(n)
after 3rd pass
unsorted region (3) and
place where it belongs Space = O(1)
(before 7) in sorted
after 2nd pass region
Shell sort
after 3rd pass Shell sort is a special variant of insertion sort but with O(n3/2) performance :D
Sorts many smaller subarrays using insertion sort before sorting entire array.
Initial Array
after 4th pass Gap = n /2 = 4 Compare and swap!
after 1st pass Compare and swap!
Worst = O(n ) 2 Gap = (n /2) / 2 = 2
For an array that
is already sorted, Average = O(n2)
inner loop of
Best = O(n) Worst = O(n2)
algorithm will not Continue dividing gap by 2
execute Space = O(1) until it = 1. Do one more
Average = O(n5/4)
compare + swap and you’re Best = O(n7/6)
done! Space = O(1)
Merge sort: NON-QUADRATIC, NOT IN-PLACE
Splits array in half, sorts the two smaller halves then merges them together. Initial Array
Algorithm is broken into two functions: mergeSort and merge Divide
array into
mergeSort(int [] array, int start, int end) smaller
{ subarrays
if(start < end) until you
{ reach a
int middle = (start + end) / 2; size of
mergeSort(array, start, middle); // sort left half one
mergeSort(array, middle + 1, end); // sort right half
merge(array, start, middle, end); // merge two halves
}
}
Sorted left half Sorted right half
Conquer:
combine
- merge(array = ) two
subarrays
and sort
left_copy = All this copy making
is what causes the
merge sort algorithm
right_copy = to take O(n) space
while (elements are still left in either copy)
// compare element i from left_copy
// with element j of right_copy
// put smaller element at position k in array
Worst = O(n*log(n))
Average = O(n*log(n))
- mergeSort takes O(log(n)) time and merge takes O(n) time Best = O(n*log(n))
so together, they take O(n*log(n)) time Space = O(n)
Quick sort: IN-PLACE Heap sort: IN-PLACE
Chooses pivot element (usually the first element in array). Re-arranges array so that all Builds a max heap from the array in place then extracts elements one by
elements <= pivot are in left subarray and all elements > pivot are in right subarray. one.
Recursively call quicksort on left and right subarrays. Building heap is O(n)
up down Every extraction is O(log(n)) [O(1) to remove, and O(log(n)) to heapify]
Initial Array move “up” ptr until it finds value > 7
move “down” ptr until it finds value <= 7 Initial Array
Pivot = 7
Swap!
up down
swap array[up] with array[down]
Delete 9
(store at end of array)
up down
move “up” ptr until it finds value > 7
move “down” ptr until it finds value <= 7
up down
swap array[up] with array[down] Heapify!
up down
move “up” ptr until it finds value > 7
move “down” ptr until it finds value <= 7
down up
STOP! “down” passed “up”
Swap array[pivot] with array[down] Repeat!
after 1st pass Worst = O(n2) Worst = O(n*log(n))
Average = O(n*log(n)) Average = O(n*log(n))
Best = O(n*log(n)) Best = O(n*log(n))
Now we recursively call quicksort on left and right subarrays
Space = O(log(n)) Space = O(1)
