# quicksort and bubblesort comparison

• March 23rd, 2013, 03:24 PM
husain2213
quicksort and bubblesort comparison
Hello everyone,
I'm having trouble with my assignment and need you're help!
I'm supposed to write the code for bubblesort and quicksort and test them under different array sizes while recording the number of comparisons done by each algorithm (to compare efficiency). the output should be the sorted arrays for array sizes of 64 and less, and then a list of the number of comparisons for each algorithm and array size.
The Problems I'm having:
1- although I run the sorting algorithm, the outputed array is not sorted!
2- I'm not sure about the code for quicksort (and where to increment for the number of comparisons). I have to use the median of three implementation.
3- the program just freeze after displaying the "supposedly" sorted arrays. It doesn't crash, but it doesn't go on to show the number of comparisons.

I would appreciate anyone taking the time to help me, I've been stuck on it for a while and sometimes you need another pair of eyes to see what you're missing.
this is my code (sorry if its messy :confused:)
Code :

```import java.util.*;   public class CompareSorts2 { public static int quickCount, bubbleCount; // declaring the count variables here to use them in all the methods   public static void main(String[]args) { int[] Asize = {16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768}; // different array sizes to be tested int[] quickCountArray = new int[12]; //Those arrays hold the count values for each sorting method int[] bubbleCountArray = new int[12]; Random rand = new Random();   for(int i =0; i < Asize.length; i++) { int n = Asize[i]; //current array size int[] array = new int[n]; // declare array with the sizes in the array Asize int[] tempArray = new int[n];   for(int j =0; j < array.length; j++) // populate the array { array[j] = rand.nextInt(5000); // new random for each position in array 0-4999 (array to be sorted) }   for(int k = 0; k < array.length; k++) { tempArray[k] = array[k]; //copy the array to to use it on quicksort first } // sorting the array using both sorting algorithms quickCount = quickSort(tempArray, 0, tempArray.length-1); // running quicksort     if(n <=64) { System.out.print("\n\nn = "+n); // display sorted array using both sorting method System.out.println("\nQuick Sort:"); for(int y = 0; y < n; y++) { System.out.print(tempArray[y]+" "); } }   for(int k = 0; k < array.length; k++) { tempArray[k] = array[k]; // assigning tempArray to the original array to sort it again using bubblesort }   bubbleCount = bubbleSort(tempArray); // sorting with bubblesort   if(n <=64) { System.out.println("\nBubble Sort:"); for(int y = 0; y < n; y++) { System.out.print(tempArray[y]+" "); } }   //Store the comparison count for each algorithm in its specified array at the i position quickCountArray[i] = quickCount; bubbleCountArray[i] = bubbleCount; }   // printing the comparison count as a table System.out.println("\n\nArray Size\t quick Sort\t\t Bubble Sort"); for(int i = 0; i < 12; i++) System.out.println(Asize[i]+"\t\t\t"+quickCountArray[i]+"\t\t\t"+bubbleCountArray[i]); }   //=================================================================================================== //Bubble Sort method public static int bubbleSort(int[] array) { int n = array.length; bubbleCount = 0; // setting the count to 0 for each time you sort for(int i =0; i < n-1; i++) { for(int j = 0; j <(n-1-i); j++) { bubbleCount++; // incrementing the count each time you compare two elements if(array[j+1] < array[j]) // if true, swap values { swap(array, j+1, i); } } }   return bubbleCount; // return the whole array sorted }   //======================================Quick Sort Method===================================================   public static int quickSort(int[] array, int low, int high) { int n = array.length; quickCount = 0; // setting the count to 0 for each time you sort   if(low+10 > high) // switch to bubble sort if array size is less than 10 return quickCount + bubbleSort(array); else { // Sort low, middle, high int middle = (low + high)/2;   // increment count quickCount++;   if( array[middle] < (array[low])) swap(array, low, middle); if(array[high] < (array[low])) swap(array, low, high); if(array[high] > (array[middle])) swap(array, middle, high);   // Place pivot at position high - 1 swap(array, middle, high-1); int pivot = array[high - 1];   // Begin partitioning int i, j; for(i = low, j = high - 1; ;) { while(array[++i] < pivot) ; while(array[--j] > pivot) ; if(i >= j) break; swap(array, i, j); }   // Restore pivot swap(array, i, high-1);   quickSort(array, low, i-1); // Sort small elements quickSort(array, i+1, high); // Sort large elements   return quickCount; } }   public static final void swap(int[] array, int index1, int index2 ) { int temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } }```
• March 23rd, 2013, 03:36 PM
Norm
Re: quicksort and bubblesort comparison
Quote:

