1Sorting AlgorithmsFawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewComparison sortBubble sortSelection sortTree sortHeap sortQuick sortMerge sortLinear sortCounting sort Bucket (bin) sortRadix sortO(n2)O(n log(n) )O(n)2SortingGoalArrange elements in predetermined order Based on key for each elementDerived from ability to compare two keys by sizePropertiesStable ⇒relative order of equal keys unchangedIn-place ⇒uses only constant additional spaceExternal ⇒can efficiently sort large # of keysSortingComparison sortOnly uses pairwise key comparisonsProven lower bound of O( n log(n) )Linear sortUses additional properties of keys3Bubble SortApproach1. Iteratively sweep through shrinking portions of list2. Swap element x with its right neighbor if x is largerPerformanceO( n2) average / worst caseBubble Sort Example 72 8 5 42 7 8 5 427 8 5 42 7 5 8 427 5 4 827 5 4 825 7 4 82 5 4 7 82 7 5 4 825 4 7 824 5 7 82 5 4 7 824 5 7 82 4 5 7 8Sweep 1 Sweep 2 Sweep 3 Sweep 44Bubble Sort Codevoid 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]) {int temp = a[inner]; a[inner] = a[inner + 1];a[inner + 1] = temp;}}}}Sweep through arraySwap with right neighbor if largerSelection SortApproach1. Iteratively sweep through shrinking portions of list2. Select smallest element found in each sweep3. Swap smallest element with front of current listPerformanceO( n2) average / worst case7 2 8 5 427 8 5 42 4 8 5 724 5 8 724 5 7 8Example5Selection Sort Codevoid 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;}}int temp = a[outer];a[outer] = a[min];a[min] = temp;}}Swap with smallest element foundSweep through arrayFind smallest elementTree SortApproach1. Insert elements in binary search tree2. List elements using inordertraversalPerformance Binary search treeO( n log(n) ) average caseO( n2) worst case Balanced binary search treeO( n log(n) ) average / worst case78254{ 7, 2, 8, 5, 4 }ExampleBinary search tree6Heap SortApproach1. Insert elements in heap2. Remove smallest element in heap, repeat 3. List elements in order of removal from heapPerformanceO( n log(n) ) average / worst case28457{ 7, 2, 8, 5, 4 }ExampleHeapQuick SortApproach1. Select pivot value (near median of list)2. Partition elements (into 2 lists) using pivot value3. Recursively sort both resulting lists4. Concatenate resulting listsFor efficiency pivot needs to partition list evenly PerformanceO( n log(n) ) average caseO( n2) worst case7Quick Sort Algorithm1. If list below size KSort w/ other algorithm2. Else pick pivot x and partition S into L elements < xE elements = xG elements > x3. Quicksort L & G4. Concatenate L, E & GIf not sorting in placexxL GExQuick Sort Codevoid 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 sortedUpper end of array region to be sorted8Quick Sort Example7 2 8 5 42 5 4 7 85 424 52 4 5 7 82 4 5 7 84 524 5Partition & Sort ResultQuick Sort Codeint 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 pivotPartition elements in array relative to value of pivotPlace pivot in middle of partitioned array, return index of pivot9Merge SortApproach1. Partition list of elements into 2 lists2. Recursively sort both lists3. Given 2 sorted lists, merge into 1 sorted lista) Examine head of both listsb) Move smaller to end of new list PerformanceO( n log(n) ) average / worst caseMerge Example2 475 82 74 5 8274 5 82 4 5782 4 5 782 4 5 7 810Merge Sort Example7 2 8 5 47 28 5 4278 5 4Split Merge452 4 5 7 82 74 5 8278 4 545Merge Sort Codevoid 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 sortedUpper end of array region to be sorted11Merge Sort Codevoid 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 1starray regionUpper end of 2ndarray regionUpper end of 1starray regionCopy merged array backCopy smaller of two elements at head of 2 array regions to tmp buffer, then move onCounting SortApproach1. Sorts keys with values over range 0..k2. Count number of occurrences of each key3. Calculate # of keys ≤ each key4. Place keys in sorted location using # keys countedIf there are x keys ≤ key y Put y in xthpositionDecrement x in case more instances of key yPropertiesO( n + k ) average / worst case12Counting Sort ExampleOriginal listCountCalculate # keys ≤ value0 1 2 3 47 2 8 5 40 1 2 3 4 5 6 7 80 0 1 0 1 1 0 1 10 0 1 1 2 3 3 4 50 1 2 3 4 5 6 7 8Counting Sort ExampleAssign locations0 0 1 1 2 3 3 4 50 1 2 3 4 5 6 7 87 2 8 5 40 1 2 3 42 77 2 8 5 40 1 2 3 42 4 5 7 87 2 8 5 40 1 2 3 42 7 87 2 8 5 40 1 2 3 477 2 8 5 40 1 2 3 42 5 7 84-1 = 31-1 = 05-1 = 42-1 = 13-1 = 213Counting Sort Codevoid countSort(int[] a, int k) { // keys have value 0…kint[] b; int[] c; int i;for (i = 0; i ≤k; i++) // initialize countsc[i] = 0;for (i = 0; i < a.size(); i++) // count # keysc[a[i]]++;for (i = 1; i ≤k; i++) // calculate # keys ≤value ic[i] = c[i] + c[i-1]for (i = a.size()-1; i > 0; i--) { b[c[a[i]]-1] = a[i]; // move key to locationc[a[i]]--; // decrement # keys ≤a[i]}for (i = 0; i < a.size(); i++) // copy sorted list back to aa[i] = b[i];}Bucket (Bin) SortApproach1. Divide key interval into k equal-sized subintervals2. Place
View Full Document
Unlocking...