Question 2: Write the following methods for sorting an array of integers: A (non

Question

Question 2:

Write the following methods for sorting an array of integers:

A (non-recursive) insertion sort method,

A recursive merge sort method,

Two different recursive quick sort methods:

A "plain" recursive quick sort method that chooses as the pivot the first element in the (sub)list to be sorted. Also, the base cases for this plain method are lists of 0 elements and lists of 1 element (since these lists are already sorted, you don't need to do anything to sort them).

A modified recursive quick sort method that uses the median-of-three method (pick the median of the 1st, middle and last element of the sub-array as the pivot) to choose the pivot. Also, the base cases for this modified method are lists of 10 elements or less. Your modified method should sort a list of 10 elements or less directly (i.e., with no recursion) using your insertion sort method.

An error-checking method that makes sure that an array is sorted (by checking that each item (after the first item) is at least as large as the previous item).

Finally, write a main method that reads integers from a file into an array and, with each of the above sorting methods, performs the following steps:

Makes a copy of the input array. Remember to make a separate copy of the array for each sorting call (or else you will be resorting a sorted array!). You can use the System.arraycopy.

Sort a new copy of the array using the sorting method, timing how long the method took (in milliseconds). You can time a method as follows:

Run the error-checking method on the sorted array after you have called the method.

Your output should include the timing of each method, the size of the array sorted and whether the error-checking method found any errors in the output from each method, all with appropriate headers. Thus, your output will look something like the following:

(Use the results of your error-checking method to decide whether to print that a sorting method "successfully" or "unsuccessfully" sorted the array.)

Explanation / Answer

Solution:

code:

package chegg;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.Scanner;

public class Sort {

// function to read data from the given file
public static ArrayList<Integer> readData() throws FileNotFoundException {

// read the file
Scanner sc = new Scanner(new File("../PlayerStats/src/data.txt"));

ArrayList<Integer> arr = new ArrayList<>();

// logic to set values in particular arrays
while (sc.hasNext()) {
// new line
String s = sc.nextLine();
if (s.trim().isEmpty()) {
continue;
} else {
// set values
// System.out.println(Integer.parseInt(s));
arr.add(Integer.parseInt(s));
}

}
sc.close(); // file closed
return arr;
}

// insertion sort method
public static void insertionSort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;

while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

// function to sorting the array Note left pointer is low and high is right
public static void quicksort(int list[], int low, int high) {
// variables for i for left and j for right and pivot for pivot value
int pivot, i, j, temp;

// check the low < high
if (low < high) {
// assign the value to pivot
pivot = low;
i = low;
j = high;

// for left < right
while (i < j) {
// increament the left until it less than pivot
while (list[i] <= list[pivot] && i <= high) {
i++;
}

// decreament the right pointer until it less than pivot
while (list[j] > list[pivot] && j >= low) {
j--;
}

// swap the left pointer value to right pointer value
if (i < j) {
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}

// swap the pivot pointer value to right pointer value
temp = list[j];
list[j] = list[pivot];
list[pivot] = temp;

// recursive call for quicksort for left partition
quicksort(list, low, j - 1);
// recursive call for quicksort for right partition
quicksort(list, j + 1, high);
}
}

// method by quicksort by median
public static void quicksortPivot(int[] arr, int left, int right) {
int size = right - left + 1;

// if size is < 3 we have to do direct sort by insertion or quick
if (size <= 3)
insertionSort(arr);
else {
// find the median
double median = median(arr, left, right);
// do partition
int partition = partition(arr, left, right, median);
  
// call recursive
quicksortPivot(arr, left, partition - 1);
quicksortPivot(arr, partition + 1, right);
}
}

// logic to find median
public static int median(int[] arr, int left, int right) {

int center = (left + right) / 2;

if (arr[left] > arr[center])
swap(arr, left, center);

if (arr[left] > arr[right])
swap(arr, left, right);

if (arr[center] > arr[right])
swap(arr, center, right);

swap(arr, center, right - 1);
return arr[right - 1];
}

// swap the numbers in array
public static void swap(int[] arr, int d1, int d2) {

int temp = arr[d1];
arr[d1] = arr[d2];
arr[d2] = temp;
}

// do partition
public static int partition(int[] arr, int left, int right, double pivot) {

int leftPtr = left;
int rightPtr = right - 1;

while (true) {
while (arr[++leftPtr] < pivot);
while (arr[--rightPtr] > pivot);
if (leftPtr >= rightPtr)
break;
else
swap(arr, leftPtr, rightPtr);
}
swap(arr, leftPtr, right - 1);
return leftPtr;
}

// error checking
public static boolean errorChecking(int[] array1, int[] array2) {

boolean b = true;
if (array1 != null && array2 != null) {
if (array1.length != array2.length)
b = false;
else
for (int i = 0; i < array2.length; i++) {
if (array2[i] != array1[i]) {
b = false;
}
}
} else {
b = false;
}
return b;
}

// main method
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub

ArrayList<Integer> arr = readData();
Integer[] i_arr = arr.toArray(new Integer[arr.size()]);
long timestamp;

int[] intertionArray = Arrays.stream(i_arr).mapToInt(Integer::intValue).toArray();
int[] quickArray = Arrays.stream(i_arr).mapToInt(Integer::intValue).toArray();
int[] quickPivotArray = Arrays.stream(i_arr).mapToInt(Integer::intValue).toArray();

timestamp = new Date().getTime();
insertionSort(intertionArray); // call insertion method
timestamp = new Date().getTime() - timestamp;
System.out.println();
System.out.println("Time for insertion sort: " + timestamp + " milliseconds.");
System.out.println("Insertion sort successfully sorted " + intertionArray.length + " elements.");

timestamp = new Date().getTime();
quicksort(quickArray, 0, quickArray.length - 1); // call simple quicksort
timestamp = new Date().getTime() - timestamp;
System.out.println();
System.out.println("Time for simple quick sort: " + timestamp + " milliseconds.");
System.out.println("sample quick sort successfully sorted " + quickArray.length + " elements.");

timestamp = new Date().getTime();
quicksortPivot(quickPivotArray, 0, quickArray.length - 1); // call pivot as median quick sort
timestamp = new Date().getTime() - timestamp;
System.out.println();
System.out.println("Time for median quick sort: " + timestamp + " milliseconds.");
System.out.println("median quic sort successfully sorted " + quickPivotArray.length + " elements.");

System.out.println();
System.out.println("Error Checking : " + errorChecking(quickArray, quickPivotArray)); // error checking method
}

}

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.