Sorting program #1 : Bubble sort !

Bubble Sort :

        Name suggest that there must be something bubbling in the process . If you think so , you are correct . For array of n elements the comparison is done (n-1)*(n-1) times . Means every single element is compared with its adjacent element and swapped(if needed)  n-1 times.

For understanding in better way -

---

ALGO :- Bubble_sort(K,N)

o) Given a vector K with N elements .

o) PASS - pass counter
o) LAST - position of the last unsorted element
o) I - index of the vector element
o) SWAP - for counting the number of swapping made

step 1 : [Initialize]
    LAST <- N (Entire list is unsorted initially)
   
step 2 : [Loop on pass index]
    Repeat thru step 5 for PASS = 1,2,3,...,N-1

step 3 : [Initialize swapping counter for this PASS]
    SWAP <- 0
   
step 4 : [Perform pairwise comparisons on unsorted elements]
    Repeat for I = 1,2,3,...,LAST-1
    If K[I] > k[I+1]
    Then K[I] <-> k[I+1]
         SWAP = SWAP + 1

step 5 : [Where any swapping done ?]
    If SWAP = 0
    Then Return ( Sorted )
    Else LAST = LAST -1 (reduce the size of unsorted part)

step 6 : [Finished]
    Return (Maximum nnumber of passes required)

Isn't is so simple ?

Try to make the C program according to this algorithm or copy the code given below :

---

C program : Bubble sort 

---

#include < stdio.h > 
int main()
{
    int i,j,k,n,temp,flag;
    printf("Enter number of elements \n");
    scanf("%d",&n);
    int array[n];
    printf("Enter elements : \n");
    for(i=0;i < n;i++)
    {
        printf("Element %d : ",i+1);
        scanf("%d",&array[i]);
    }
    for(i=0;i < n-1;i++)
    {   flag = 0;
        for(j=0;j < n-i-1;j++)
        {

            if(array[j] > array[j+1])
            {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                flag = 1;
            }
        }
        if(flag == 0)
        {
            break;
        }
    }

    printf("\n\nShorted list:\n");
    for(i=0;i < n;i++)
    {
        printf(" %d ",array[i]);
    }

}

Extra :

Bubble sort is very easy to understand and follow , but there are limitations regarding to time complexity of sorting algorithm .

for detailed information about time complexity and improvisation in bubble sort , go through my article "Analysis of Bubble Sort."

Link to :
* Selection Sort 

---

Thank you !