Sorting AlgorithmsOverviewSortingSlide 4Bubble SortBubble Sort ExampleBubble Sort CodeSelection SortSelection Sort CodeTree SortHeap SortQuick SortQuick Sort AlgorithmQuick Sort CodeQuick Sort ExampleSlide 16Merge SortMerge ExampleMerge Sort ExampleMerge Sort CodeSlide 21Counting SortCounting Sort ExampleSlide 24Counting Sort CodeBucket (Bin) SortBucket Sort ExampleRadix SortRadix Sort ExampleSorting PropertiesSorting SummarySorting 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)SortingGoalArrange 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 keysBubble 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 427 8 5 427 8 5 427 5 8 427 5 4 827 5 4 825 7 4 825 4 7 827 5 4 825 4 7 824 5 7 825 4 7 824 5 7 824 5 7 8Sweep 1 Sweep 2 Sweep 3 Sweep 4Bubble 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 case72 8 5 427 8 5 424 8 5 724 5 8 724 5 7 8ExampleSelection 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 inorder traversalPerformance 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 treeHeap 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 caseQuick 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 sortedQuick 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 pivotMerge 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 8Merge 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 sortedMerge 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 1st array regionUpper end of 2nd array regionUpper end of 1st array 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 xth positionDecrement x in case more instances of key yPropertiesO( n + k ) average / worst caseCounting Sort ExampleOriginal listCountCalculate # keys value0 1 2 3 4 7 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 4 2 77 2 8 5 40 1 2 3 4 2 4 5 7 87 2 8 5 40 1 2 3 4 2 7 87 2 8 5 40 1 2 3 4 77 2 8 5 40 1 2 3 4 2 5 7
View Full Document
Unlocking...