DOC PREVIEW
USF CS 245 - Data Structures and Algorithms

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

{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

USF CS 245 - Data Structures and Algorithms

Download Data Structures and Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Data Structures and Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Data Structures and Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?