I have two Java implementations of a bi-directional bubble sort (cocktail sort) designed to sort a list of n integers.
- The first one is a "vanilla" cocktail sort.
- The second one increments a left or right buffer after each pass, because after each left or right pass, exactly one item is guaranteed to be sorted.
Strangely, the second implementation is much slower (~15 and ~18 seconds respectively for 100k integers).
Sample one: ("vanilla")
int n = 100000; //length of array, largest element in array
//create an array with one million random integers
int[] array = new int[n];
for (int i = 0; i < array.length; i++) //set each item...
{
array[i] = (int)((Math.random() * n) + 1); //...to a random int 1 to n inclusive
}
long startTime = System.currentTimeMillis(); // start timer
boolean changed = true; //to flag if any changes were made
int a; // to hold each of two items
int b;
long totalPasses = 0; // total passes over the array
long totalSwaps = 0; // total number of times two elements were swapped
do
{
changed = false;
if (totalPasses % 2 == 0) // pass from left to right
{
for (int i = 0; i < (array.length-1); i++)
{
a = array[i];
b = array[i+1];
if (a > b) // if the two selected elements are not in order
{
array[i] = b; // swap the elements
array[i+1] = a;
changed = true; // flag that a change has been made
totalSwaps++; // update the number of changes made
}
}
}
else // pass from right to left
{
for (int i = (array.length-1); i > 0; i--)
{
a = array[i-1];
b = array[i];
if (a > b) // if the two selected elements are not in order
{
array[i-1] = b; // swap the elements
array[i] = a;
changed = true; // flag that a change has been made
totalSwaps++; // update the number of changes made
}
}
} // end sorting for this pass
totalPasses++;
} while (changed);
long endTime = System.currentTimeMillis();
System.out.println();
System.out.println("Finished sorting " + n + " integers. (" + (double)(endTime-startTime)/1000 + " seconds to make " + totalSwaps + " swaps over " + totalPasses + " passes)");
Sample two: (with incrementing buffer)
int n = 100000; //length of array, largest element in array
//create an array with one million random integers
int[] array = new int[n];
for (int i = 0; i < array.length; i++) //set each item...
{
array[i] = (int)((Math.random() * n) + 1); //...to a random int 1 to n inclusive
}
/*
* at the end of each left to right pass, increment the right buffer
* at the end of each right to left pass, increment the left buffer
*/
long startTime = System.currentTimeMillis(); // start timer
boolean changed = true; //to flag if any changes were made
int a; // to hold each of two items
int b;
int leftBuffer = 0; // distance from each side that is already sorted
int rightBuffer = 0;
long totalPasses = 0; // total passes over the array
long totalSwaps = 0; // total number of times two elements were swapped
do // main sorting loop
{
changed = false;
if (totalPasses % 2 == 0) // pass from left to right
{
for (int i = leftBuffer; i < ((array.length-1)-rightBuffer); i++)
{
a = array[i];
b = array[i+1];
if (a > b) // if the two selected elements are not in order
{
array[i] = b; // swap the elements
array[i+1] = a;
changed = true; // flag that a change has been made
totalSwaps++; // update the number of changes made
}
}
rightBuffer++; // increment the cover for
}
else // pass from right to left
{
for (int i = ((array.length-1)-rightBuffer); i > leftBuffer; i--)
{
a = array[i-1];
b = array[i];
if (a > b) // if the two selected elements are not in order
{
array[i-1] = b; // swap the elements
array[i] = a;
changed = true; // flag that a change has been made
totalSwaps++; // update the number of changes made
}
}
leftBuffer++;
} // end sorting for this pass
totalPasses++;
} while (changed); // end sorting loop
long endTime = System.currentTimeMillis();
System.out.println();
System.out.println("Finished sorting " + n + " integers. (" + (double)(endTime-startTime)/1000 + " seconds to make " + totalSwaps + " swaps over " + totalPasses + " passes)");
Can someone explain to this Java noob what is happening?
