Home > Programming > Sorting is easy!!!

## Sorting is easy!!!

One of the most common questions in many interviews is the sorting techniques. There are many sorting techniques, I am going to explain some of them in the coming posts.

We will start off with, the basic and simplest of all the sorting techniques, Bubble sort

Bubble Sort

Method: Bubble sort compares two adjacent elements and swaps if the first element is greater than the second one. After every pass the largest element in that pass bubbles up to the last position.

Example:

suppose the array elements are

5  7  8  3  2

pass1:

5  7 8  3  2  (compare 5 & 7)  (No Exchange)

5  7  8 3  2  (compare 7 & 8 )  (No Exchange)

5  7 8 3 2  (compare 8 & 3)  (Exchange)

5  7 3 8 2 (compare 8 & 2)  (Exchange)

5  7 3  2  8    (End of the pass1, the largest element is in its corresponding position the array)

pass2:

5 7 3 2 8 (compare 5 & 7)  (No Exchange)

5  7 3 2 8 (compare 7 & 3)  (Exchange)

5 3 7 2 8 (compare 7 & 2)  (Exchange)

5  3 2 7 8 (End of the pass2, the largest element in the pass2 is bubbled up to its corresponding position)

pass 3:

5  3 2 7 8 (compare 5 & 3)  (Exchange)

3 5  2 7 8 (compare 5 & 2)  (Exchange)

3  2 5 7 8 (End of the pass3, the largest element in this pass is bubbled up to its corresponding position)

pass 4:

3  2 5 7 8 (compare 3 &2 ) (Exchange)

2 3 5 7 8 (End of the pass4, all elements sorted)

Algorithm

#include<stdio.h>
#include<conio.h>
int main(void)
{
int a[]={1,12,2,11,3},i,j,n=5,temp;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<n;i++)
printf(“%d “,a[i]);
getch();
return 0;
}

compiled on: dev c++,  gcc, Turbo C

Analysis:

Worst Case: O(N2)        Average Case: O(N2)