DOC PREVIEW
UMD CMSC 132 - 24-sorting_new

This preview shows page 1-2-3-4-5-6-7-8-57-58-59-60-61-62-63-64-65-116-117-118-119-120-121-122-123 out of 123 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 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 123 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 123 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC 132: Object-Oriented Programming IISortingCMSC 132 Summer 2017 1What Is Sorting?• To arrange a collection of items in some specified order.• Numerical order • Lexicographical order• Input: sequence <a1, a2, …, an> of numbers.• Output: permutation <a'1, a'2, …, a’n> such that a'1 £ a'2£…£ a'n .• Example• Start à 1 23 2 56 9 8 10 100• End à 1 2 8 9 10 23 56 100CMSC 132 Summer 2017 2Why Sort?• A classic problem in computer science.• Data requested in sorted order• e.g., list students in increasing GPA order• Searching• To find an element in an array of a million elements• Linear search: average 500,000 comparisons• Binary search: worst case 20 comparisons• Database, Phone book• Eliminating duplicate copies in a collection of records• Finding a missing element, Max, MinCMSC 132 Summer 2017 3Sorting Algorithms• Selection Sort Bubble Sort• Insertion Sort Shell Sort• T(n)=O(n2) Quadratic growth• In clock time• Double input -> 4X time• Feasible for small inputs, quickly unmanagable• Halve input -> 1/4 time• Hmm... can recursion save the day?• If have two sorted halves, how to produce sorted full result?10,0003 sec20,00017 sec50,00077sec100,0005 minCMSC 132 Summer 2017 4Divide and Conquer1. Base case: the problem is small enough, solve directly2. Divide the problem into two or more similar and smallersubproblems3. Recursively solve the subproblems 4. Combine solutions to the subproblemsCMSC 132 Summer 2017 5Merge Sort• Divide and conquer algorithm• Worst case: O(nlogn)• Stable• maintain the relative order of records with equal values• Input: 12, 5, 8, 13, 8, 27 • Stable: 5, 8, 8, 12, 13, 27 • Not Stable:5, 8, 8, 12, 13, 27 CMSC 132 Summer 2017 6Merge Sort: IdeaMergeRecursively sortDivide intotwo halvesFirstPartSecondPartFirstPartSecondPartA:A is sorted!CMSC 132 Summer 2017 7Merge-Sort: MergeSorted SortedmergeA:L:R:SortedCMSC 132 Summer 2017 8Merge ExampleL:R:1 2 6 83 4 5 7A:CMSC 132 Summer 2017 9i=0j=0Merge ExampleL:R:11 2 6 83 4 5 7A:CMSC 132 Summer 2017 10i=1j=0Merge ExampleL:R:211 2 6 83 4 5 7A:CMSC 132 Summer 2017 11i=2j=0Merge Example cont.1 2 3 4 5 6 7 8L:A:3 5 15 286 10 14 22R:1 2 6 83 4 5 7i=4j=4k=8CMSC 132 Summer 2017 12Merge sort algorithmMERGE-SORT A[1 . . n]1. If n = 1, done.2. Recursively sort A[ 1 . . én/2ù ] and A[ én/2ù+1 . . n ] .3. “Merge” the 2 sorted lists.Key subroutine: MERGECMSC 132 Summer 2017 13Merge sort (Example) CMSC 132 Summer 2017 14Merge sort (Example) CMSC 132 Summer 2017 15Merge sort (Example) CMSC 132 Summer 2017 16Merge sort (Example) CMSC 132 Summer 2017 17Merge sort (Example) CMSC 132 Summer 2017 18Merge sort (Example)CMSC 132 Summer 2017 19Merge sort (Example)CMSC 132 Summer 2017 20Merge sort (Example)CMSC 132 Summer 2017 21Merge sort (Example)CMSC 132 Summer 2017 22Merge sort (Example)CMSC 132 Summer 2017 23Merge sort (Example)CMSC 132 Summer 2017 24Merge sort (Example)CMSC 132 Summer 2017 25Merge sort (Example)CMSC 132 Summer 2017 26Merge sort (Example)CMSC 132 Summer 2017 27Merge sort (Example)CMSC 132 Summer 2017 28Merge sort (Example)CMSC 132 Summer 2017 29Merge sort (Example)CMSC 132 Summer 2017 30Merge sort (Example) CMSC 132 Summer 2017 31Merge sort (Example)CMSC 132 Summer 2017 32Merge sort (Example)CMSC 132 Summer 2017 33Analysis of merge sortMERGE-SORT A[1 . . n]1. If n = 1, done.2. Recursively sort A[ 1 . . én/2ù ]and A[ én/2ù+1 . . n ] .3.“Merge”the 2 sorted listsT(n)Q(1)2T(n/2)Q(n)CMSC 132 Summer 2017 34Analyzing merge sortT(n) =Q(1) if n = 1;2T(n/2) + Q(n) if n > 1.T(n) = Q(n lg n) (n > 1) CMSC 132 Summer 2017 35Recursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant.cncn/4 cn/4cn/4 cn/4cn/2cn/2Q(1)h = log ncncncn#leaves = nQ(n)Total = Q(n log n)…CMSC 132 Summer 2017 36Memory RequirementNeeds additional n locations because it is difficult to merge two sorted sets in placeL:R:1 2 6 83 4 5 7A:CMSC 132 Summer 2017 37Merge Sort Conclusion• Merge Sort: O(n log n)• asymptotically beats insertion sort in the worst case• In practice, merge sort beats insertion sort for n > 30 or so• Space requirement: • O(n), not in-placeCMSC 132 Summer 2017 38HEAPSORTCMSC 132 Summer 2017 39Heapsort• Merge sort time is O(n log n) but still requires, temporarily, n extra storage locations• Heapsort does not require any additional storage• As its name implies, heapsort uses a heap to store the arrayCMSC 132 Summer 2017 40Heapsort Algorithm• When used as a priority queue, a heap maintains a smallest value at the top• The following algorithm • places an array's data into a heap, • then removes each heap item (O(n log n)) and moves it back into the array• This version of the algorithm requires n extra storage locationsHeapsort Algorithm: First Version1. Insert each value from the array to be sorted into a priority queue (heap).2. Set i to 03. while the priority queue is not empty4. Remove an item from the queue and insert it back into the array at position i5. Increment iCMSC 132 Summer 2017 41Trace of Heapsort89767437 32 39 6620 26 18 28 29 6CMSC 132 Summer 2017 42Trace of Heapsort (cont.)89767437 32 39 6620 26 18 28 29 6CMSC 132 Summer 2017 43Trace of Heapsort (cont.)89767437 32 39 6620 26 18 28 29 6CMSC 132 Summer 2017 44Trace of Heapsort (cont.)6767437 32 39 6620 26 18 28 29 89CMSC 132 Summer 2017 45Trace of Heapsort (cont.)7667437 32 39 6620 26 18 28 29 89CMSC 132 Summer 2017 46Trace of Heapsort (cont.)7637746 32 39 6620 26 18 28 29 89CMSC 132 Summer 2017 47Trace of Heapsort (cont.)76377426 32 39 6620 6 18 28 29 89CMSC 132 Summer 2017 48Trace of Heapsort (cont.)76377426 32 39 6620 6 18 28 29 89CMSC 132 Summer 2017 49Trace of Heapsort (cont.)76377426 32 39 6620 6 18 28 29 89CMSC 132 Summer 2017 50Trace of Heapsort (cont.)76377426 32 39 6620 6 18 28 29 89CMSC 132 Summer 2017 51Trace of Heapsort (cont.)29377426 32 39 6620 6 18 28 76 89CMSC 132 Summer 2017 52Trace of Heapsort (cont.)74372926 32 39 6620 6 18 28 76 89CMSC 132 Summer 2017 53Trace of Heapsort (cont.)74376626 32 39 2920 6 18 28 76 89CMSC 132 Summer 2017 54Trace of Heapsort (cont.)74376626 32 39 2920 6 18 28 76 89CMSC 132 Summer 2017 55Trace of Heapsort (cont.)74376626 32 39 2920 6 18 28 76 89CMSC 132 Summer 2017 56Trace of Heapsort (cont.)74376626 32 39 2920 6 18 28 76 89CMSC 132 Summer 2017 57Trace of Heapsort (cont.)28376626 32 39 2920 6 18 74 76 89CMSC 132 Summer 2017 58Trace of Heapsort (cont.)6182026 28 29 3237


View Full Document

UMD CMSC 132 - 24-sorting_new

Download 24-sorting_new
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 24-sorting_new 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 24-sorting_new 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?