/*** Simple integer-based implementations of some popular* sorting algorithms. Used in conjunction with the sortinglab.** @author Jeremy Morris***/public class IntSort {/*** arrayToString* Turns an array of integers into a string. Useful forprinting and* debugging purposes.* * @param a array to be transformed* @param start index of first position to be displayed* @param end index of final position to be displayed* @return String containing array elements*/public static String arrayToString(int[] a, int start, intend) {String result=””;for (int i=start; i<end; i++) {result=result+a[i]+” “;//System.out.println(result);}if (start<=end)result=result+a[end];return result;}
/*** swap* Swaps the position of two elements of an array* in place* @param a array to be swapped* @param i position to swap from* @param j position to swap to*/public static void swap(int [] a, int i, int j) {int tmp = a[i];a[i] = a[j];a[j] = tmp;}
/*** selectionSort* Performs the selection sort algorithm over* an array in-place.** @param a array to be sorted*/public static void selectionSort(int [] a) {for (int i=0; i<a.length-1; i++) { // For each passSystem.out.println(“Starting pass: “+i);System.out.println(“Array at start:”+arrayToString(a,0,a.length-1));int minIndex = i;int compareCount=0;for (int j=i+1; j<a.length; j++) { // Traverse thelistif (a[j] < a[minIndex]) { // if list item smallerminIndex = j; // make it the minimum }}compareCount = compareCount +1;}System.out.println(“Swapping “+a[minIndex]+” for”+a[i]);System.out.println(“Made “+compareCount+” comparisons thispass”);System.out.println();swap(a,i,minIndex); // SWAP current and min.}}/*** insertionSort* Performs the insertion sort algorithm over* an array in-place* * @param a array to be sorted*/public static void insertionSort(int [] a) {for (int i=1; i<a.length; i++) { // For each passSystem.out.println(“Starting pass: “+(i-1));System.out.println(“Array at start:”+arrayToString(a,0,a.length-1));int insert = a[i];int scan = i;int compareCounts=0;System.out.println(“Scanning for where to insert”+insert);while (scan>0 && a[scan-1]>insert) {// Traverse the sorted side of the list to find the// insertion pointa[scan]=a[scan-1];scan=scan-1;compareCounts=compareCounts+1;}System.out.println(“Inserting “+insert+” into position”+scan);System.out.println(“Made “+(compareCounts+1)+” comparisonsthis pass”);System.out.println();a[scan]=insert; // insert the unsorted value}}/*** quickSort* A simple wrapper method for the quicksort code below.* Takes an array and calls the recursive quicksort code* appropriately. Used to give the same kind of methodcall* for quicksort that the non-recursive sorts have.* @param a*/public static void quickSort(int [] a) {quicksort(a,0,a.length-1);}/*** quicksort* Performs the quicksort algorithm over an* array in-place, using the recursive quicksort* algorithm* * @param a array to be sorted* @param start index of first position to be sorted* @param end index of last position to be sorted*/public static void quicksort(int [] a, int start, int end){if (start<end) { // general caseSystem.out.println(“Finding partitions for:”+arrayToString(a,start,end));int pivot = partition(a, start, end);System.out.println(“Partitioning around “+a[pivot]);System.out.println(“Partitioned array:”+arrayToString(a,start,end));
System.out.println(“Sorting left sublist:”+arrayToString(a,start,pivot-1));// sort left sublistquicksort(a,start,pivot-1);
System.out.println(“Sorting right sublist:”+arrayToString(a,pivot+1,end));// sort the right sublistquicksort(a,pivot+1,end);}}/*** partition* Helper method for quicksort. Used to find the* partition point and reorder the list so that items* less than the partition point are to its left anditems* greater than it are to its right* * @param a array to be partitioned* @param start index of first position to consider forpartition* @param end index of last position to consider forpartition* @return index of pivot element*/public static int partition(int [] a, int start, int end){
int pivot;int endOfLeft;int midIndex = (start+end)/2;
swap(a,start,midIndex);pivot=a[start];endOfLeft=start;int compareCount=0;for (int i=start+1; i<=end; i++) {if (a[i]<pivot) {endOfLeft=endOfLeft+1;swap(a,endOfLeft,i);}compareCount=compareCount+1;}System.out.println(“Performed “+compareCount+”comparisons”);swap(a,start,endOfLeft);return endOfLeft;}
/*** mergeSort* Performs the mergeSort algorithm to sort a list.* This method is a recursive implementation of mergesort* and is a non-destructive version (i.e. the original listremains* unsorted and a new, sorted list is returned)* * @param a array to be sorted* @param start initial position of sublist to sort* @param end final position of sublist to sort* @return sorted array*/public static int[] mergeSort(int [] a, int start, int end){
if (start<end) { // general caseint mid=(start+end)/2;int[] left = mergeSort(a,start,mid);int[] right = mergeSort(a,mid+1,end);return merge(left, right);}else {int[] arr = new int[1];arr[0] = a[end];return arr;}}
/*** merge* Given two sorted arrays left and right, returns a new* sorted array containing the elements of both left and* right.* * @param left sorted array to be merged* @param right sorted array to be merged* @return sorted array containing left and rightelements*/public static int[] merge(int [] left, int[] right) {int lIndex=0;int rIndex=0;int newIndex=0;int[] list = new int[left.length+right.length];while (lIndex<left.length &&rIndex<right.length) {if (left[lIndex]<=right[rIndex]) {list[newIndex]=left[lIndex];lIndex=lIndex+1;}else {list[newIndex]=right[rIndex];rIndex=rIndex+1;}newIndex=newIndex+1;}while (lIndex<left.length) {list[newIndex]=left[lIndex]; lIndex=lIndex+1;newIndex=newIndex+1;}while (rIndex<right.length) {list[newIndex]=right[rIndex]; rIndex=rIndex+1;newIndex=newIndex+1;}return list;}
public static void main(String[] args) {// Exercise 1 – selection sort codeint [] array = {7, 5, 3, 4, 9, 6};String arr = IntSort.arrayToString(array, 0,array.length-1);System.out.println(“Initial array: “+arr);IntSort.selectionSort(array);arr = IntSort.arrayToString(array, 0, array.length-1);System.out.println(“Sorted array: “+arr);
// // Exercise 2 – insertion sort code// int [] array = {7, 5, 3, 4, 9, 6};// String arr = IntSort.arrayToString(array, 0,array.length-1);// System.out.println(“Initial array: “+arr);// IntSort.insertionSort(array);// arr = IntSort.arrayToString(array, 0,array.length-1);// System.out.println(“Sorted array: “+arr);// // Exercise 3 – quick sort code// int [] array = {7, 5, 3, 4, 9, 6};// String arr = IntSort.arrayToString(array, 0,array.length-1);// System.out.println(“Initial array: “+arr);// IntSort.quickSort(array);// arr = IntSort.arrayToString(array, 0,array.length-1);// System.out.println(“Sorted array: “+arr);}
}
Examine the main method at the bottom of the IntSort.java file. Note that this code consists of 3 blocks of code where two of the blocks are commented out. For exercise 1 we will only use the first block of code (exercise 2 will use the second, and exercise 3 will use the third). Examine the code in this file and determine what it does. Trace through the code that it calls in IntSort,java and make sure you understand what it is doing. Then run the code and examine the output. Modify the code so that it performs selection sort on three different arrays and examine its behavior each time. The arrays that you should use are: (7,5, 3,4, 9, 6 (3, 4,5, 6, 7,9) (9, 7, 6, 5,4, 3) Note that the first array is already given to you – It is in the code for IntSort.java. Note also that the two additional arrays are special cases of the first- already sorted, and sorted in exactly reverse order. Extend the code so that it shows the results of sorting the other two arrays. You should place your modifications directly after the exercise 1 code block (so before the commented out exercise 2 code block) For each array, add up the number of comparisons made when sorting the array. Indicate in the comment block at the top of the IntSort.java code the total number of comparisons for each of the three arrays. Indicate which array the algorithm performed best for, and which array it performed the worst for. If performance was the same for all of the arrays, indicate that it performed the same. Exercise 2 Comment out the code in the main method for Exercise 1 and uncomment the code used for Exercise 2. Run this code and examine its output. Then modify the code so that it performs insertion sort on the same three arrays given above. You should place your modifications directly after the exercise 1 code block (so before the commented out exercise 3 code block) For each array, add up the number of comparisons made when sorting the array. Indicate in the comment block at the top of the IntSort.java code the total number of comparisons for each of the three arrays for this algorithm. Indicate which array the algorithm performed best for, and which array it performed the worst for. If performance was the same for all of the arrays, indicate that it performed the same. Is the behavior of this code substantially different from the behavior of the selection sort code? If so, explain in a few sentences in the comment block at the top of your code how it is different. Exercise 3 Comment out the code in the main method for Exercises 1 and 2 and uncomment the code used for Exercise 3. Run this code and examine its output. Then modify the code so that it performs quick sort on the same three arrays given above. You should place your modifications directly after the exercise 1 code block (so before the commented out exercise 3 code block) For each array, add up the number of comparisons made when sorting the array. Indicate in the comment block at the top of the IntSort.java code the total number of comparisons for each of the three arrays for this algorithm. Indicate which array the algorithm performed best for, and which array it performed the worst for. In this case I will guarantee you that one of these arrays will perform substantially worse with quicksort than the other two- for the one that performs the worst explain why it performs so poorly in your comment. Show transcribed image text Examine the main method at the bottom of the IntSort.java file. Note that this code consists of 3 blocks of code where two of the blocks are commented out. For exercise 1 we will only use the first block of code (exercise 2 will use the second, and exercise 3 will use the third). Examine the code in this file and determine what it does. Trace through the code that it calls in IntSort,java and make sure you understand what it is doing. Then run the code and examine the output. Modify the code so that it performs selection sort on three different arrays and examine its behavior each time. The arrays that you should use are: (7,5, 3,4, 9, 6 (3, 4,5, 6, 7,9) (9, 7, 6, 5,4, 3) Note that the first array is already given to you – It is in the code for IntSort.java. Note also that the two additional arrays are special cases of the first- already sorted, and sorted in exactly reverse order. Extend the code so that it shows the results of sorting the other two arrays. You should place your modifications directly after the exercise 1 code block (so before the commented out exercise 2 code block) For each array, add up the number of comparisons made when sorting the array. Indicate in the comment block at the top of the IntSort.java code the total number of comparisons for each of the three arrays. Indicate which array the algorithm performed best for, and which array it performed the worst for. If performance was the same for all of the arrays, indicate that it performed the same.
Exercise 2 Comment out the code in the main method for Exercise 1 and uncomment the code used for Exercise 2. Run this code and examine its output. Then modify the code so that it performs insertion sort on the same three arrays given above. You should place your modifications directly after the exercise 1 code block (so before the commented out exercise 3 code block) For each array, add up the number of comparisons made when sorting the array. Indicate in the comment block at the top of the IntSort.java code the total number of comparisons for each of the three arrays for this algorithm. Indicate which array the algorithm performed best for, and which array it performed the worst for. If performance was the same for all of the arrays, indicate that it performed the same. Is the behavior of this code substantially different from the behavior of the selection sort code? If so, explain in a few sentences in the comment block at the top of your code how it is different. Exercise 3 Comment out the code in the main method for Exercises 1 and 2 and uncomment the code used for Exercise 3. Run this code and examine its output. Then modify the code so that it performs quick sort on the same three arrays given above. You should place your modifications directly after the exercise 1 code block (so before the commented out exercise 3 code block) For each array, add up the number of comparisons made when sorting the array. Indicate in the comment block at the top of the IntSort.java code the total number of comparisons for each of the three arrays for this algorithm. Indicate which array the algorithm performed best for, and which array it performed the worst for. In this case I will guarantee you that one of these arrays will perform substantially worse with quicksort than the other two- for the one that performs the worst explain why it performs so poorly in your comment.
Expert Answer
Answer to /** * Simple integer-based implementations of some popular * sorting algorithms. Used in conjunction with the sorting la…