{small lecturenumber - heblocknumber :} Main Memory Sortingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Stable Sortingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Insertion Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$For Insertion Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$For Insertion Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$For Insertion Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$For Insertion Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$For Insertion Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$For Insertion Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Bubble Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Bubble Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Bubble Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Selection Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Selection Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} $Theta ()$for Selection Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Improving Insertion Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Shell Sortaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Shell's Incrementsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Other Incrementsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Shell Sort: Best caseaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Shell Sort: Best caseaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Shell Sort: Best caseaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Shell Sort: Best caseaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Shell Sort: Best caseaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Stabilityaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Stabilityaddtocounter {blocknumber}{1}Data Structures and AlgorithmsCS245-2014S-10SortingDavid GallesDepartment of Computer ScienceUniversity of San Francisco10-0: Main Memory SortingAll data elements can be stored in memory at thesame timeData stored in an array, indexed from 0 . . . n − 1,where n is the number of elementsEach element has a key value (accessed with akey() method)We can compare keys for <, >, =For illustration, we will use arrays of integers –though often keys will be strings, otherComparable types10-1: Stable SortingA sorting algorithm i s Stable if the relative order ofduplicates is preservedThe order of duplicates matters if the keys areduplicated, but the records are not.3 1 2 1 1 2 3BobJoeEdAmySueAlBudKeyData1 1 1 2 2 3 3AmyJoeSueEdAlBobBudKeyDataA non-Stable sort10-2: Insertion SortSeparate list into sorted porti on, and unsortedportionInitially, sorted portion contains first element in thelist, unsorted portion is the rest of the list(A list of one element is always sorted)Repeatedly insert an element from the unsortedlist into the sorted list, until the list is sorted10-3: Θ() For Insertion SortRunning time ∝ # of compari sonsWorst Case:10-4: Θ() For Insertion SortRunning time ∝ # of compari sonsWorst Case: Inverse sort ed list# of comparisons:10-5: Θ() For Insertion SortRunning time ∝ # of compari sonsWorst Case: Inverse sort ed list# of comparisons:n−1Xi=1i ∈ Θ(n2)10-6: Θ() For Insertion SortRunning time ∝ # of compari sonsBest Case:10-7: Θ() For Insertion SortRunning time ∝ # of compari sonsBest Case: Sorted List# of comparisons:10-8: Θ() For Insertion SortRunning time ∝ # of compari sonsBest Case: Sorted List# of comparisons:n − 110-9: Bubble SortScan list from the last index to index 0, swappingthe smallest element to the front of the listScan the list from the last index to index 1,swapping the second smallest element to index 1Scan the list from the last index to index 2,swapping the third smallest element to index 2. . .Swap the second largest element into position(n − 2)10-10: Θ() for Bubble SortRunning time ∝ # of compari sonsNumber of Comparisons:10-11: Θ() for Bubble SortRunning time ∝ # of compari sonsNumber of Comparisons:n−1Xi=1i ∈ Θ(n2)10-12: Selection SortScan through the list, and find the sm allest elementSwap smallest element into position 0Scan through the list, and find the second smallestelementSwap second smallest element into posit i on 1. . .Scan through the list, and find the second largestelementSwap smallest largest into position n − 210-13: Θ() for Selection SortRunning time ∝ # of compari sonsNumber of Comparisons:10-14: Θ() for Selection SortRunning time ∝ # of compari sonsNumber of Comparisons:n−1Xi=1i ∈ Θ(n2)10-15: Improving Insertion SortInsertion sort i s fast if a list is “almost sorted”How can we use this?Do some work to make the list “almost sorted”Run insertion sort t o finish sorting the listOnly helps if work required to make list “almostsorted” is less than n210-16: Shell SortSort n/2 sublists of length 2, using insert ion sortSort n/4 sublists of length 4, using insert ion sortSort n/8 sublists of length 8, using insert ion sort. . .Sort 2 sublists of length n/2, using insertion sortSort 1 sublist of length n, using insertion sort10-17: Shell’s IncrementsShell sort runs several insertion sorts, usingincrementsCode on monitor uses “Shell’s Increments”:{n/2, n/4, . . . 4, 2, 1}Problem with Shell’s Increments:Various sorts do not interact muchIf all large elements are stored in large indices,and small elements are stored in even indices,what happens?10-18: Other IncrementsShell’s Increments: {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 caseWhat is the best case r unning time for Shell Sort(using Shell’s increments)When would the best case occur?10-20: Shell Sort: Best caseWhat is the best case r unning time for Shell Sort(using Shell’s increments)When would the best case occur?When the list was
View Full Document