CS245-2014S-10 Sorting 110-0: Main Memory Sorting• All data elements can be stored in memory at the same time• Data stored in an array, indexed from 0 . . . n − 1, where n is the number of elements• Each element has a key value (accessed with a key() me thod)• We can compare keys for ¡, ¿, =• For illustration, we will use arrays of integers – though often keys will be strings, other Comparable types10-1: Stable Sorting• A sorting algorithm is Stable if the relative order of duplica te s is preserved• The order of duplicates matters if the keys are duplicated, but the records are not.3 1 2 1 1 2 3BobJoeEdAmySueAlBudKeyData1 1 1 2 2 3 3AmyJoeSueEdAlBobBudKeyDataA non-Stable sort10-2: Insertion Sort• Separate list into sorted portion, and unsorted portion• Initially, sorted portion contains first element in the list, unsorted portion is the rest of the list• (A list of one element is always sorted)• Repeatedly insert an e lement fro m the unsorted list into the sorted list, until the list is sorted10-3: Θ() For Insertion Sort• Running time ∝ # of com parisons• Worst Case:10-4: Θ() For Insertion Sort• Running time ∝ # of com parisons• Worst Case: Inverse sorted list# of co mparisons:10-5: Θ() For Insertion Sort• Running time ∝ # of com parisonsCS245-2014S-10 Sorting 2• Worst Case: Inverse sorted list# of co mparisons:n−1Xi=1i ∈ Θ(n2)10-6: Θ() For Insertion Sort• Running time ∝ # of com parisons• Best Case:10-7: Θ() For Insertion Sort• Running time ∝ # of com parisons• Best Case: Sorted List# of co mparisons:10-8: Θ() For Insertion Sort• Running time ∝ # of com parisons• Best Case: Sorted List# of co mparisons:n − 110-9: Bubble Sort• Scan list from the last ind ex to index 0 , swapping the smallest element to the front of the list• Scan the list from the la st index to index 1, swapping the second smallest element to index 1• Scan the list from the la st index to index 2, swapping the third smallest elemen t to index 2. . .• Swap the second largest element into position (n − 2)10-10: Θ() for Bubble Sort• Running time ∝ # of com parisons• Number of Compa risons:10-11: Θ() for Bubble Sort• Running time ∝ # of com parisons• Number of Compa risons:n−1Xi=1i ∈ Θ(n2)10-12: Selection Sort• Scan through th e list, and find the smallest elementCS245-2014S-10 Sorting 3• Swap sm allest element into position 0• Scan through th e list, and find the second smallest element• Swap second smallest element into position 1. . .• Scan through th e list, and find the second largest element• Swap sm allest largest into position n − 210-13: Θ() for Selection Sort• Running time ∝ # of com parisons• Number of Compa risons:10-14: Θ() for Selection Sort• Running time ∝ # of com parisons• Number of Compa risons:n−1Xi=1i ∈ Θ(n2)10-15: Improving Insertion Sort• Insertion sort is fast if a list is “almost sorted”• How can we use this?• Do some work to make the list “almost sorted”• Run insertion sort to finish sorting the list• Only helps if work required to make list “almost sorted” is less than n210-16: Shell Sort• Sort n/2 sublists of length 2, using insertion sor t• Sort n/4 sublists of length 4, using insertion sor t• Sort n/8 sublists of length 8, using insertion sor t. . .• Sort 2 sublists of length n/2, using insertion sort• Sort 1 sublist of length n, using insertion sort10-17: Shell’s Increments• Shell sort runs several insertion sorts, using increments• Code on monitor uses “Shell’s Increments”: {n/2, n/4, . . .4, 2, 1}• Problem with Shell’s Incre ments:CS245-2014S-10 Sorting 4• Various sorts do no t interact much• If all large elements are stored in large indic es, and small elements are stored in even indices, what hap-pens?10-18: Other Increments• Shell’s Incr ements: {n/2, n/4, . . . 4, 2, 1}• Running time: O(n2)• “/3” increments: {n/3, n/9, . . . , 9, 3, 1}• Running time: O(n32)• Hibbard’s Increments: {2k− 1, 2k−1− 1, . . . 7, 3, 1}• Running time: O(n32)10-19: Shell Sort: Best case• What is the b est case running time for Shell Sort (using Shell’s increments)• When would the best case occur?10-20: Shell Sort: Best case• What is the b est case running time for Shell Sort (using Shell’s increments)• When would the best case occur?• When the list was origin ally sorted• How long would each pass through Shell Sort take?10-21: Shell Sort: Best case• What is the b est case running time for Shell Sort (using Shell’s increments)• When would the best case occur?• When the list was origin ally sorted• How long would each pass through Shell Sort take?• Θ(n)• How Many Passes?10-22: Shell Sort: Best case• What is the b est case running time for Shell Sort (using Shell’s increments)• When would the best case occur?• When the list was origin ally sorted• How long would each pass through Shell Sort take?• Θ(n)• How Many Passes?• lg nCS245-2014S-10 Sorting 5• Total running time?10-23: Shell Sort: Best case• What is the b est case running time for Shell Sort (using Shell’s increments)• When would the best case occur?• When the list was origin ally sorted• How long would each pass through Shell Sort take?• Θ(n)• How Many Passes?• lg n• Total running time?• Θ(n lg n)10-24: Stability• Is Insertion sort stable?• Is Bubble Sor t stable?• Is Selection Sort stable?• Is Shell Sort stable?10-25: Stability• Is Insertion sort stable? Yes!• Is Bubble Sor t stable? Yes!• Is Selection Sort stable? No!• Is Shell Sort stable? No!Note th at minor changes to the stable sorting algorithms will make them unstable (for instance, swaping A[i] andA[i + 1 ] when A[i] ≥ A[i + 1], not just when A[i] > A[i +