DStruct Sorting.ppt

Sorting 1  Chapter Objectives Describe the three kinds of sorting methods ◦ Selection, exchange, and insertion Look at examples of each kind of sort that are O(n2) sorts ◦ Simple selection, bubble, and insertion sorts Study heaps, show how used for efficient selection sort, heapsort ◦...

Sorting 1  Chapter Objectives Describe the three kinds of sorting methods ◦ Selection, exchange, and insertion Look at examples of each kind of sort that are O(n2) sorts ◦ Simple selection, bubble, and insertion sorts Study heaps, show how used for efficient selection sort, heapsort ◦ Look at implementation of priority queues using heaps Study quicksort in detail as example of divide-and-conquer strategy for efficient exchange sort Study mergesort as example of sort usable with for sequential files Look at radix sort as example of non-comparison-based sort 2 Sorting Consider list x1, x2, x3, … xn We seek to arrange the elements of the list in order ◦ Ascending or descending Some O(n2) schemes ◦ easy to understand and implement ◦ inefficient for large data sets 3 Categories of Sorting Algorithms Selection sort ◦ Make passes through a list ◦ On each pass reposition correctly some element The algorithm works as follows: 1.Find the minimum value in the list 2.Swap it with the value in the first position 3.Repeat the steps above for the remainder of the list (starting at the second position and advancing each time) 4 Selection Sort int i, j, minIndex, tmp; for (i = 0; i < n - 1; i++) { minIndex = i; for (j = i + 1; j < n; j++) if (arr[j] < arr[minIndex]) minIndex = j; if (minIndex != i) { tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } } 5 Categories of Sorting Algorithms Exchange sort ◦ Systematically interchange pairs of elements which are out of order ◦ Bubble sort does this Out of order, exchange In order, do not exchange 6 Bubble Sort Algorithm 1. Initialize numCompares to n - 1 2. While numCompares != 0, do following a. Set last = 1 // location of last element in a swap b. For i = 1 to numCompares if xi > xi + 1 Swap xi and xi + 1 and set last = i c. Set numCompares = last – 1 End while 7 Bubble Sort for(r=0;r= data in children 13 Figure 9-1 HEAP STRUCTURE Figure 9-2 Figure 9-3 BASIC HEAP ALGORITHMS ReheapUp The reheapUp operation repairs a “broken” heap by floating the last element up the tree until it is in its correct location in the heap. Figure 9-4 Figure 9-5 ReheapDown The reheapDown operation repairs a “broken” heap by pushing the root down the tree until it is in its correct location in the heap. Figure 9-6 Figure 9-7 HEAP DATA STRUCTURE 1. For a node located at index i, its children are found at 1. Left child : 2i + 1 2. Right child: 2i + 2 2. The parent of a node located at index i is located at [(i - 1)/2]. 3. Given the index of a left child, j, its right sibling if any, is found at j + 1. Conversely, given the index for a right child, k, its left sibling, which must exist, is found at k - 1. 4. Given the size, n , of a complete heap, the location of the first leaf is [(n/2)]. Given the first leaf element, the location of the last nonleaf element is 1 less. Figure 9-8 BuildHeap 1 walker =1 2 loop(walker pivot} Return the list rearranged as: Quicksort(SmallerThanPivot), pivot, Quicksort(LargerThanPivot). 40 Quicksort Note visual example of a quicksort on an array etc. … 41 Quicksort Performance O(nlog2n) is the average case computing time ◦ If the pivot results in sublists of approximately the same size. O(n2) worst-case ◦ List already ordered, elements in reverse ◦ When Split() repetitively results, for example, in one empty sublist 42 Improvements to Quicksort Quicksort is a recursive function ◦ stack of activation records must be maintained by system to manage recursion. ◦ The deeper the recursion is, the larger this stack will become. The depth of the recursion and the corresponding overhead can be reduced ◦ sort the smaller sublist at each stage first 43 Improvements to Quicksort Another improvement aimed at reducing the overhead of recursion is to use an iterative version of Quicksort() To do so, use a stack to store the first and last positions of the sublists sorted "recursively". 44 Improvements to Quicksort An arbitrary pivot gives a poor partition for nearly sorted lists (or lists in reverse) Virtually all the elements go into either SmallerThanPivot or LargerThanPivot ◦ all through the recursive calls. Quicksort takes quadratic time to do essentially nothing at all. 45 Improvements to Quicksort Better method for selecting the pivot is the median-of-three rule, ◦Select the median of the first, middle, and last elements in each sublist as the pivot. Often the list to be sorted is already partially ordered Median-of-three rule will select a pivot closer to the middle of the sublist than will the “first-element” rule. 46 Improvements to Quicksort For small files (n