Quick Sort program in DrJava.....Need Help Please!!!! I need help in modfying th

Question

Quick Sort program in DrJava.....Need Help Please!!!! I need help in modfying the code

Using the QuickSort class that we developed in class as a starting point, you should modify the class code as needed to implement and test variations to improve average run-time of the algorithm.

Second, another mathematician suggested that you should select the pivot as a RANDOM element in the array. This can be implemented and tested by creating a Random object as a class variable and choosing a random element of each sub-array rather than the middle element.

_________________________________________________________________

Quicksort Code:

___________________________________________________________

Here is the Test Program:

Explanation / Answer

/**
** Java Program to Implement Quick Sort
**/

import java.util.Scanner;

/** Class QuickSort **/
public class QuickSort
{
/** Quick Sort function **/
public static void sort(int[] arr)
{
quickSort(arr, 0, arr.length - 1);
}
/** Quick sort function **/
public static void quickSort(int arr[], int low, int high)
{
int i = low, j = high;
int temp;
int pivot = arr[(low + high) / 2];

/** partition **/
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
/** swap **/
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

i++;
j--;
}
}

/** recursively sort lower half **/
if (low < j)
quickSort(arr, low, j);
/** recursively sort upper half **/
if (i < high)
quickSort(arr, i, high);
}
/** Main method **/
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Quick Sort Test ");
int n, i;
/** Accept number of elements **/
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/** Create array of n elements **/
int arr[] = new int[ n ];
/** Accept elements **/
System.out.println(" Enter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/** Call method sort **/
sort(arr);
/** Print sorted Array **/
System.out.println(" Elements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}

Quick Sort Test

Enter number of integer elements
10

Enter 10 integer elements
877 567 3456 876 467 26 934 9876 1 4567

Elements after sorting
1 26 467 567 876 877 934 3456 4567 9876

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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