# UMD CMSC 132 - 24-sorting_new (123 pages)

Previewing pages 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 of 123 page document
View Full Document

## 24-sorting_new

Previewing pages 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 of actual document.

View Full Document
View Full Document

## 24-sorting_new

87 views

Pages:
123
School:
University of Maryland, College Park
Course:
Cmsc 132 - Object-oriented Programming II
Unformatted text preview:

CMSC 132 Object Oriented Programming II Sorting CMSC 132 Summer 2017 1 What 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 100 CMSC 132 Summer 2017 2 Why 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 Min CMSC 132 Summer 2017 3 Sorting Algorithms Selection Sort Insertion Sort T n O n2 Quadratic growth In clock time Bubble Sort Shell Sort 10 000 3 sec 20 000 17 sec 50 000 77 sec 100 000 5 min 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 CMSC 132 Summer 2017 4 Divide and Conquer 1 Base case the problem is small enough solve directly 2 Divide the problem into two or more similar and smaller subproblems 3 Recursively solve the subproblems 4 Combine solutions to the subproblems CMSC 132 Summer 2017 5 Merge 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 6 Merge Sort Idea Divide into two halves A FirstPart SecondPart FirstPart Recursively sort SecondPart Merge A is sorted CMSC 132 Summer 2017 7 Merge Sort Merge Sorted A merge Sorted L CMSC 132 Summer 2017 Sorted R 8 Merge Example A L 1 2 i 0 CMSC 132 Summer 2017 6 8 R 3 4 5 7 j 0 9 Merge Example A L 1 1 2 i 1 CMSC 132 Summer 2017 6 8 R 3 4 5 7 j 0 10 Merge Example A L 1 1 2 2 6 i 2 CMSC 132 Summer 2017 8 R 3 4 5 7 j 0 11 Merge Example cont A 1 2 3 4 5 6 7 8 k 8 R L 3 1 5 2 15 6 28 8 6 3 i 4 CMSC 132 Summer 2017 10 4 14 5 22 7 j 4 12 Merge sort algorithm MERGE 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 MERGE CMSC 132 Summer 2017 13 Merge sort Example CMSC 132 Summer 2017 14 Merge sort Example CMSC 132 Summer 2017 15 Merge sort Example CMSC 132 Summer 2017 16 Merge sort Example CMSC 132 Summer 2017 17 Merge sort Example CMSC 132 Summer 2017 18 Merge sort Example CMSC 132 Summer 2017 19 Merge sort Example CMSC 132 Summer 2017 20 Merge sort Example CMSC 132 Summer 2017 21 Merge sort Example CMSC 132 Summer 2017 22 Merge sort Example CMSC 132 Summer 2017 23 Merge sort Example CMSC 132 Summer 2017 24 Merge sort Example CMSC 132 Summer 2017 25 Merge sort Example CMSC 132 Summer 2017 26 Merge sort Example CMSC 132 Summer 2017 27 Merge sort Example CMSC 132 Summer 2017 28 Merge sort Example CMSC 132 Summer 2017 29 Merge sort Example CMSC 132 Summer 2017 30 Merge sort Example CMSC 132 Summer 2017 31 Merge sort Example CMSC 132 Summer 2017 32 Merge sort Example CMSC 132 Summer 2017 33 Analysis of merge sort T n Q 1 2T n 2 Q n CMSC 132 Summer 2017 MERGE 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 34 Analyzing merge sort T n Q 1 if n 1 2T n 2 Q n if n 1 T n Q n lg n CMSC 132 Summer 2017 n 1 35 Recursion tree Solve T n 2T n 2 cn where c 0 is constant cn cn cn 2 cn 2 cn 4 cn 4 cn 4 cn 4 cn h log n cn Q 1 leaves n Q n Total Q n log n CMSC 132 Summer 2017 36 Memory Requirement Needs additional n locations because it is difficult to merge two sorted sets in place A L 1 2 CMSC 132 Summer 2017 6 8 R 3 4 5 7 37 Merge 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 place CMSC 132 Summer 2017 38 HEAPSORT CMSC 132 Summer 2017 39 Heapsort 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 array CMSC 132 Summer 2017 40 Heapsort 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 locations Heapsort Algorithm First Version 1 Insert each value from the array to be sorted into a priority queue heap 2 Set i to 0 3 while the priority queue is not empty 4 Remove an item from the queue and insert it back into the array at position i 5 Increment i CMSC 132 Summer 2017 41 Trace of Heapsort 89 74 76 37 20 32 26 CMSC 132 Summer 2017 18 39 28 29 66 6 42 Trace of Heapsort cont 89 74 76 37 20 32 26 CMSC 132 Summer 2017 18 39 28 29 66 6 43 Trace of Heapsort cont 89 74 76 37 20 32 26 CMSC 132 Summer 2017 18 39 28 29 66 6 44 Trace of Heapsort cont 6 74 76 37 20 32 26 CMSC 132 Summer 2017 18 39 28 29 66 89 45 Trace of Heapsort cont 76 74 6 37 20 32 26 CMSC 132 Summer 2017 18 39 28 29 66 89 46 Trace of Heapsort cont 76 74 37 6 20 32 26 CMSC 132 Summer 2017 18 39 28 29 66 89 47 Trace of Heapsort cont 76 74 37 26 20 32 6 CMSC 132 Summer 2017 18 39 28 29 66 89 48 Trace of Heapsort cont 76 74 37 26 20 32 6 CMSC 132 Summer 2017 18 39 28 29 66 89 49 Trace of Heapsort cont 76 74 37 26 20 32 6 CMSC 132 Summer 2017 …

View Full Document

Unlocking...