QuickSort Help

• March 26th, 2013, 05:30 PM
3sbwya
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:

Code Java:

```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
• March 26th, 2013, 06:04 PM
Norm
Re: QuickSort Help
Can you explain what the problem is?
Quote:

that is bogging it down
My suggestion is to try debugging the code by adding println() statements to show where the execution goes and how the values of variables change as the code is executed. The System currrentTimeMillis() method is useful for computing how long a section of code took to execute.
• March 26th, 2013, 06:57 PM
3sbwya
Re: QuickSort Help
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?
• March 26th, 2013, 07:03 PM
Norm
Re: QuickSort Help
Some suggestions;
Use a seed value in the Random class's constructor so the same sequence of numbers is generated while debugging.
Pick ONE array size that has enough elements to show the problem and work with that while debugging. That will reduce the debug output.
Add printlns to show where the time is being spent. Use times of execution (See post#2) or the counts to see where the code is executing too much.