Sorting
Sorting!
-What’s a sorting algorithm? -Insertion sort
-Merge sort
-Divide & conquer (Master’s thm) -Quicksort
Outline
Sorting!
-What’s a sorting algorithm? -Insertion sort
-Merge sort
-Divide & conquer (Master’s thm) -Quicksort
Outline
Input: sequence of numbers = {a1, a2, … an}
Output: different order = {a1′, a2′, … an’}, where
a1′ < a2' < ... < an'
Sorting problem
General idea:
-Examine one element at a time
-Insert into correct place in an already sorted sequence
-Repeat...
Insertion sort
Where to put a 10 of spades? A 6 of hearts?
Insertion sort
Where to put a 10 of spades? A 6 of hearts? Between 5 and 7
Insertion sort
Input: A[1,2, ... n] for j = 2 to n
i=j-1
key = A[j] // why do we need this? while i > 0 AND A[i] > key
A[i+1] = A[i]
i= i – 1 A[i+1] = key
0
Insertion sort
Sort: {4, 5, 3, 8, 1, 6, 2}
1
Insertion sort
Sort: {4, 5, 3, 8, 1, 6, 2}
{4} – done
{4, 5} – done
{4, 5, 3}, {4,3,5}, {3,4,5} – done {3, 4, 5, 8} – done
{3, 4, 5, 8, 1}, {3, 4, 5, 1, 8}, {3, 4, 1, 5, 8}, {3, 1, 4, 5, 8}, {1, 3, 4, 5, 8} – done
2
Insertion sort
Sort: {4, 5, 3, 8, 1, 6, 2}
{1, 3, 4, 5, 8} – done
{1, 3, 4, 5, 8, 6}, {1, 3, 4, 5, 6, 8} -done
{1, 3, 4, 5, 6, 8, 2},{1, 3, 4, 5, 6, 2, 8} {1, 3, 4, 5, 2, 6, 8},{1, 3, 4, 2, 5, 6, 8} {1, 3, 2, 4, 5, 6, 8},{1, 2, 3, 4, 5, 6, 8} -done and done
3
Insertion sort
Worst case runtime?
Average case?
4
Insertion sort
Worst case runtime?
Outer loop runs n times and inner loop runs j-1 times
1+2+3+ … + n-1 = ?
Average case?
5
Insertion sort
Worst case runtime?
Outer loop runs n times and inner loop runs j-1 times
1+2+3+ … + n-1 = n(n-1)/2 = O(n2)
Average case?
inner loop (j-1)/2 times = O(n2)
6
Insertion sort
Correctness:
Base: Initial list is 1 element, sorted Step: Inner loop places everything bigger than key after it and everything smaller before. Before & after will be sorted as it started sorted Termination: Terminates after n A[n] placed, so whole list sorted
7
Insertion sort