1 CMSC 132: Object-Oriented Programming II Sorting!Department of Computer Science!University of Maryland, College Park!2 Overview ! Comparison sort ! Bubble sort ! Selection sort ! Tree sort ! Heap sort ! Quick sort ! Merge sort ! Linear sort ! Counting sort ! Bucket (bin) sort ! Radix sort O(n2) O(n log(n) ) O(n)3 Sorting ! Goal ! Arrange elements in predetermined order ! Based on key for each element ! Derived from ability to compare two keys by size ! Properties ! Stable ⇒ relative order of equal keys unchanged ! Stable: 3, 1, 4, 3, 3, 2 → 1, 2, 3, 3, 3, 4 ! Unstable: 3, 1, 4, 3, 3, 2 → 1, 2, 3, 3, 3, 4 ! In-place ⇒ uses only constant additional space ! External ⇒ can efficiently sort large # of keys4 Sorting ! Comparison sort ! Only uses pairwise key comparisons ! Proven lower bound of O( n log(n) ) ! Linear sort ! Uses additional properties of keys5 Bubble Sort ! Approach 1. Iteratively sweep through shrinking portions of list 2. Swap element x with its right neighbor if x is larger ! Performance ! O( n2 ) average / worst case6 Bubble Sort Example 7!2! 8! 5! 4!2!7 8 5! 4!2!7 8 5 4!2!7 5! 8 4 2!7 5! 4 8 2 7 5! 4 8 2!5 7 4 8 2!5 4! 7 8 2!7 5 4 8 2 5 4! 7 8 2!4 5 7 8 2!5 4 7 8 2 4 5 7 8 2!4 5 7 8 Sweep 1 Sweep 2 Sweep 3 Sweep 47 Bubble Sort Code void bubbleSort(int[ ] a) { int outer, inner; for (outer = a.length - 1; outer > 0; outer--) for (inner = 0; inner < outer; inner++) if (a[inner] > a[inner + 1]) swap(a, inner, inner+1); } void swap(int a[ ], int x, int y) { int temp = a[x]; a[x] = a[y]; a[y] = temp; } Sweep through array Swap with right neighbor if larger Swap array elements at positions x & y8 Selection Sort ! Approach 1. Iteratively sweep through shrinking portions of list 2. Select smallest element found in each sweep 3. Swap smallest element with front of current list ! Performance ! O( n2 ) average / worst case 7!2! 8! 5! 4!2!7 8! 5! 4!2 4 8 5! 7!2 4 5 8 7!2 4 5 7 8 ! Example9 Selection Sort Code void selectionSort(int[] a) { int outer, inner, min; for (outer = 0; outer < a.length - 1; outer++) { min = outer; for (inner = outer + 1; inner < a.length; inner++) { if (a[inner] < a[min]) { min = inner; } } swap(a, outer, min); } } Swap with smallest element found Sweep through array Find smallest element10 Tree Sort ! Approach 1. Insert elements in binary search tree 2. List elements using inorder traversal ! Performance ! Binary search tree ! O( n log(n) ) average case ! O( n2 ) worst case ! Balanced binary search tree ! O( n log(n) ) average / worst case 7 8 2 5 4 { 7, 2, 8, 5, 4 } ! Example Binary search tree11 Heap Sort ! Approach 1. Insert elements in heap 2. Remove smallest element in heap, repeat 3. List elements in order of removal from heap ! Performance ! O( n log(n) ) average / worst case 2 8 4 5 7 { 7, 2, 8, 5, 4 } ! Example Heap12 Quick Sort ! Approach 1. Select pivot value (near median of list) 2. Partition elements (into 2 lists) using pivot value 3. Recursively sort both resulting lists 4. Concatenate resulting lists ! For efficiency pivot needs to partition list evenly ! Performance ! O( n log(n) ) average case ! O( n2 ) worst case13 Quick Sort Algorithm 1. If list below size K ! Sort w/ other algorithm 2. Else pick pivot x and partition S into ! L elements < x ! E elements = x ! G elements > x 3. Quicksort L & G 4. Concatenate L, E & G ! If not sorting in place x x L G E x14 Quick Sort Code void quickSort(int[] a, int x, int y) { int pivotIndex; if ((y – x) > 0) { pivotIndex = partionList(a, x, y); quickSort(a, x, pivotIndex – 1); quickSort(a, pivotIndex+1, y); } } int partionList(int[] a, int x, int y) { … // partitions list and returns index of pivot } Lower end of array region to be sorted Upper end of array region to be sorted15 Quick Sort Example 7 2 8 5 4 2 5 4 7 8 5 4 2 4 5 2 4 5 7 8 2 4 5 7 8 4 5 2 4 5 Partition & Sort Result16 Quick Sort Code int partitionList(int[] a, int x, int y) { int pivot = a[x]; int left = x; int right = y; while (left < right) { while ((a[left] < pivot) && (left < right)) left++; while (a[right] > pivot) right--; if (left < right) swap(a, left, right); } swap(a, x, right); return right; } Use first element as pivot Partition elements in array relative to value of pivot Place pivot in middle of partitioned array return index of pivot17 Merge Sort ! Approach 1. Partition list of elements into 2 lists 2. Recursively sort both lists 3. Given 2 sorted lists, merge into 1 sorted list a) Examine head of both lists b) Move smaller to end of new list ! Performance ! O( n log(n) ) average / worst case18 Merge Example 2 4 7 5 8 2 7 4 5 8 2 7 4 5 8 2 4 5 7 8 2 4 5 7 8 2 4 5 7 819 Merge Sort Example 7 2 8 5 4 7 2 8 5 4 2 7 8 5 4 Split Merge 4 5 2 4 5 7 8 2 7 4 5 8 2 7 8 4 5 4 520 Merge Sort Code void mergeSort(int[] a, int x, int y) { int mid = (x + y) / 2; if (y == x) return; mergeSort(a, x, mid); mergeSort(a, mid+1, y); merge(a, x, y, mid); } void merge(int[] a, int x, int y, int mid) { … // merges 2 adjacent sorted lists in array } Lower end of array region to be sorted Upper end of array region to be sorted21 Merge Sort Code void merge (int[] a, int x, int y, int mid) { int size = y – x; int left = x; int right = mid+1; int[] tmp; int j; for (j = 0; j < size; j++) { if (left > mid) tmp[j] = a[right++]; else if (right > y) || (a[left] < a[right]) tmp[j] = a[left++]; else tmp[j] = a[right++]; } for (j = 0; j < size; j++) a[x+j] = tmp[j]; } Lower end of 1st array region Upper end of 2nd array region Upper end of 1st array region Copy merged array back Copy smaller of two elements at head of 2 array regions to tmp buffer, then move on22 Counting Sort !
View Full Document
Unlocking...