Please help: Create a program (in Java) to sort a list of integers using the in
ID: 3762390 • Letter: P
Question
Please help:
Create a program (in Java) to sort a list of integers using the in place Quicksort algorithm.
---------
Test out the program on lists of size 100, 1000, 5000, 10000 and 50000 or other sizes. The program should generate the list randomly every time using the java.util.Random class.
---------
It should allow the user to choose the size and pivot method at runtime. In particular, try randomly choosing the pivot element, try choosing the median of 3 randomly chosen elements as the pivot or the book technique (median of first center and last element).
----------
Is there a noticeable difference? How much of a difference in there for different sizes.
------
Both the unsorted and sorted lists must be written to two output files named ‘sorted’ and ‘unsorted’.
Attempt to gauge the run time of your sort experimentally, print these results on the console.
Explanation / Answer
Java code:
import java.util.Arrays;
public class QuickSortTest{
public static void main(String args[]) {
int[] unsorted = {1000, 100, 50000, 10000,5000};
System.out.println("Unsorted array :" + Arrays.toString(unsorted));
QSort algorithm = new QSort();
algorithm.sort(unsorted);
System.out.println("Sorted array :" + Arrays.toString(unsorted));
}
}
class QSort {
private int length;
private int data[];
public void sort(int[] num) {
if (num == null || num.length == 0) {
return;
}
this.data = numbers;
length = num.length;
qSort(0, length - 1);
}
private void qSort(int low, int high) {
int i = low;
int j = high;
int pivot = data[low + (high - low) / 2];
while (i <= j) {
while (data[i] < pivot) {
i++;
}
while (data[j] > pivot) {
j--;
}
if (i <= j) {
swap(i, j);
i++;
j--;
}
}
if (low < j) {
qSort(low, j);
}
if (i < high) {
qSort(i, high);
}
}
private void swap(int i, int j)
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
Output of java code:
Unsorted array :[1000, 100, 50000, 10000,5000]
Sorted array :[100, 1000, 5000, 10000, 50000]