Friday, 8 November 2013

This Bubble Sort Program will sort the array in ascending order. 

Bubble Sort is considered one of the simplest methods to sort an array of elements. In algorithmic approach, this is not the best method to use for sorting an array.

Worst Case Performance     : O(n2) 
Best Case Performance       : O(n)
Average Case Performance : O(n2) 

Logic
Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

Step by Step Example
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.

First Pass:
( 5 1 4 2 8 )  ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 )  ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 )  ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 )  ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 )  ( 1 4 2 5 8 )
( 1 4 2 5 8 )  ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )
( 1 2 4 5 8 )  ( 1 2 4 5 8 )


Facts | Q and A
  1. Bubble Sort is an internal sort
  2. Advantages     :   Very Simple to understand
  3. Disadvantages :   Very time-consuming and is not recommended for large size arrays.
  4. How will you determine the number of comparisons needed to sort the array?
    Answer:  Use the formula n-1.  Where n = the number of elements in the array.  So, if you have 25 elements in the array, bubble sort will compare 25-1 times.

#include <stdio.h>
#define SIZE 10
int main()
{
int array[SIZE];
int I;
int J;
int temp;
printf("Enter %d integer values\n\n", SIZE);
for(I = 0; I<SIZE; I++)
{
printf("Integer %d : ", I+1);
scanf("%d", &array[I]);
}
for(I = 0 ; I < ( SIZE - 1 ); I++)
{
for(J = 0 ; J < SIZE - I - 1; J++)
{
if(array[J] > array[J+1]) /* For decreasing order use < */
{
temp = array[J];
array[J] = array[J + 1];
array[J + 1] = temp;
}
}
}
printf("\n\nArray in Ascending Order : \n");
for(I = 0; I < SIZE ;I++)
printf("%d\n", array[I]);
return 0;
}
Find out other sorting algorithms in The Complete C Tutorial

References

Read More about Bubble Sort


Get Ebooks delivered to your email id

Comments

Subscribe to our channel

Facebook

Powered by Blogger.

Home | Contact Us | DMCA | Terms of Service | Privacy | Advertise

Maven Scientists