# 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

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

Unlocking...