New Page 0

Array at beginning:

After Pass #1:

After Pass #2:

After Pass #3:

After Pass #4:

Array at end of sort:

Bubble sort

The bubble sort or (sinking sort) because the smaller value gradually "bubble" their way upward the top (beginning) of the array like bubbles rising in water, while the larger values sink to the bottom (end) of the array.
A bubble sort repeatedly compares adjacent elements of an array, starting with the first and second elements, and swapping them if they are out of order. After the first and second elements are compared, the second and third elements are compared, and swapped if they are out of order. This continues until the end of the list is reached.
When the end is reached, elements one and two are compared again, and the process continues until all elements are in their proper order. The bubble sort knows that it is finished when it examines the entire array and no "swaps" are needed.
On the first pass , the largest value is guaranteed to move to the end of the array n-1.
On the second pass , the second largest value is guaranteed to move to location n-2.
On the n-1 pass , the n-1 largest value is guaranteed to move to the 2nd location in the array. This leaves the smallest value in location 1st location.
You need n-1 pass to sort an array on size n.

How to swap 2 values ?

How we can swap 2 values , a[i] and a[i+1] ? let say that a[i] contain 4 and a[i+1] contain 9 . Can we use the following code?

a[i]=a[i+1];

a[i+1]=a[i];

After executing the first line a[i]=a[i+1]; a[i] =9 and a[i+1] also contain 9 , where the 4 went ? You know now that you replaced it with 9 . Then what should we do ? We need an extra variable to hold (store) the value of 4, and the new code will be :

hold=a[i]; // store the value of 4

a[i]=a[i+1]; // a[i] and a[i+1] equals to 9

a[i+1]=hold; //a[i+1] equals to 4

Sorting Program

#include <stdio.h>
#define SIZE 10

int main()
{
int a[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
int i, pass, hold;

printf( "Data items in original order\n" );

for ( i = 0; i <= SIZE - 1; i++ )
printf( "%4d", a[ i ] );

for ( pass = 0; pass < SIZE - 1; pass++ ) /* passes */
   for ( i = 0; i < SIZE - 1; i++ )                 /* one pass */
        if ( a[ i ] > a[ i + 1 ] )             /* one comparison */
           {
             hold = a[ i ]; /* one swap */
             a[ i ] = a[ i + 1 ];
             a[ i + 1 ] = hold;
           }

printf( "\nData items in ascending order\n" );

for ( i = 0; i <= SIZE - 1; i++ )
printf( "%4d", a[ i ] );

printf( "\n" );

return 0;
}

Descent sort Example

The table below shows a list of numbers before, during, and after a bubble sort for descending order. Several passes have to be made through the array before it is finally sorted. The bubble sort is easy to program, but it is slower when compared to many other sorting algorithms.