COP 3540 Data Structures with OOPAdvanced SortingRecall how the Insertion Sort worked.Approach that helped us:Potential Problems with the Insertion SortShell Sort ApproachShell Sort uses the notion of a ‘computed Gap’ExampleConsider Improved Performance!What about Larger Arrays? Gap Size?PowerPoint PresentationAlgorithm (covered in previous slide)Note:Slide 14Google: Shell Sort AppletDemo of Shell SortShell Sort - EvaluationFinal Remarks on Shell SortPartitioningSlide 20Pivot ValuesRun Partition Algorithm to build Sub-ArraysThe Partitioning AlgorithmPartition.htmlPartitioning and the Pivot ValueOne (of several) Problems with PartitioningEfficiency of the PartitionEfficiency of the Partitioning Algorithm1/28COP 3540 Data Structures with OOP Chapter 7 - Part 1Advanced Sorting2/28Advanced SortingTwo sorts we will cover first.Shell Sort – an O(n(log2 n) 2) sort … in general, and ‘can approach’ O(n) performance!Partitioning, an O(nlog2n) sort.Then, we’ll cover the QuickSort.3/28Recall how the Insertion Sort worked.Took an element out of the ‘array’ and assumed all elements ‘to the left’ were sorted.We marked this spot.And we extracted out that element.We then compared the element extracted out with the elements ‘to the left’ of this element and ‘inserted’ this element into its proper place shifting all elements to the right as needed to make room for this inserted element and fill the vacated spot.4/28Approach that helped us:Constraints:Helped ourselves by:•starting with a single element to the left – so knew ‘that’ element was sorted - certainly sorted unto itself.Then we proceeded:•Slowly the elements to the ‘left’ of the marked element grew in sorted number, as new numbers find their proper place in the subarray to the left - while the unsorted elements to the right diminish in number.5/28Potential Problems with the Insertion Sort Now, what happens if the new number to be sorted is very small (or very large) and our sort is ‘ascending (or descending)?’This may require a large number of ‘copies’ to the right to make room for this new element.Can require a number of ‘copies’ close to ‘n’ in fact.Average number of copies is clearly n/2.For n elements to be sorted and an average of n/2 copies per element, we have n*n/2 or n2/2 copies.That may result in a very inefficient sort. This is how the insertion sort is an O(n2) sort.It is this number of copies (comparing and shifting) that decreases its performance.6/28Shell Sort ApproachWant to reduce these numbers of large shifts Shell sort does this by sorting a very small subset of numbers – like three or four: Where the numbers themselves might be large distances apart (like in a large array)and it sorts them with respect to each otherBy sorting a small number of numbers, very small (or very large) numbers can be put much more nearly ‘in place’ much more quickly than with other approaches. How done?7/28Shell Sort uses the notion of a ‘computed Gap’The Shell Sort uses a computed ‘gap’ between numbers represented by an ‘h’ as the distance between numbers in each subset to be sorted. 1. Sorts all numbers (say in the array of numbers) with the same ‘h’ (gap)•Like, numbers eight apart – or four apart…•Sorts these numbers with respect to each other.2. Then, after doing this, the algorithm reduces the gap (or distance) to a smaller number, like maybe 4 apart.3. (Ultimately the gap has size = 1;) Then the algorithm ‘1-sorts’ the array using the insertion sort.8/28ExampleConsider: sort three elements at a time with respect to each other, where the numbers are some ‘h’ distance apart…………………………………………………….For array size n=10, and if gap size h = 4, we have four sub-arrays: (We call this a 4-sort)Indices: (0,4,8), (1,5,9), (2,6) and (3,7). These sets are sorted with respect to each other.(Note: all ten are sorted!)Arrays are interleaved, but, again, sorted with respect to each other.  (Note: the integers are not yet in final spot.9/28Consider Improved Performance!Recall again the Insertion SortRecalling how the insertion sort works,very efficient for arrays nearly sorted (fewer swaps and movement, and yet can bevery inefficient (due to shifts and copies) if the data are very unsorted.•Particularly true for very large / very small numbers.Shell sort does ‘n-sorting’ Capitalizes on initial position of elements especially if they are far from where they might ultimately end up. Brings numbers more quickly to final position…(or nearer)Algorithm moves elements that may be very far apart much closer to their final position more quickly thus reducing copying and shifting and swapping!Shell Sort can approach O(n) performance: much better than O(n2) !10/28What about Larger Arrays? Gap Size?Using a carefully researched algorithm to compute optimum gap size,.Don Knuth developed a ‘recursive’ relationship: h= 3*h+1 to start with, and then, subsequent gaps at (h-1)/3. (note the ‘recursion’ in the formula itself. Uses value of h to compute new value of h. These h-values are referred to as interval sequence or gap sequence and are recursively computed as functions of h.In more detail:11/28Don Knuth’s algorithm will start with a 3-sort; that is, sort three numbers some distance apart.By Don Knuth’s research reveals, as it turns out (algorithm is a few slides ahead), for an array of size > 364 and < 1093, 3-sort with a gap size of 364; After that sort, use a gap size of 121; then gap size = 40; steadily decreasing… Develop initial gap size recursively by computing h: (algorithm is three slides ahead)h 3*h+1 h is determined by computing the largest value of h 1 4 computing h=h*3 +1 until h <= nElems/3 is false 4 13 13 40 So, computing h we see that h increases from 1 to 4 to 13 to 121 to 364 to …. 40 121 121 364 Once original gap is determined, sort continues and algorithm steadily reduces gap h from 364 to 121 .. 364 1093 until h = 1 1093 3280 So for array size > 364 and < 1093, gap = 364, etc. Gapsizes12/28Algorithm