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;
}
}
LinkBack URL
About LinkBacks
quicksort and bubblesort comparison
)
Reply With Quote
Related threads:
Re: quicksort and bubblesort comparison