Thread: QuickSort Help

I'm working on this program which uses the quickSort algorithm to sort arrays of N sizes using the median of 3 to determine the pivot. The output is to print the list the number of comparisons for the arrays of N= 64 and 128 to a file named "output.txt". Also as another requirement, when the arrays get repartitioned below 10 elements, it switches to bubbleSort. So far I have this:

import java.util.Random;
import java.io.*;
 
public class Project3 {
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        //array n = the size of arrays to sort
        //array bsa and ssa for BubbleSort and SelectionSort
        int[] n = {16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768};
        int count = 0;
        int[] qsa = new int[n.length];
 
        Random randomNumber = new Random();
 
        for(int i = 0; i < n.length; i++){
            int[] array = new int[n[i]];
            for(int j= 0; j < array.length; j++){
                array[j] = randomNumber.nextInt(4999);
            }
 
            int quickSortCount = quickSort(array, 0, array.length - 1);
 
            if(count <= 2){
                System.out.println("Sorted Array of "+n[i]+": " + java.util.Arrays.toString(array));
                count++;
            }
 
            qsa[i] = quickSortCount;
        }
 
        System.out.println();
 
        /**
         * Writes the # of comparisons in the quickSort
         * method at each n[x] location.
         */
        PrintWriter out = new PrintWriter("Output.txt");
 
        out.println("N\tQuickSort");
        System.out.println("N\t\tQuickSort");
 
        for(int x = 0; x < qsa.length; x++){
            out.println(n[x]+"\t"+qsa[x]);
            System.out.println(n[x]+"\t\t"+qsa[x]);
        }
 
        out.close();
    }
 
    /**
     * QuickSort: Sorts the array recursively through the 
     * quickSort method until the  partitioned array size
     * is less than 10, at with point it switches to 
     * bubbleSort.
     * 
     * @param array
     * @param left
     * @param right 
     */
    static int quickSort(int[] array, int left, int right){
        int size = right - left + 1;
        int count = 0;
        int bsc = 0;
 
        count++;
 
        if(size < 10){
 
            bsc = bubbleSort(array);
 
        }
        else{
            double median = medOf3(array, left, right);
            int p = partition(array, left, right, median);
            quickSort(array, left, p - 1);
            quickSort(array, p + 1, right);
        }
 
        count += bsc;
        return count;
    }
 
    /**
     * 
     * @param array
     * @return 
     */
    static int bubbleSort(int[] array){
        int n = array.length;
        int count = 0;
 
        for(int pass=1; pass<=n; pass++){
            for(int current=0; current<n-pass; current++){
                if(array[current] > array[current+1]){
                    //swap 
                    int temp = array[current];
                    array[current] = array[current+1];
                    array[current+1] = temp;
                    count++;
                }
            }
        }
 
        return count;
    }
    /**
     * MedOf3: computes the the median.
     * 
     * @param array
     * @param left
     * @param right
     * @return 
     */
    static int medOf3(int[] array, int left, int right){
        int center = (left+right) / 2;
 
        if(array[left] > array[center])
            swap(array, left, center);
        if(array[left] > array[right])
            swap(array, left, right);
        if(array[center] > array[right])
            swap(array, center, right);
 
        swap(array, center, right - 1);
 
        return array[right - 1];
    }
 
    /**
     * Partitions the array.
     * 
     * @param intArray
     * @param left
     * @param right
     * @param pivot
     * @return 
     */
    static int partition(int[] array, int left, int right, double pivot) {
    int lPointer = left;
    int rPointer = right - 1;
 
    while (true) {
      while (array[++lPointer] < pivot)
        ;
      while (array[--rPointer] > pivot)
        ;
      if (lPointer >= rPointer)
        break;
      else
        swap(array, lPointer, rPointer);
    }
    swap(array, lPointer, right - 1);
    return lPointer;
  }
 
    /**
     * Swaps elements within the array.
     * 
     * @param array
     * @param index1
     * @param index2 
     */
    static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
 
    array[index1] = array[index2];
    array[index2] = temp;
  }
 
 
}

It lists the sorted arrays of N = 64, 128, and 256 but after that is when I start having issues. Is it a continuous loop or something else that is bogging it down?

The output is supposed to look something like this:

Sorted Array of 64:[*,*,*,*]
Sorted Array of 128:[*,*,*,*]
Sorted Array of 256:[*,*,*,*]

N Comp
64 *
128 *


Any help would be highly useful

Thanks

The problem is that it takes roughly 25-30 min for the program to finish running. That's what I meant by bogging it down. I'm confused on whats going on within the quickSort method that's causing such a delay?