Sequential SortingA Lower Bound on SpeedSorting AlgorithmsSelection SortSlide 5Insertion SortSlide 7Bubble SortSlide 9Shell Sortn=3Bucket SortNumbers are bound from 1 to 29 starting with: 5 2 19 22 25 7 3 16Radix SortSlide 15Quick SortSlide 17Slide 18Works CitedSequential SortingSean LynCOP4800February 5, 2008A Lower Bound on Speed•The fastest any comparison based sort can sort a list is O(NlogN)•The longest any comparison based sort should take is O(N²)Sorting Algorithms•Selection Sort•Insertion Sort•Bubble Sort•Shell Sort•Bucket Sort•Radix Sort•Quick Sort•Merge Sort – not covered•Heap Sort – not coveredSelection Sort•“Selects” the smallest element•Find the smallest element•Put that element at the beginning•Repeat•Speed: O(N²)7 1 3 5 6 4 8 21 7 3 5 6 4 8 21 2 3 5 6 4 8 71 2 3 5 6 4 8 71 2 3 4 6 5 8 71 2 3 4 5 6 8 71 2 3 4 5 6 8 71 2 3 4 5 6 7 8Insertion Sort•“Inserts” the element into the right position•Start with the first element•Insert the next element into the current list in the right position•Repeat•Speed: O(N²)7 1 3 5 6 4 8 21 7 3 5 6 4 8 21 3 7 5 6 4 8 21 3 5 7 6 4 8 21 3 5 6 7 4 8 21 3 4 5 6 7 8 21 3 4 5 6 7 8 21 2 3 4 5 6 7 8Bubble Sort•Compare the first two elements•Put them in order •Compare the second and third•Put them in order•Repeat this process•Speed: O(N²)7 1 3 5 6 4 8 21 3 5 6 4 7 2 81 3 5 4 6 2 7 81 3 4 5 2 6 7 81 3 4 2 5 6 7 81 3 2 4 5 6 7 81 2 3 4 5 6 7 8Shell Sort•Sort the kth element of every nth set of elements where k goes from 1 to n•Repeat the process on (n-1) until n=1•n <= size/2•Speed: up to O(N^(7/6))n=37 1 3 5 6 4 8 25 7 85 1 7 2 8 65 1 3 7 2 4 8 62 3 5 82 1 3 4 5 6 8 71 2 3 4 5 6 7 8Bucket Sort•Put the elements into “buckets” of smaller denominations based on their most significant digits•Repeat on each bucket•Speed: O(N) – varies due to the bound of the digitsNumbers are bound from 1 to 29starting with: 5 2 19 22 25 7 3 160 1 25 2 7 3 19 16 22 250 1 2 3 4 5 6 7 8 92 3 5 76 916 192 522 25Radix Sort•Sort the array based on the least significant digit•Sort the array based on the next least significant digit•Repeat until the array is sorted•Speed: O(N) – varies depending on the bound of the digits5 2 19 22 25 7 3 162 22 3 5 25 16 7 192 3 5 7 16 19 22 25Quick Sort•Pick a pivot•Put all numbers lower than the pivot to the left of it and all numbers higher to the right•Repeat on the smaller arrays until only 1 element remains•Speed: O(NlogN) (average)Pivot = 2 2 1 3 41 2 3 4Pivot = 7 6 8 5 71 2 3 426 8 2 4 5 7 1 3Pivot = 4 6 8 2 4 5 7 1 32 1 3 4 6 8 5 71 3 46 5 7 86578Pivot = 66 5 75 6•The fastest any comparison based sort can sort a list is O(NlogN)•The longest any comparison based sort should take is O(N²)•Selection Sort – O(N²)•Insertion Sort – O(N²)•Bubble Sort – O(N²)•Shell Sort – O(N^(7/6))•Bucket Sort – O(N) - depends•Radix Sort – O(N) - depends•Quick Sort – O(NlogN) - averageWorks Cited•Dewdney, A. The New Turing Omnibus. New York: Computer Science Press, 1989.•Douglass, Ben. Computer Science 2. UCF, 2006.•Weiss, Mark. Data Structures and Problem Solving Using Java. Boston: Pearson Education, Inc,
View Full Document
Unlocking...