Consider the array
Review the steps in the above code for this array segment with k-1 = 7 and with item having the value 17. Explain what happens and why.
| CSC 207 | Grinnell College | Fall, 2018 |
| Algorithms and Object-Oriented Design | ||
This laboratory exercises provides some practice with the insertion sort, quicksort, and merge sort and outlines a mechanism for determining experimentally the efficiency of these sorting algorithms.
Many applications require the maintenance of ordered data. In Java (and Scheme and C), such data often are structured in an array (or vector). The reading for this lab provides considerable detail on both the insertion sort and quicksort. You should read that material before proceeding further in this lab.
As with other labs, please submit your work for this lab on Github Classroom, using the URL link, https://classroom.github.com/g/f6wSxS49. Material submitted should contain three files, each clearly labeled:
The insertion sort 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.
A main helper method adds add one item to an ordered array segment. More specifically, 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;
Consider the array
Review the steps in the above code for this array segment with k-1 = 7 and with item having the value 17. Explain what happens and why.
Using this basic insertion step, an array A can be sorted iteratively. 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;
}
}
Write a few sentences explaining how this code works.
The Quicksort, originally devised by C. A. R. Hoare [Computing Journal, Volume 5 (1962), pages 10-15], proceeds by 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.
The reading for this lab identifies two main approaches for applying this divide-and-conquer approach to sorting. This lab reviews the two approaches quickly and then asks you to write the details for another variation (based on a modified pictoral loop invariant).
The first approach follows the approach you implemented in the Lab on Pictoral Loop Invariants. In summary, sorting relied upon the function
int partition (int a[], int left, int right)
which, in turn, was based on the following loop invariant:
Incorporating partition into the quicksort function yields code, such as the following:
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);
}
As a review, write careful responses to the following statements:
Explain why each loop contains the condition right >= left. Given an example where the code would fail if each right >= left test were omitted.
The code swaps a[left] and a[right] only if right > left. Give an example to show how the code could fail if the swap were done without the test for right > left.
This code illustrates the husk-and-kernel programming style which arose frequently earlier in CSC 151.
Write a few sentences explaining how this code works. What does the husk procedure do? Why is the husk needed?
Program SortShell2.java provides a shell for testing the quicksort. Program SortShell3.java is the same as SortShell2.java, except that a few lines have been added at the start of quicksortKernel.
Write a few sentences explaining what this new code accomplishes; what is the logical effect of this change? For future reference in this lab, we will call this new version of quicksort a refined quicksort.
The second implementation of the quicksort is motivated by the following pictorial loop invariant.
This loop invariant motivates the following code to implement the basic step of the quicksort:
// progress through array,
// moving small elements to a[first+1] .. a[left-1]
// and moving large elements 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;
Review the code segment and explain why the "then" and "else" clauses of the if statement in the loop maintain the loop invariant.
Explain why the swap at the end of the code swaps a[first] with a[left-1] rather than with a[left].
The full code for this version of quicksort may be found in program SortShell4.java. Explain why the recursive calls involve left-2 and left.
As noted, program SortShell4.java provides a shell for testing this alternative quicksort. Run it with several sets of test data.
The third implementation of the quicksort is motivated by the following pictorial loop invariant.
Wrote a quicksort algorithm (following a husk and kernel) approach using this new loop invariant.
Modify SortShell2.java to allow testing for this revised quicksort. Then describe the results of testing, and discuss how the testing might demonstrate that this variant of a quicksort works properly.
The merge sort is motivated by the observation that merging two sorted arrays (or array segments) into another is reasonably straight forward:
In practice, some care is needed in coding, so that one copies just the relevant array segments and one does not go beyond the bounds of either initial array segment.
With this notion of merging, a merge sort proceeds as follows:
In this process, one needs to copy elements in one array into a second array. Since copying the array elements back to the original array takes time, the idea is to first merge from one array to a second, and then to merge from the second to the first. At the end, the sorted items will be in one of the two arrays, and some carefully bookkeeping can determine whether one copy is needed at the end to move data to the original array.
As already indicated, entire process depends upon merging two adjacent (and ordered) array segments into the corresponding place in a second array. In practice, this suggests the following method header:
/**
* 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
* valid part of aInit[start1] is copied
*/
private static void merge (int aInit [ ], int aRes [ ],
int start1, int start2, int end2)
Here, the ordered array segment aInit[start1]..aInit[start2-1] is merged with the following ordered array segment aInit[start2]..aInit[end2]
With this method implemented, the main merge sort algorithm becomes:
/**
* 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;
}
//copy result into initArr, as needed
if (needCopyBack)
{
for (int i = 0; i < initArr.length; i++)
initArr [i] = a0 [i];
}
}
Implement the merge method, as described.
Annotate the code for the mergeSort method, explaining in some detail what each line (or small collection of lines) accomplishes.
The insertion sort, quicksort, refined quicksort, and merge sort each yield their own analyses of efficiency.
For each algorithm, identify circumstances under which the best case and the worst case analyses could occur. What is the order of each sorting algorithm in the best case and in the worst case? (While class discussion may help answer this question for the insertion sort, and the discussion provides an answer for the quicksort, you still need to tabulate those answers, and you will need to formulatae the answer for the refined quicksort and merge sort.)
Program SortShell5.java combines the code for the insertion sort, quicksort, refined quicksort, and merge sort into a single testing shell, although the merge sort is incomplete (the merge method is not implemented). Copy this program to your account.
Insert your merge method, so that the program is complete. Review the program to determine how it works, and run it to observe its output.
if (size > 30000)
System.out.print(" ---")
else {
/* time the quicksort algorithm */
}
What happens if this code is replaced by the usual code for testing the algorithm (i.e., the code with the if removed)?
Why do you think this result might occur?
In reviewing the various timings of algorithms, what algorithm(s) do you think should be used in various contexts (e.g., for ascending data, for random data, and for descending data). Explain your conclusions.
|
created 24 April 2001 revised 28 April 2006 revised 11-13 March 2012 revised 2-3 November 2018 |
|
| For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. |