program just freeze
Are there any infinite loops? Add some printlns to track down where the code is executing so you can find the infinite loop and fix it. when you find the looping, print out the values of the variables that control the loop so you can see how their values are changing (or not changing) and stop the looping.
• March 23rd, 2013, 04:00 PM
husain2213
Re: quicksort and bubblesort comparison
I think there was a problem in my swap() method, but its fixed now and the arrays are sorted.
There are no infinite loops, but quicksort is.. well, not quick. It takes forever and doesn't return a correct comparison count (always return 1)

I fixed a few things in the code to make it easier to debug, please take a look and tell me what you think

Code :

```import java.util.*;   public class CompareSorts2 { //public static int quickCount, bubbleCount; // declaring the count variables here to use them in all the methods   public static void main(String[]args) { int[] Asize = {16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768}; int[] quickCountArray = new int[12]; //Those arrays hold the count values for each sorting method int[] bubbleCountArray = new int[12]; Random rand = new Random();   for(int i =0; i < Asize.length; i++) { int n = Asize[i]; //current array size int[] array = new int[n]; // declare array with the sizes in the array Asize int[] tempArray = new int[n];   for(int j =0; j < array.length; j++) // populate the array { array[j] = rand.nextInt(5000); // new random for each position in array 0-4999 }   for(int k = 0; k < array.length; k++) { tempArray[k] = array[k]; }   quickCountArray[i] = quickSort(tempArray, 0, tempArray.length-1);     if(n <=64) { System.out.print("\n\nn = "+n); System.out.println("\nQuick Sort:"); for(int y = 0; y < n; y++) { System.out.print(tempArray[y]+" "); } }   for(int k = 0; k < array.length; k++) { tempArray[k] = array[k]; }   bubbleCountArray[i] = bubbleSort(tempArray);   if(n <=64) { System.out.println("\nBubble Sort:"); for(int y = 0; y < n; y++) { System.out.print(tempArray[y]+" "); } }   System.out.println("\n\nArray Size\t quick Sort\t\t Bubble Sort"); System.out.println(Asize[i]+"\t\t\t"+quickCountArray[i]+"\t\t\t"+bubbleCountArray[i]); } /* temporarly removed for diagnosis // printing the comparison count as a table System.out.println("\n\nArray Size\t quick Sort\t\t Bubble Sort"); for(int i = 0; i < 12; i++) System.out.println(Asize[i]+"\t\t\t"+quickCountArray[i]+"\t\t\t"+bubbleCountArray[i]); */ }   //=================================================================================================== //Bubble Sort method public static int bubbleSort(int[] array) { int n = array.length; int bubbleCount = 0; // setting the count to 0 for each time you sort for(int i =0; i < n-1; i++) { for(int j = 0; j <(n-1-i); j++) { bubbleCount++; // incrementing the count each time you compare two elements if(array[j+1] < array[j]) // if true, swap values { swap(array, j+1, j); } } }   return bubbleCount; // return the whole array sorted }   //======================================Quick Sort Method===================================================   public static int quickSort(int[] array, int low, int high) { int n = array.length; int quickCount = 0; // setting the count to 0 for each time you sort   if(low+10 > high) // switch to bubble sort if array size is less than 10 return quickCount + bubbleSort(array); else { // Sort low, middle, high int middle = (low + high)/2;   // increment count quickCount++;   if( array[middle] < (array[low])) swap(array, low, middle); if(array[high] < (array[low])) swap(array, low, high); if(array[high] > (array[middle])) swap(array, middle, high);   // Place pivot at position high - 1 swap(array, middle, high-1); int pivot = array[high - 1];   // Begin partitioning int i, j; for(i = low, j = high - 1; ;) { while(array[++i] < pivot) ; while(array[--j] > pivot) ; if(i >= j) break; swap(array, i, j); }   // Restore pivot swap(array, i, high-1);   quickSort(array, low, i-1); // Sort small elements quickSort(array, i+1, high); // Sort large elements   return quickCount; } }   public static final void swap(int[] array, int x, int z ) { int temp = array[x]; array[x] = array[z]; array[z] = temp; } }```

--- Update ---

Oh, I forgot to tell. Quick sort should switch to bubble sort when there are only 10 or less items to be sorted, but it should still count the number of comparisons :confused:
• March 23rd, 2013, 04:05 PM
Norm
Re: quicksort and bubblesort comparison
Have you solved your problem? If not, please explain what the problem is now.
• March 23rd, 2013, 04:09 PM
husain2213
Re: quicksort and bubblesort comparison
no, its not completely solved yet! here is what's wrong:

