Strange Bublesort implementation flaw on wikisource
IMPORTANT! Please read it carefully in order to understand. Thanks for reading.
Hi all,
Today we explored the Bubble sort algorithm at school(Sixth Form in the UK, Y13) when we doing some Discrete Maths. So I thought I would go and implement it in Java(i've been doing Java for 4 days now). I firstly took a look at wikisource to see at the implementation and couldn't understand theirs so I went on and with the definition on a piece of paper I wrote mine. After some examination and tests I can conclude that my algorithm implementation is faster because I do the sorting with fewer passes - their implementation didn't take account whether any swaps occured in a pass so their number of passes was constant with respect to number of elements. So, here's the definition of Bubble sort according to our textbook:
1. If there's only one or less numbers in the list, then stop.
2. Make one pass down the list, comparing and swapping
3.If no swaps have occured then stop. Otherwise, ignore the last element
4. Repeat...
Now let's do the analysis.
I'll take the numbers 2, 1, 3, 5, 4. They only require one pass in order to be sorted but the disadvantage of Bubble sort as we all know is that we have to complete another pass through the data to ensure sorting is finished, so total number of passes is 2. Now, here's their implementation:
publicstaticvoid bSort(int data[],int n)// wikisource implementation
// pre: 0<=n <= data.length
// post: values in data[0..n-1] in ascending order
{
int numSorted=0;// number of values in order
int index;// general index
int temp;
while (numSorted < n)
{
// bubble a large element to higer array index
for (index=1; index < n-numSorted; index++)
{
if (data[index]<data[index-1])
{
// swap data[index] and data[index-1]
temp = data[index];
data[index]= data[index-1];
data[index-1] = temp;
}
}
// at least one more value in place
numSorted++;
System.out.println("pass done! their algorithm!");
}
}
You can see that their never check if any swaps have been done or not. Their algorithm does 5 passes in total. Here's my implementation:
publicstaticvoid BubbleSort(int[] data)
{
boolean Swaped =true;// set to true so while is executed once, too lazy to use do {} while()
if(data.length == 0 || data.length == 1)
{
System.out.println("List empty or no data to sort.");
}
else
{
int n = data.length;// n is the number of numbers to sort, so I have to do n - 1 comparisons
int temp;// temp var so I can swap vars
while(Swaped ==true)
{
Swaped =false;// could remove this if use do {} while()
for(int z = 0; z >< (n - 1); z++)
{
if(data[z+1] < data[z])
{
temp = data[z+1];
data[z+1] = data[z];
data[z] = temp;
Swaped =true;
}
}
n--;// decrement number of comparisons to do
System.out.println("pass done! my algorithm!");
}
}
My algorithm does only 2 passes(as expected). If you want to test yourself, here's the full source to play with:
/*
* Copyright (c) 2005 Milen Dzhumerov
* All rights reserved.
*/
/**
*
*/
package bubble;
/**
* @author gamehack
*
*/
publicclass Main{
/**
* @param args
*/
publicstaticvoid main(String[] args){
int[] test =newint[]{2, 1, 3, 5, 4};
int[] test1 =newint[]{2, 1, 3, 5, 4};
BubbleSort(test);
System.out.println();
bSort(test1, 5);
System.out.println();
int t = 0;
while(t < test.length)
{
System.out.println(test[t]);
t++;
}
System.out.println();
t = 0;
while(t < test1.length)
{
System.out.println(test1[t]);
t++;
}
System.exit(0);
}
publicstaticvoid BubbleSort(int[] data)
{
boolean Swaped =true;// set to true so while is executed once, too lazy to use do {} while()
if(data.length == 0 || data.length == 1)
{
System.out.println("List empty or no data to sort.");
}
else
{
int n = data.length;// n is the number of numbers to sort, so I have to do n - 1 comparisons
int temp;// temp var so I can swap vars
while(Swaped ==true)
{
Swaped =false;// could remove this if use do {} while()
for(int z = 0; z < (n - 1); z++)
{
if(data[z+1] < data[z])
{
temp = data[z+1];
data[z+1] = data[z];
data[z] = temp;
Swaped =true;
}
}
n--;// decrement number of comparisons to do
System.out.println("pass done! my algorithm!");
}
}
}
publicstaticvoid bSort(int data[],int n)// wikisource implementation
// pre: 0<=n <= data.length
// post: values in data[0..n-1] in ascending order
{
int numSorted=0;// number of values in order
int index;// general index
int temp;
while (numSorted < n)
{
// bubble a large element to higer array index
for (index=1; index < n-numSorted; index++)
{
if (data[index]<data[index-1])
{
// swap data[index] and data[index-1]
temp = data[index];
data[index]= data[index-1];
data[index-1] = temp;
}
}
// at least one more value in place
numSorted++;
System.out.println("pass done! their algorithm!");
}
}
}
I'm probably wrong anyway but I just wanted to share this with you and see what you will say about it.
Regards,
gamehack>
