Write the following method for sorting an array of integers( IN JAVA): recursive
ID: 3876758 • Letter: W
Question
Write the following method for sorting an array of integers( IN JAVA):
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). Add 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.)
Test Data
Explanation / Answer
class QuickSort
{
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
if (arr[j] <= pivot) // If current element is smaller than or equal to pivot
{
i++;
int temp = arr[i]; // swap arr[i] and arr[j]
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1]; // swap arr[i+1] and arr[high] (or pivot)
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Run program
public static void main(String args[])
{
int arr[] = { 50,854,540,492,656,345,599,518,325,691,700,6,279,938,937,940,411,949,333,717,992,685,378,652,33,701,66,666,657,232,610,598,342,349,210,828,879,378,216,257,94,957,797,21,909,878,730,711,135,118,259 };
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.