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 the full content.
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 the full content.
View Full Document
View Full Document

24-sorting_new

9 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



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

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 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?