Write a JAVA program to sort a list of integers using \'in place\' Quicksort alg
ID: 3811588 • Letter: W
Question
Write a JAVA program to sort a list of integers using 'in place' Quicksort algorithm.
Generate the list randomly every time using the java.util.Random class. Allow the user to choose the size of the array.
The program should display the result of sorting the array of that size using a PIVOT element that chooses the median of 3 RANDOMLY chosen elements.
Try your program on lists of size 100, 1000, 5000, 10000 and 50000. (You may try other sizes as well.) is there a noticeable difference?
Note how much of a difference is there for different sizes, you should record this in your 'readme file
Both the unsorted and sorted lists must be written to two text files named 'sorted' and unsorted'
Explanation / Answer
package com.java2novice.sorting;
public class MyQuickSort {
private int array[];
private int length;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(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();
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}