ch 7 sorts

Question 1

insertion sort

Answer 1

5 4 3 2 1
4 5 3 2 1
3 4 5 2 1 
2 3 4 5 1 
1 2 3 4 5

Question 2

heapsort

Answer 2

used in priortiy queue
call delete max
instead of deleting the first element, simply put it to the back of the array
therefore, you will end up with an array of sorted decreasing numbers
97 53 39 26 41 58 31
53 39 26 41 58 31 97
NlogN?

Question 3

Mergesort

Answer 3

O(Nlogn)
splits large array up so each individual index is its own array
compares indexes of the left and right sides, adds to a slightly larger array
continues doing this until there is only one array left

5263
5 2 6 3
25 36 
5 36            2
5 6              23
6                 235
2356

Question 4

picking the pivot for quicksort

Answer 4

median of three
pick the first, last, and center index
the median of the three is the pivot

Question 5

quicksort

Answer 5

pick a pivot
move it to the very end
i (left pointer) should be smaller than pivot
j (right pointer) should be larger than pivot
if both i and j are incorrect, swap the two
when j passes i, swap i with the pivot
call quicksort on the left and right pivots

worst case N^2
average case NlogN

look at notes for review onn ccode