Talk:Algorithm Implementation/Sorting/Bubble sort

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

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

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;
   }
}

C

Instead of using two for loops, one can choose do...while for the same job. The algorithm for it would be:

void BubbleSort (int a[], int length)
{
	int i, swapHappened;
	
	do {
	swapHappened = 0;
	for (i = 0; i < length - 1; i++)
		{
			if (a[i] > a[i + 1]) // this just swaps and changes swapHappenedd to true
			{
				a[i]^=a[i + 1];
				a[i + 1]^=a[i];
				a[i]^=a[i + 1];
				swaphappened = 1;
			}
		}

	} while (swapHappened == 1);
}

Once can note that, the variable j that was used to run a loop is no longer required. At the same time, swapHappened is used as a switch.
acagastya  ✍️ Dicere Aliquid 🐾 18:15, 2 February 2016 (UTC)

Ada Bubble Sort

The listed implementation for Ada isn't bubble sort.

What is currently happening: If the last integer in the array is less than the currently indexed at J, swap them. This means that if we have a 10 integer array, the 10th gets swapped multiple times per iteration. This doesn't happen with bubble sort.

Bubble sort says if the *next* element after J is less, then swap. In other words, the Ada implementation isn't comparing adjacent elements as it should, but always the last element with the currently indexed element.

I am not experienced enough with Ada to correct this myself.

2605:A601:AD74:2D00:B508:A447:E481:3CAE (discuss) 11:29, 16 October 2020 (UTC)