Bubble Sort

• It requires n-1 passes to sort an array.
• In each pass every element a[i] is compared with a[i+1], for i=0 to (n-k-1), where k is the pass number and if they are out of order i.e. if a[i]>a[i+1], they are swapped.
• This will cause the largest element to move up or bubble up.
• Thus after the end of the first pass the largest element in the array will be placed in the last or nth position and on the next pass, the next largest element will be placed at position (n-1). This continues for each successive pass until the last or (n-1)th pass when the second smallest element will be placed at the second position.

Pass1.
Step 1. if a[0]>a[1] then swap a[0] and a[1].
Step 2. if a[1]>a[2] then swap a[1] and a[2].
…
Step n-1. if a[n-2]>a[n-1] then swap a[n-2] and a[n-1].
Pass2.
Step 1. if a[0]>a[1] then swap a[0] and a[1].
Step 2. if a[1]>a[2] then swap a[1] and a[2].
…
Step n-2. if a[n-3]>a[n-2] then swap a[n-3] and a[n-2].
…
Pass k.
Step 1. if a[0]>a[1] then swap a[0] and a[1].
Step 2. if a[1]>a[2] then swap a[1] and a[2].
…
Step n-k. if a[n-(k+1)]>a[n-k] then swap a[n-(k+1)] and a[n-k].
…
Pass n-1
Step 1. if a[0]>a[1] then swap a[0] and a[1].

Analysis of bubble sort

• First pass requires n-1 comparison
• Second pass requires n-2 comparison
• kth pass requires n-k comparisons
• Last pass requires only one comparison

Therefore the total comparisons are:

Algorithm

Bubblesort(a,n)

Begin
    for k=1 to (n-1) by 1 do
        for j=0 to (n-k-1) by 1 do
            if(a[j]>a[j+1]) then
                set temp=[j]
                set a[j]=a[j+1]
                set a[j]=temp
            endif
        endfor
    endfor
end

Complete Program

/**

 * Bubble sort

 * http://www.byteguide.com

 */

#include <stdio.h>

void bubblesort(int a[], int size)

{

    int temp, i, j;

    for (i=0; i<size-1; i++)

        for (j=0; j<size-1-i; j++)

            if (a[j]>a[j+1])

            {

                temp = a[j];

                a[j] = a[j+1];

                a[j+1] = temp;

            }

}

int main()

{

    int a[50], n, i;

    printf("How many elements in the array(max 50)?: ");

    fflush(stdout);

    scanf("%d", &n);

    puts("Enter array elements");

    for (i=0; i<n; i++)

        scanf("%d", &a[i]);

    bubblesort(a, n);

    puts("-----The sorted array is--------------");

    for (i=0; i<n; i++)

        printf("%d ", a[i]);

    printf("n");

    return 0;

}