CMSC 202 Lecture Notes: Sorting Routines

These lecture notes present three different sorting routines: Selection Sort, Merge Sort, and Quicksort. Each of these routines takes three arguments: an array of items to sort; the low and high indices in the array between which lie the elements we wish to sort. We will sort arrays of integers, but the reader should note that these algorithms can be used to sort floating point numbers, rationals, fractions, etc. We define the types data and index which we will use to index the array. This is to avoid the confusion between integers in the array and integers used to index the array.

typedef int data ; typedef int index ;

Selection Sort

The Selection Sort algorithm works by repeatedly finding the next item in the sequence and putting that item in its proper place. This is easily accomplished by a pair of nested loops. The inner for loop finds the index of the smallest element of the subarray A[i...high].

void selection_sort(data A[], index low, index high) { index i, j, min ; data temp ; for (i = low ; i < high ; i++) { min = i ; for (j = i+1 ; j <= high ; j++) { if (A[j] < A[min]) min = j ; } temp = A[min] ; A[min] = A[i] ; A[i] = temp ; } }

Merge Sort

Merge Sort relies on the merge function to merge together two sorted arrays. Merge Sort gets its efficiency from the fact that at most one comparison is needed for each item being merged. Think about merging two decks of cards, A and B, into a third deck C. Decks A and B are assumed to each be already in sorted order. Deck C stars out empty. You compare the top cards from each deck and place the smaller of the two, face down, on the merged deck. When either deck A or deck B becomes empty, you place the entire remaining deck, face down, onto deck C. The key here is that the two decks, A and B are sorted to begin with. At most one comparison is made for each card merged. When one of the decks becomes empty, no further comparisons are done and the entire remaining deck is merged in at once. This is the basis for the following merge algorithm. In this algorithm, the "cards" are stored in an array. Deck A is stored in indices low1..high1, inclusive. Deck B is stored in indices low2..high2. We further stipulate that the two "decks" are contiguous in the array (the last card of deck A comes just before the first card of deck B). The mergesort algorithm uses the merge algorithm (below) to sort the entire array. To sort the whole array A, low would be zero and high would be the maximum index in the array.

void mergesort(data A[], index low, index high) { index mid ; if (low >= high) return ; mid = (low + high)/2 ; mergesort(A, low, mid) ; mergesort(A, mid + 1, high) ; merge(A, low, mid, mid + 1, high) ; }

Merge Sort breaks the array down into smaller and smaller pieces until the individual pieces are just one item in size. Since a single item is already sorted, we can merge two contiguous items. The Merge Sort algorithm therefore breaks the array down into smaller chunks on the way down the recursion tree. On the way back up, it merges these smaller pieces of the array into larger pieces. One could say that the sorting is done on the way back up the tree.

/* Global variable temp must be allocated the same amount of space as the array to be sorted */ data *temp ; void merge(data A[], index low1, index high1, index low2, index high2) { index t, i1, i2 ; /* Sanity check */ assert(low2 == high1 + 1) ; /* while there are elements in both halves, copy the lowest one */ i1 = low1 ; i2 = low2 ; t = 0 ; while (i1 <= high1 && i2 <= high2) { if (A[i1] < A[i2]) { temp[t] = A[i1] ; i1++ ; t++ ; } else { temp[t] = A[i2] ; i2++ ; t++ ; } } /* copy any remaining elements */ while (i1 <= high1) { temp[t] = A[i1] ; t++ ; i1++ ; } while (i2 <= high2) { temp[t++] = A[i2++] ; } /* copy the now-sorted elements back into the original array */ for (t = low1; t <= high2; t++) { A[t] = temp[t - low1] ; } }

Quicksort

Just as in Merge Sort, Quicksort splits the array into two pieces. However, Quicksort takes the additional step of placing all the low values in the left piece and all the high values in the right piece. Consequently, no merge step is needed after the two halves have been sorted. The partition() function (below) is responsible for dividing the array into two pieces. void quicksort(data A[], index low, index high) { index q ; if (low >= high) return ; q = partition(A, low, high) ; assert(q < high) ; quicksort(A, low, q) ; quicksort(A, q + 1, high) ; }

In Quicksort, the partitioning is done on the way down the recursion tree. One could say that the sorting is done on the way down. The partition() function places all the elements smaller than the first element in the first part of the array and all the elements larger than the first element in the second part. The partition() function starts an index at each end of the array and moves them inward. Whenever two values that are in the wrong halves are found, they are swapped. When the two indices meet, the partitioning is complete.

index partition(data A[], index low, index high) { data x, temp ; index i, j ; i = low - 1; j = high + 1; x = A[low] ; while (1) { /* Find an element less than x */ do { j = j - 1; } while (A[j] > x) ; /* Find an element greater than x */ do { i = i + 1; } while (A[i] < x); if (i < j) { temp = A[j] ; A[j] = A[i] ; A[i] = temp ; } else { return j; } } }

Thomas A. Anastasio, Thu Nov 13 16:32:43 EST 1997

Much modified by Richard Chang Fri Feb 06 16:02:42 EST 1998.