I'm trying to compare the execution of the java implementation of QuickSort and its hybrid version (using InsertionSort for those partitions which are smaller than an integer k). I wrote a test class to analyze the behaviour of the algorithms for some values ok k (1 <= k <= 25). For each value of k the class compares for different sizes of the input array the two algorithms.
I can't run the program for some values of the size of the array, for instance for values greater than 4000. The execution reach some different values and then freeze, after a while it will finish but I have no output of the computation. (I'm using eclipse).
What could be the problem? I wish to perform the comparation of the two algoritms for an array size from 10 to 10000 (at least).
The code is listed below:
public class Main {
private static final int MAX_K = 25;
private static final int MAX_SIZE = 4500;
private static final int ADD_SIZE = 100;
private static int size = 10;
private static QuickSort qSort;
private static HybridSort hSort;
private static void initArray(int[] A) {
Random rand = new Random();
for (int i = 0; i < A.length; i++) {
// A[i] = (int)(Math.random()*100000);
A[i] = rand.nextInt();
}
}
private static int[] A = new int[10];
private static int[] B = new int[10];
public static void main(String[] args) {
try {
FileWriter fstream = new FileWriter("out.txt");
BufferedWriter out = new BufferedWriter(fstream);
out.write("Init file");
qSort = new QuickSort();
hSort = new HybridSort();
/************************************************/
/* Comparison */
/************************************************/
for (int i = 1; i <= MAX_K; i++) {
hSort.setK(i);
int p = 0;
for (int j = size; j <= MAX_SIZE; j = j + ADD_SIZE) {
A = new int[j];
B = new int[j];
initArray(A);
initArray(B);
long sTime = System.nanoTime();
qSort.quickSort(A, 0, A.length - 1);
long qDuration = System.nanoTime() - sTime;
sTime = System.nanoTime();
hSort.hybridSort(B, 0, B.length - 1);
long hDuration = System.nanoTime() - sTime;
out.append(/* "\nA: " +printArray(A)+ */"K: " + i + " A["
+ j + "]\tQ = " + qDuration + " H = " + hDuration
+ "\n");
String h = Long.toString(hDuration);
String q = Long.toString(qDuration);
if (h.length() < q.length()) {
p++;
out.append("\t#OUTPERM for K: "
+ i
+ "\t\t"
+ hDuration
+ "\t\t < \t\t "
+ qDuration
+ "\t\t\t\t| A[]\t\t"
+ A.length
+ ((q.length() - h.length()) == 2 ? "\t Magn. 2"
: "") + "\n");
}
}
if (p > 0)
out.append("#P= " + p + " for K= " + i + "\n\n");
}
out.append("Close file");
out.close();
} catch (IOException e) {
}
}
}
The algorithm classes:
public class QuickSort {
public void quickSort(int[] A, int left, int right){
if (left < right) {
int m = Partition(A, left, right);
quickSort(A, left, m-1);
quickSort(A, m, right);
}
}
private int Partition(int[] A, int left, int right){
int pivot = A[right];
int i = left;
int j = right;
while (true) {
while ( (A[j] > pivot)) {
j--;
}
while ((A[i] < pivot)) {
i++;
}
if (i < j){
int swap = A[j];
A[j] = A[i];
A[i] = swap;
}else{
return i;
}
}
}
}
public class HybridSort {
int k;
int m;
InsertionSort iSort;
public HybridSort() {
k = 3;
iSort = new InsertionSort();
}
public void hybridSort(int[] A, int left, int right) {
if (left < right) {
if ((right - left) < k) {
iSort.sort(A,left,right);
} else {
m = Partition(A, left, right);
hybridSort(A, left, m - 1);
hybridSort(A, m, right);
}
}
}
private int Partition(int[] A, int left, int right) {
int pivot = A[right];
int i = left;
int j = right;
while (true) {
while ((A[j] > pivot) && (j >= 0)) {
j--;
}
while ((A[i] < pivot) && (i < A.length)) {
i++;
}
if (i < j) {
int swap = A[j];
A[j] = A[i];
A[i] = swap;
} else {
return i;
}
}
}
public void setK(int k) {
this.k = k;
}
}
Your implementation of Partition is not correct. Consider the small test below (I made Partition static for my convenience).
Both while loops won't be executed, because A[i] == A[j] == pivot. Moreover, i<j, so the two elements will be swapped, resulting in exactly the same array. Therefore, the outer while loop becomes infinite.
The same problem occurs for any array for which the first and last element are the same.
public class Test {
public static void main(String[] args) {
int[] A = {1, 1};
Partition(A, 0, 1);
}
private static int Partition(int[] A, int left, int right){
int pivot = A[right];
int i = left;
int j = right;
while (true) {
while ( (A[j] > pivot)) {
j--;
}
while ((A[i] < pivot)) {
i++;
}
if (i < j){
int swap = A[j];
A[j] = A[i];
A[i] = swap;
}else{
return i;
}
}
}
}