Description of program Write a Java program to implement and

Description of program:

Write a Java program to implement and test the quicksort function. This simple implementation will sort an array of integers. Upload the .java file into A5 folder of icollege.

The grading program will run at least these tests:

Calls quicksort(NULL, 0) to make sure that it doesn\'t crash.

Calls quicksort to sort an array with just one element.

Calls quicksort to sort an array with 1000 elements (containing the numbers 0 through 1000 in a random order).

Calls quicksort to sort an array that contains 1000 elements with two copies of the numbers from 0 to 499. Check that the array is correct after sorting.

Calls quicksort to sort an array that contains the numbers 0 through 25 already sorted.

Calls quicksort to sort an array that contains the numbers 25 through 0 in reverse order.

Solution

import java.util.Random;
public class QuickSort {

private int array[];
private int length;

public void sortArray(int[] inArr) {

if (inArr == null || inArr.length == 0) {
return;
}
this.array = inArr;
length = inArr.length;
quickSort(0, length - 1);
}

private void quickSort(int lIndex, int hIndex) {

int i = lIndex; // lowerIndex
int j = hIndex;
// pivot number calculating, i am taking pivot as middle index number
int pivot = array[lIndex+(hIndex-lIndex)/2];
// divide and conquer techinq
while (i <= j) {
/**
* Divid and conquer
           * In every iteration, number which is greater then the pivot value, and
           * right side which is less then the pivot value.
* after searching swapping numbers
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swap(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lIndex < j)
quickSort(lIndex, j);
if (i < hIndex)
quickSort(i, hIndex);
}

private void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

public static void main(String a[]){

MyQuickSort sorter = new MyQuickSort();
       Random randomGenerator = new Random();
       int[] randArray = new int[1001]; // initialising empty array with size
       for (int i = 1; i <=1000; ++i){
           int randomInt = randomGenerator.nextInt(1000);
           randArray[i]=randomInt;
             
           System.out.println(randomInt);
       }
sorter.sort(randArray);
for(int i:randArray){
System.out.print(i);
          
System.out.print(\" \");
}
}
}