1- quick sort still takes forever for larger array sizes (I don't think it is supposed to).
2- comparison count returned by quicksort is always 1

Can you help?
• March 23rd, 2013, 04:34 PM
Norm
Re: quicksort and bubblesort comparison
The count variable is a local variable whose value is lost on recursive calls.
One solution is to make it a static class variable.

For testing shorten the Asize array.
One measure of method execution would be to time its duration by using the System.currentTimeMillis() values.

To find the problem, continue adding println method calls that show time or elapse time.
• March 25th, 2013, 12:27 AM
husain2213
Re: quicksort and bubblesort comparison
Thanks Norm. This code is full of mistakes, i'm finding out, but i've been fixing them one by one.
I think I fixed the counts, but I broke some other stuff on the way :confused:
Quick sort is now giving me an error that I can't seem to fix. Are you familiar with quick sort and median of three partitioning?

the error I get is an java.lang.ArrayIndexOutOfBoundsException: -1, I looked and tried many codes for quicksort that I fount on the internet but I always get this error.
Do you have any idea on how to fix it? are you familiar with the algorithm?

Code :

```import java.util.*;   public class CompareSorts2 { public static int quickCount; // declaring the count variables here to use them in all the methods   public static void main(String[]args) { int[] Asize = {16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768}; int[] quickCountArray = new int[12]; //Those arrays hold the count values for each sorting method int[] bubbleCountArray = new int[12]; Random rand = new Random();   for(int i =0; i < Asize.length; i++) { int n = Asize[i]; //current array size int[] array = new int[n]; // declare array with the sizes in the array Asize int[] tempArray = new int[n];   for(int j =0; j < array.length; j++) // populate the array { array[j] = rand.nextInt(5000); // new random for each position in array 0-4999 }   for(int k = 0; k < array.length; k++) { tempArray[k] = array[k]; }   if(n <=64) { System.out.print("\n\nn = "+n); System.out.println("\nArray before Quick Sort:"); for(int y = 0; y < n; y++) { System.out.print(tempArray[y]+" "); } }   quickCountArray[i] = quickSort(tempArray, 0, tempArray.length-1, 0);   if(n <=64) { System.out.print("\n"); System.out.println("\nAfter Quick Sort:"); for(int y = 0; y < n; y++) { System.out.print(tempArray[y]+" "); } }   for(int k = 0; k < array.length; k++) { tempArray[k] = array[k]; }   if(n <=64) { System.out.print("\n"); System.out.println("\nArray before Bubble Sort:"); for(int y = 0; y < n; y++) { System.out.print(tempArray[y]+" "); } }   //bubbleCountArray[i] = bubbleSort(tempArray, 0);   if(n <=64) { System.out.println("\nAfter Bubble Sort:"); for(int y = 0; y < n; y++) { System.out.print(tempArray[y]+" "); } }   }   // printing the comparison count as a table System.out.println("\n\nArray Size\t Quick Sort\t\t Bubble Sort"); for(int i = 0; i < 12; i++) System.out.println(Asize[i]+"\t\t\t"+quickCountArray[i]+"\t\t\t"+bubbleCountArray[i]);   }   //=================================================================================================== //Bubble Sort method public static int bubbleSort(int[] array, int count) { int n = array.length; //bubbleCount = count; // setting the count to 0 for each time you sort for(int i =0; i < n-1; i++) { for(int j = 0; j <(n-1-i); j++) { count++; // incrementing the count each time you compare two elements if(array[j+1] < array[j]) // if true, swap values { swap(array, j+1, j); } } }   return count; // return the whole array sorted }   //======================================Quick Sort Method===================================================   public static int quickSort(int[] array, int left, int right, int count) { //int n = right - left +1; //array size quickCount = count+1; // setting the count to 0 for each time you sort   if(right - left > 10) // switch to bubble sort if array size is less than 10 { int median = partition(array, left, right);   quickSort(array, left, median-1, quickCount); // Sort small elements return quickSort(array, median+1, right, quickCount); // Sort large elements }   else { int[] newArray = new int[10]; int j = 0; for(int i = left; i <= right; i++) { int temp = array[i];   newArray[j] = temp; j++; } System.out.println("\nArray to be switched to Bubblesort:"); for(int y = 0; y <10; y++) { System.out.print(newArray[y]+" "); } return bubbleSort(newArray, quickCount); } }   public static int partition(int[] array, int left, int right) { int pivot = (left + right) / 2;   int i = left; int j = right+1;   while(i < j) { while(array[++i] < pivot) ; while(array[--j] > pivot) ; if(i >= j) break;   swap(array, i, j);   } swap(array, i, j); // undo last swap when i >=j swap(array, left, j);   return j; }   public static final void swap(int[] array, int x, int z ) { int temp = array[x]; array[x] = array[z]; array[z] = temp; }   }```
• March 25th, 2013, 05:51 AM
Norm
Re: quicksort and bubblesort comparison
Quote:

java.lang.ArrayIndexOutOfBoundsException: -1,
Check how the index's value is created so it stays in range. You need to look at why the index is -1

I don't know the algorithm.