New version page

GSU CSC 2320 - CSCI2320 Sorting

This preview shows page 1-2-3-23-24-25-26-47-48-49 out of 49 pages.

View Full Document
View Full Document

End of preview. Want to read all 49 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

SortingInsertion Sort IInsertion Sort IIInsertion Sort: CodeInsertion Sort: AnalysisOptimality Analysis IOther AssumptionsShell SortSorting nonconsecutive subarraysDoing the 1-sortExample of shell sortDiminishing gapsSlide 13Increment sequenceSlide 15Slide 16Merge SortMergingSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Merging numerical exampleBinary Merge SortSlide 31Slide 32Slide 33QuicksortSlide 35Slide 36Slide 37Quicksort ExampleSlide 39Quicksort SplitSlide 41Quicksort PerformanceImprovements to QuicksortCounting SortSlide 45Slide 46Slide 47Radix SortSlide 49SortingDr. Bernard Chen Ph.D.University of Central ArkansasFall 2010Insertion Sort IThe list is assumed to be broken into a sorted portion and an unsorted portionKeys will be inserted from the unsorted portion into the sorted portion.SortedUnsortedInsertion Sort IIFor each new key, search backward through sorted keysMove keys until proper position is foundPlace key in proper positionMovedInsertion Sort: Codetemplate <class Comparable> void insertionSort( vector<Comparable> & a ) { for( int p = 1; p < a.size( ); p++ ) { Comparable tmp = a[ p ]; int j; for( j = p; j > 0 && tmp < a[ j - 1 ]; j-- ) a[ j ] = a[ j - 1 ]; a[ j ] = tmp; } } Fixed n-1 iterationsWorst case i-1 comparisonsMove current key to rightInsert the new key to its proper positionSearching for the proper position for the new keyMovedInsertion Sort: AnalysisWorst Case: Keys are in reverse orderDo i-1 comparisons for each new key, where i runs from 2 to n.Total Comparisons: 1+2+3+ … + n-1 in nnin11212( )ComparisonOptimality Analysis ITo discover an optimal algorithm we need to find an upper and lower asymptotic bound for a problem.An algorithm gives us an upper bound. The worst case for sorting cannot exceed (n2) because we have Insertion Sort that runs that fast.Lower bounds require mathematical arguments.Other AssumptionsThe only operation used for sorting the list is swapping two keys.Only adjacent keys can be swapped.This is true for Insertion Sort and Bubble Sort.Shell SortWith insertion sort, each time we insert an element, other elements get nudged one step closer to where they ought to beWhat if we could move elements a much longer distance each time?We could move each element:A long distanceA somewhat shorter distanceA shorter distance stillThis approach is what makes shellsort so much faster than insertion sortSorting nonconsecutive subarraysConsider just the red locationsSuppose we do an insertion sort on just these numbers, as if they were the only ones in the array?Now consider just the yellow locationsWe do an insertion sort on just these numbersNow do the same for each additional group of numbersThe resultant array is sorted within groups, but not overall• Here is an array to be sorted (numbers aren’t important)Doing the 1-sortIn the previous slide, we compared numbers that were spaced every 5 locationsThis is a 5-sortOrdinary insertion sort is just like this, only the numbers are spaced 1 apartWe can think of this as a 1-sortSuppose, after doing the 5-sort, we do a 1-sort?In general, we would expect that each insertion would involve moving fewer numbers out of the wayThe array would end up completely sortedExample of shell sortoriginal81 94 11 96 12 35 17 95 28 58 41 75 155-sort35 17 11 28 12 41 75 15 96 58 81 94 953-sort28 12 11 35 15 41 58 17 94 75 81 96 951-sort11 12 15 17 28 35 41 58 75 81 94 95 96Diminishing gapsFor a large array, we don’t want to do a 5-sort; we want to do an N-sort, where N depends on the size of the arrayN is called the gap size, or interval sizeDiminishing gapsWe may want to do several stages, reducing the gap size each timeFor example, on a 1000-element array, we may want to do a 364-sort, then a 121-sort, then a 40-sort, then a 13-sort, then a 4-sort, then a 1-sortWhy these numbers?Increment sequenceNo one knows the optimal sequence of diminishing gapsThis sequence is attributed to Donald E. Knuth:Start with h = 1Repeatedly compute h = 3*h + 11, 4, 13, 40, 121, 364, 1093This sequence seems to work very wellIncrement sequenceAnother increment sequence mentioned in the textbook is based on the following formula:start with h = the half of the container’s sizehi = floor (hi-1 / 2.2)It turns out that just cutting the array size in half each time does not work out as wellAnalysis What is the real running time of shellsort?Nobody knows!Experiments suggest something like O(n3/2) or O(n7/6)Analysis isn’t always easy!Merge SortIf List has only one Element, do nothingOtherwise, Split List in HalfRecursively Sort Both ListsMerge Sorted ListsMergesort(A, l, r) if l < r then q = floor((l+r)/2) mergesort(A, l, q) mergesort(A, q+1, r) merge(A, l, q, r)auxiliary arraysmallest smallestA G L O R H I M S T MergingMerge.Keep track of smallest element in each sorted half.Insert smallest of two elements into auxiliary array.Repeat until done.Aauxiliary arraysmallest smallestA G L O R H I M S TA GMergingMergingMerge.Merge.Keep track of smallest element in each sorted Keep track of smallest element in each sorted half.half.Insert smallest of two elements into auxiliary Insert smallest of two elements into auxiliary array.array.Repeat until done.Repeat until done.auxiliary arraysmallest smallestA G L O R H I M S TA G MergingMerge.Keep track of smallest element in each sorted half.Insert smallest of two elements into auxiliary array.Repeat until done.Hauxiliary arraysmallest smallestA G L O R H I M S TA G H MergingMerge.Keep track of smallest element in each sorted half.Insert smallest of two elements into auxiliary array.Repeat until done.Iauxiliary arraysmallest smallestA G L O R H I M S TA G H I MergingMerge.Keep track of smallest element in each sorted half.Insert smallest of two elements into auxiliary array.Repeat until done.Lauxiliary arraysmallest smallestA G L O R H I M S TA G H I L MergingMerge.Keep track of smallest element in each sorted half.Insert smallest of two elements into auxiliary array.Repeat until done.Mauxiliary arraysmallest smallestA G L O R H I M S TA G H I L M


View Full Document
Loading Unlocking...
Login

Join to view CSCI2320 Sorting and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CSCI2320 Sorting and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?