[SOLVED] CS algorithm Sorting

Sorting

Sorting!
-Whats a sorting algorithm? -Insertion sort
-Merge sort
-Divide & conquer (Masters thm) -Quicksort
Outline

Sorting!
-Whats a sorting algorithm? -Insertion sort
-Merge sort
-Divide & conquer (Masters 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 sortInput: A[1,2, … n] for j = 2 to ni=j-1key = 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