Talk:Algorithm Implementation/Sorting/Bubble sort

From Wikibooks, the open-content textbooks collection

I found a number of mistakes in the VBA example (atleast when it is run in VB6):

1. Array is a reserved word, and cannot be usede as a variable.
2. This causes a subscript out of rage error when it goes Array(J + 1)
3. The N argument is not needed, UBound() can return the number of arrauy elements.

Anyway, I fixed it up, the following example runs fine in VB6 enterprise:

Sub bubble(bblarray() As Integer)

'N is the number of integers in the array'
'0 to N-1'
 
Dim I, J, P, Temp As Integer
 
For I = UBound(bblarray()) To 0 Step -1
    P = 0
    For J = 0 To I - 1
         If bblarray(J) > bblarray(J + 1) Then
            Temp = bblarray(J)
            bblarray(J) = bblarray(J + 1)
            bblarray(J + 1) = Temp
         Else
            P = P + 1
         End If
         If P = I Then GoTo premend
    Next J
Next I

'premend = premature ending = all integers are allready sorted'
premend:

End Sub

I dunno if it is compatible with VBA though... anyone know? MichaelBillington 02:36, 16 July 2006 (UTC)

Thanks for correcting that was my bubblesort/mistake and I wrote it for VBA (just badly changed the variables when posting here) so it works in VBA. Cheers YB 0:10 16 November 2006

[edit] Bubblesort Java implementation

Hi there,

I found an error in the Java Implementation. The problem is that numberOfTimesLooped is incremented on the inner loop instead of the outer...

Here is the corrected version (which also has some questionable performance enhancements which were required for my purpose), please somebody else insert it because I just stumbled upon this page and don't have a clue what the rules for commiting stuff here are...

public static void bubbleSort (int[] data) {
	boolean isSorted;
	int numberOfTimesLooped = 0;
	do {
		isSorted = true;
		int a = data[0];
		int b;
		for (int i = 1; i < data.length - numberOfTimesLooped; i++) {
			b = data[i];
			if (b < a) {
				data[i] = a;
				data[i - 1] = b;
				isSorted = false;
			}
			else
				a = b;
		}
		numberOfTimesLooped++;
	} while (!isSorted);
}

- Jannik Jochem, 2007-07-20

[edit] New algorithm for Bubblesort

I've found a slightly better implementation of bubblesort, that in the average case will have a slightly better round time. The theory behind it is the same as having a flag that checks whether or not it made any swaps, and if it has, it exits immediately. However, this will keep track of the last place where it made the swap, and cut off the list after that, when it goes through. The benefit of this implementation is that if a portion of the latter-part of your list is already sorted, it'll cut that off. My implementation of it in C# will show you what I mean.

public static void BubbleSort(LinkedList<T> list)
{
   LinkedListNode<T> tail = list.Last;
   while(tail != list.First)
   {
      LinkedListNode<T> swapped = list.First;
      LinkedListNode<T> current = list.First;
      while(current != tail && swapped != tail)
      {
         if(current.Value.CompareTo(current.Next.Value) > 0)
         {
            swapped = current.Next;
            list.Remove(swapped);
            list.AddBefore(current, swapped);
         }
         else
            current = current.Next;
      }
      tail = swapped;
   }
}