Bubble Sort

Hi can someone plz explain the basics of a bubble sort thank you

you need two loops

one for the number of passes.
one inside (x) to do one pass
{
is array[x]>array[x+1] if so then swap them else leave them be.
}

number of passes is related to array size-1

I will be using the following sequence of numbers...

3 6 8 2 9 0 1 4 7 5

The basic action we're going to is compare two numbers, and if they're out of order, we'll switch them. We're going to do this to every pair of numbers... here's basically how the process goes

Code:

---

3 6 8 2 9 0 1 4
3 6 8 2 9 0 1 4 (3 & 6, no change)
3 6 8 2 9 0 1 4 (6 & 8, no change)
3 6 2 8 9 0 1 4 (8 & 2, swapped)
3 6 2 8 9 0 1 4  (8 & 9, no change)
3 6 2 8 0 9 1 4  (9 & 0, swapped)
3 6 2 8 0 1 9 4  (9 & 1, swapped)
3 6 2 8 0 1 4 9 (9 & 4, swapped)

---

7 steps for an awway of 8 elements... Notice that when we were running down the list with this process, we carried the largest number we had yet encountered with us...we started with the 6, picked up the 8, got the 9 after that, and carried the 9 untill the end. So we end up with the largest number, 9, at the end of the list. The code for this process is...

Code:

---

void runThroughList (int a[], int n)
{
 int i, temp;
 for (i = 0; i < n - 1; i++)
 {
  if (a[i] > a[i + 1])
  {
  // I will refer to the following 3 lines as the swap routine.
  temp = a[i];
  a[i] = a[i + 1];
  a[i + 1] = temp;
  }
 }
 return;
}

---

Now if we could just put the numbers before the 9 in order, then we'd have a sorted list, so we'll do the bubble sort on this part of the array...
3 6 2 8 0 1 4 (9)

So let's look what happens when we keep doing this sort on the left-over part of the array...
3 6 8 2 9 0 1 4
3 6 2 8 0 1 4 (9)
3 2 6 0 1 4 (8) (9)
2 3 0 1 4 (6) (8) (9)
2 0 1 3 (4) (6) (8) (9)
0 1 2 (3) (4) (6) (8) (9)
0 1 (2) (3) (4) (6) (8) (9)
0 (1) (2) (3) (4) (6) (8) (9)
(0) (1) (2) (3) (4) (6) (8) (9)
So, we just have to perform this sort on succesively smaller runs of the array. The code would look like this...

Code:

---

void bubbleSort (int a[], int n)
{
 int i;
 for (i = n; i > 0; i--)
 {
  runThroughList (int a[], int n);
 }
 return;
}

---

For the sake of efficiency however, we don't use a wrapper function for runThroughList. Notice that it really doesn't need it's own function. The only problem is that it needs it's own local variable for it's cound, and temp. We won't use i as the variable for it, since the bubbleSort function already has a variable i. We instead use j.

Code:

---

void bubbleSort (int a[], int n)
{
 int i, j, temp;
 for (i = n; i > 0; i--)
 {
  for (j = 0; j < i - 1; j++)
  {
  if (a[j] > a[j + 1])
  {
    temp = a[j];
    a[j] = a[j + 1];
    a[j + 1] = temp;
  }
  }
 }
 return;
}

---

The runTrhoughList function is practically copy and pasted. The only changes are that it's instances of 'i' were changed to 'j', and instead of n - 1 as the stopping condition, we had to use i - 1, since we no longer had i being passed to the function under the name 'n'.


An interesting improvement to the bubbleSort function is to make it recognize if the list is sorted on one of it's runs. Notice that in my example, the function could have stopped at
0 1 2 (3) (4) (6) (8) (9)
if it were able to realise this array was already sorted.

Hint: if a list is sorted, then there will be 0 swap routines in runThroughList.

The Quicksort is much faster if you have enough memory!!

klausi