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)


Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: