| CSC 161.01 | Grinnell College | Fall, 2019 |
 |
CSC 161.01
Imperative Problem Solving with Lab |
 |
| CSC 161.01 | Grinnell College | Fall, 2019 |
|
CSC 161.01
Imperative Problem Solving with Lab |
|
This laboratory exercises introduces and analyzes the insertion sort, quicksort, and merge sort as mechanisms to order numbers in an array.
Many applications require the maintenance of ordered data. In Java (and both C and Scheme), a simple way to structure ordered data is in an array (or vector), such as the following ordered array A of integers:
One common sorting approach is based on code that assumes that the first part of an array is ordered and then adds successive items to this array segment until the entire array is sorted. To understand this approach, we first consider how to add one item to an ordered array segment. We then apply this work to each array element in turn to yield an ordered array.
Suppose items a[0], ..., a[k-1] are ordered in array a:
The following code inserts an item into the array, so that items a[0], ..., a[k] become ordered:
int i = k-1;
while ((i >= 0) && a[i] > item){
a[i+1] = a[i];
i--;
}
a[i+1] = item;
Using this basic insertion step, an array a can be sorted iteratively according to the following outline:
This outline gives rise the the following code, called an insertion sort.
public static void insertionSort (int [] a) {
// method to sort using the insertion sort
for (int k = 1; k < a.length; k++) {
int item = a[k];
int i = k-1;
while ((i >= 0) && a[i] > item){
a[i+1] = a[i];
i--;
}
a[i+1] = item;
}
}
Initial Notes:
The quicksort was originally devised by C. A. R. Hoare. For more details, see the Computing Journal, Volume 5 (1962), pages 10-15.
The basic approach involves applying an initial step that partitions the array into two pieces. The algorithm then is applied recursively to each of the two pieces. This approach of dividing processing into pieces and applying recursion to the two pieces turns out to be extremely general and powerful. Such an approach is called a divide and conquer algorithm.
Much of the following discussion is based on the presentation in Henry M. Walker, Pascal: Problem Solving and Structured Program Design, Little, Brown, and Company, 1987, pages 500-506, and is used with permission of the copyright holder.
The alternative loop invariant discussed below is based on Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivset, and Clifford Stein, Introduction to Algorithms, Third Edition The MIT Press, 2009, pages170-185.
The quicksort is a recursive approach to sorting, and we begin by outlining the principal recursive step. In this step, we make a guess at the value that should end up in the middle of the array. In particular, given the array a[0], ..., a[N-1] of data, arranged at random, then we might guess that the first data item a[0] often should end up in about the middle of the array when the array is finally ordered. (a[0] is easy to locate, and it is as good a guess at the median value as another.) This suggests the following steps:
A specific example is shown below:
With the above outline, we now consider how to move the first array element into its appropriate location in the array. There are two basic approaches, based on two different loop invariants:
Approach 1:
In this approach, the idea is to maintain small elements at the start of the array, just after a[first] and to maintain large elements at the end of the array. Elements that have yet to be examined are in the middle. As processing proceeds, the middle section gets successively smaller, until all elements have been put into the correct section.
Approach 2:
In this approach, the idea is to maintain small elements and then large elements toward the start of the array. The right of the array contains elements that are yet to be examined. As processing proceeds, the right section shrinks until all items are in their appropriate section.
The basic approach is to work from the ends of the array toward the middle, comparing data elements to the first element and rearranging the array as necessary. This idea is encapsulated in the following diagram:, which is repeated from above.
To implement this approach, we move left and right toward the middle — maintaining the loop invariant with each step.. The details follow:
These steps are illustrated in the following diagram:
The following code implements this basic step:
int left=first+1;
int right=last;
int temp;
while (right >= left) {
// search left to find small array item
while ((right >= left) && (a[first] <= a[right]))
right--;
// search right to find large array item
while ((right >= left) && (a[first] >= a[left]))
left++;
// swap large left item and small right item, if needed
if (right > left) {
temp = a[left];
a[left] = a[right];
a[right] = temp;
}
}
// put a[first] in its place
temp = a[first];
a[first] = a[right];
a[right] = temp;
Given the above code to place the first element of an array segment appropriately and rearrange small and large items, the full array may be sorted by applying the algorithm recursively to the first part and the last part of the array. The base case of the recursion arises if there are no further elements in an array segment to sort.
This gives rise the the following code, called a quicksort.
public static void quicksort (int [] a) {
// method to sort using the quicksort
quicksortKernel (a, 0, a.length-1);
}
private static void quicksortKernel (int [] a, int first, int last) {
int left=first+1;
int right=last;
int temp;
while (right >= left) {
// search left to find small array item
while ((right >= left) && (a[first] <= a[right]))
right--;
// search right to find large array item
while ((right >= left) && (a[first] >= a[left]))
left++;
// swap large left item and small right item, if needed
if (right > left) {
temp = a[left];
a[left] = a[right];
a[right] = temp;
}
}
// put a[first] in its place
temp = a[first];
a[first] = a[right];
a[right] = temp;
// recursively apply algorithm to a[first]..a[right-1]
// and a[right+1]..a[last], provided these segments contain >= 2 items
if (first < right-1)
quicksortKernel (a, first, right-1);
if (right+1 < last)
quicksortKernel (a, right+1, last);
}
This code illustrates the husk-and-kernel programming style which arose frequently earlier in CSC 151.
In this approach, we compare successive items in the array to a[first].
Examining this picture in more detail, at the start, there are no examined items, so there are no items that we know are <= a[first] and also no items that we know are > a[first], as shown in the following diagram:
This picture suggests the following initialization:
left = first + 1; right = first + 1;
Once processing has begun, we examine the unprocessed element a[right].
Processing continues until all items are processed, as shown in the following diagram:
Based on this outline, the entire code for placing a[first] in its correct position is:
// progress through array,
// moving small elements to a[first+1] .. a[left-1]
// and moving large lements to a[left] .. a[right-1]
while (right <= last)
{
if (a[first] < a[right])
right++;
else {
// swap a[left] and a[right]
temp = a[right];
a[right] = a[left];
a[left] = temp;
left++;
right++;
}
}
// put a[first] in its place
temp = a[first];
a[first] = a[left-1];
a[left-1] = temp;
This code fits into the overall framework quicksort procedure in much the same way as the code following approach 1 with its loop invariant (although you need to adjust the recursive calls to reflect the new loop invariant).
The quicksort is called a divide-and-conquer algorithm, because the first step normally divides the array into two pieces and the approach is applied recursively to each piece.
Suppose this code is applied an array containing n randomly ordered data. For the most part, we might expect that the quicksort's divide-and-conquer strategy will divide the array into two pieces, each of size n/2, after the first main step. Applying the algorithm to each half, in turn, will divide the array further -- roughly 4 pieces, each of size n/4. Continuing a third time, we would expect to get about 8 pieces, each of size n/8.
Applying this process i times, would would expect to get about 2i pieces, each of size n/2i.
This process continues until each array piece just has 1 element in it, so 1 = n/2i or 2i = n or i = log2 n. Thus, the total number of main steps for this algorithms should be about log2 n. For each main step, we must examine the various array elements to move the relevant first items of each array segment into their correct places, and this requires us to examine roughly n items.
Altogether, for random data, this suggests that the quicksort requires about log2 n main steps with n operations per main step. Combining these results, quicksort on random data has O(n log2 n).
A basic quicksort algorithm typically chooses the first or last element in an array segment as the point of reference for subsequent comparisons. (This array element is often called the pivot.) This choice works well when the array contains random datam and the work for this algorithm has O(n log n) with random data.
However, when the data in the array initially are in ascending order or descending order, the analysis of efficiency breaks down, and the quicksort has O(n2). (The analysis is much the same as insertion sort for data in descending order.)
To resolve this difficulty, it is common to select an element in the array segment at random to be the pivot. The first part of the quicksort algorithm then follows the following outline:
private static void quicksortKernet (int[] a, int first, int last)
{
pick an array element a[first], ..., a[last] at random
swap the selected array element with a[first]
continue with the quicksort algorithm as described earlier
...
}
With this adjustment, quicksort typically performs equally well (O(n log n)) for all types of data.
The following sorting algorithm is called a merge sort, because it is based on a simple procedure that combines or merges two short lists of ordered data into one large, ordered list. With this procedure, the merge sort proceeds from small initial array segments to large ones:
Consider an entire array as a sequence of 1-element array segments, each of which is ordered.
Merge segment 1 with segment 2, segment 3 with segment 4, segment 5 with segment 6, etc. to obtain 2-element array segments, each of which is ordered.
With ordered array segments of size 2, merge segment 1 with segment 2, segment 3 with segment 4, segment 5 with segment 6, etc. to obtain 4-element array segments, each of which is ordered.
With ordered array segments of size 4, merge segment 1 with segment 2, segment 3 with segment 4, segment 5 with segment 6, etc. to obtain 8-element array segments, each of which is ordered.
Continue merging to obtain ordered array segments of size 16, 32, 64, ... .
Stop when the ordered array segment contains the entire array.
To clarify, this process is illustrated in the following diagram:
As this process indicates, for each step, the merge sort considers an array to be a collection of small, ordered segments, and two adjacent segments can be merged to yield a larger, ordered array segment.
In practice, this merging process is subject to several details:
To merge two adjacent array segments, one must know where the first begins (perhaps given by a variable start1), where the second begins (perhaps given by a variable start2), and where the second segment ends (perhaps given by a variable end2). There is no need to keep track of the end of the first segment, as that will always be just before start2
At each stage of processing, a variable (perhaps called mergeSize) keeps track of the current size of the ordered array. Initially, this variable is set to size 1. Thereafter, the variable is doubled with each full iteration.
Starting with one array, merging requires the existence of a second array. In the first step, data are moved from the initial array to the second. However, with all of the data now moved to the second array, the second step may move data from the second array back to the original array. (No need to keep allocating space for new arrays!) Thereafter each merging step can process from one array to the other, followed by merging back.
To keep track of the two arrays, two temporary array variables (perhaps called a0 and a1) may reference the two arrays. Then after each merge step, the arrays designated by these variables may be swapped, so a0 always points to the most recently merged array, and a1 will designate which array will receive the next merge step.
At the end of all merging steps, the fully sorted data will be in one of the two arrays, but some bookkeeping may be needed to determine which array has the sorted data set. If the fully sorted data is not in the original array, then a copy may be needed back to that array.
The following method puts these elements together, assuming the merge method has already been implemented.
/**
* sort the array a, using a merge sort
*/
public static void mergeSort (int initArr [ ]) {
int resArr [ ] = new int [initArr.length];
int a0[ ] = initArr;
int a1[ ] = resArr;
boolean needCopyBack = false;
int mergeSize = 1;
int start1;
while (mergeSize < initArr.length)
{
int end2;
for (start1 = 0; start1 < initArr.length; start1 = end2) {
int start2 = start1 + mergeSize;
end2 = start2 + mergeSize;
merge (a0, a1, start1, start2, end2);
}
// swap a0, a1 pointers, so a0 is starting array for next merge
int temp [ ] = a0;
a0 = a1;
a1 = temp;
mergeSize *= 2;
// keep track of which array holds initArr object
needCopyBack = !needCopyBack;
//print intermediate result, if desired
for (int i = 0; i < a0.length; i++)
System.out.printf ("%5d", a0[i]);
System.out.print ("\n\n");
}
//copy result into initArr, as needed
if (needCopyBack)
{
for (int i = 0; i < initArr.length; i++)
initArr [i] = a0 [i];
}
}
With this main step completed, the remaining work involves merging two sorted array segments. The outline for this merge follows:
As long as items exist in both array segments:
Copy any remaining elements from the first array segment to the new array.
Copy any remaining elements from the second array segment to the new array.
Consistent with the merge sort code above, an appropriate header for this merge method might be:
/**
* merge aInit[start1]..aInit[start1+mergeSize] with
* aInit[start2]..Init[end2]
* with the result placed in aRes
* Note: it may be that start2 >= aInit.length, in which case, only the
* valide part of aInit[start1] is copied
*/
private static void merge (int aInit [ ], int aRes [ ],
int start1, int start2, int end2)
|
created 24 April 2001 revised 11 March 2005 revised 9-13 March 2012 revised 3 November 2018 |
|
| For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. |