Question

Hello so I have written this Quicksort code, but it only seems to work when the array size is 100 or less. If it goes over than it takes forever to run and never completes. Please help debug and fix.

public class Test {

public static void main(String[] args) {
int[] myArray = new int[]{5, 10, 12, 55, 24, 90, 52, 900};
System.out.println("Before Sort");
printArray(myArray);
System.out.println("Quicksorted");
quickSort(myArray, 0, myArray.length - 1);
printArray(myArray);

}

public static void quickSort(int array[], int low, int high) {

if (low < high) {
int partitionPoint = partition(array, low, high);
quickSort(array, low, partitionPoint - 1);
quickSort(array, partitionPoint + 1, high);
}
}

public static int partition(int array[], int low, int high) {

int pivot = array[low];
int i = low;
int j = high;

while (i < j) {
while (array[i] < pivot) {
i++;
}

while (array[j] > pivot) {
j--;
}

if (i < j) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}

int temp = array[j];
array[j] = pivot;
pivot = temp;

return j;

}

public static void printArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + " ");
}
}
}

Thank you!

Answer 1

Code:

public class Test {
   public static void main(String[] args)
   {
       int[] myArray = new int[]{5, 10, 12, 55, 24, 90, 52, 900};
       System.out.println("Before Sort");
       printArray(myArray);
       System.out.println("Quicksorted");
       quickSort(myArray, 0, myArray.length - 1);
       printArray(myArray);
   }

   public static void quickSort(int array[], int low, int high)
   {
       if (low < high)
       {
           int partitionPoint = partition(array, low, high);
           quickSort(array, low, partitionPoint - 1);
           quickSort(array, partitionPoint + 1, high);
       }
   }

public static int partition(int array[], int low, int high)
{

   int pivot = array[low];
   int i ,p1=low+1,temp;
   for(i=low+1; i<=high;i++)
   {
       if(array[i]<pivot)
       {
           if(i!=p1)
           {
               temp = array[p1];
               array[p1] = array[i];
               array[i] = temp;
           }
           p1++;
       }
   }
   array[low]= array[p1-1];
   array[p1-1] = pivot;
   return p1-1;
}

   public static void printArray(int arr[])
   {
       for (int i = 0; i < arr.length; i++)
       {
           System.out.println(arr[i] + " ");
       }
   }
}

OutPut:

Before Sort
5
10
12
55
24
90
52
900
Quicksorted
5
10
12
24
52
55
90
900

//This Code will work for any size of Array.