sorting,merge,insertion and bubble sort(with C programming code provided)

Sorting

Sorting means arranging a set of data in the same order. In our daily life,we can see so many 

applications using the data in sorted order as telephone directory,merit,list,roll number etc.So ,

sorting is nothing but storage of data in sorted order(it can be in ascending or descending order).

Some Sorting techniques:

1. Bubble sort

2. Selection sort

3. Insertion sort

4. Merge sort

5. Quick sort

6. Heap sort

7. Radix sort

8. Shell sort

9. Bucket Sort

10. Counting sort

The main component in any sorting is the key comparison because most of the time we need to 

compare the key with elements in a list.The number of comparisons are more,then time for executing 

the program is also more.

Let ‘n’ be the input size of an array. If n increases,then time for execution also increases,So, execution 

time will be varying with different volumes of data.

The efficiency of any sorting technique can be represented using mathematical notations.

All the sorting technique efficiencies are in-between 0(n log n) to 0(n2).

Bubble sort:

The bubble sort technique for sorting a list of data in ascending order is as follows: 

In the first iteration, the first element of the array is compared with the second element. If the first element is 

found to be greater than the second element, they are interchanged. Now, the second element is compared 

with the third and interchanged if required. In the same way, comparison is done till the last element.At the 

end of first iteration, the largest element will be stored at the last position. 

In the second iteration, again the comparison is done from the first element to last-but-one element. At the 

end of this iteration, the second largest element will be placed in its proper position.

 If there are ‘n’ elements in the given list, then after (n-1) iterations, the array gets sorted.

 Consider the following list of integers to be sorted: 

A  =

28

20

30

15

5

        0      1        2        3      4

1st iteration:

28

20

30

15

5

Compare A[0] and A[1]  28>20 interchange

20

28

30

15

5

Compare A[1] and A[2]  28<30 no change

20

28

30

15

5

Compare A[2] and A[3]  30>15 interchange

20

28

15

30

5

Compare A[3] and A[4]  30>5 interchange

20

28

15

5

30

30 largest element in the array

2nd iteration:

20

28

15

5

30

Compare A[0] and A[1]  20<28  no change

20

28

15

5

30

Compare A[1] and A[2]  28>15 interchange

20

15

28

5

30

Compare A[2] and A[3]  28>5 interchange

20

15

5

28

30

28 second largest element

3rd iteration:

20

15

5

28

30

Compare A[0] and A[1]  20>15 interchange

15

20

5

28

30

Compare A[1] and A[2]  20>5 interchange

15

5

20

28

30

20 Third largest element

4th iteration:

15

5

20

28

30

Compare A[0] and A[1]  15>5 interchange

5

15

20

28

30

Sorted array

Algorithm:Bubblesort(A[0…..n-1])

A is an array of n elements to be sorted.

for pass =1 to n-1

    for j=0 to n-pass-1

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

temp=a[j]

a[j]=a[j+1]

a[j+1]=temp

End for

End for

Program:

#include<stdio.h>

#include<conio.h>

void main()

{

int a[10],n,i,temp,j;

clrscr();

printf("Enter the size of the array:");

scanf("%d",&n);

printf("\nEnter array elements:\n");

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

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

for(i=0;i<n;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;

}

}

}

printf("\nSorted list is:\n");

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

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

getch();

}

Time Complexities:

• Worst Case Complexity:O(n2)
  If we want to sort in ascending order and the array is in descending order then, the worst case

occurs.

• Best Case Complexity:O(n)
  If the array is already sorted, then there is no need for sorting.

• Average Case Complexity:O(n2)
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

• Space Complexity:O(1)

Space complexity is O(1) because an extra variable temp is used for swapping.

In the optimized algorithm, the variable swapped adds to the space complexity thus, making it O(2).

• Auxiliary Space: O(1)

Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.

Bubble Sort Applications

Bubble sort is used in the following cases where

• The complexity of the code does not matter.

• A short code is preferred.

Selection sort 

Selection sort is a simplest method of sorting technique. To sort the given list in ascending order, we will compare the first element with all the other elements. If the first element is found to be greater then the compared element, then they are interchanged. Thus at the end of first interaction, the smallest element will be stored in first position, which is its proper position. Then in the second interaction, we will repeat the procedure from second element to last element. The algorithm is continued till we get sorted list. If there are n elements, we require (n-1) iterations, in general.

A =

38

47

24

42

17

        0      1        2        3      4

   

1st iteration:

38

47

24

42

17

Compare A[0] and A[1]  38<47 no change

38

47

24

42

17

Compare A[0] and A[2]  38>24 interchange

24

47

38

42

17

Compare A[0] and A[3]  24<42 no change

24

47

38

42

17

Compare A[o] and A[4]  24>17 interchange

17

47

38

42

24

17 smallest element in the array

2nd iteration:

17

47

38

42

24

Compare A[1] and A[2] 47>38  interchange

17

38

47

42

24

Compare A[1] and A[3]  38<42  no change

17

38

47

42

24

Compare A[1] and A[4]  38>24  interchange

17

24

47

42

38

24 second smallest element

3rd iteration:

17

24

47

42

38

Compare A[2] and A[3]  47>42 interchange

17

24

42

47

38

Compare A[2] and A[4]  42>38 interchange

17

24

38

47

42

38 Third smallest element

4th iteration:

17

24

38

47

42

Compare A[3] and A[4]  47>42 interchange

17

24

38

42

47

Sorted array

Algorithm : Selection sort(A[0…..n-1])

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

{

    for(j=i+1;j<n;j++)

    {

if(a[ i]>a[j])

{

    temp=a[i];

                a[i]=a[j];

               a[j]=temp;

            }

    }

}

Program:

#include<stdio.h>

#include<conio.h>

void main()

{

int a[10],n,i,temp,j;

clrscr();

printf("Enter the size of the array:");

scanf("%d",&n);

printf("\nEnter array elements:\n");

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

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

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

{

for(j=i+1;j<n;j++)

{

if(a[ i]>a[j])

{

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

printf("\nSorted list is:\n");

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

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

getch();

}

Time Complexities:

• Worst Case Complexity: O(n2)
  If we want to sort in ascending order and the array is in descending order then, the worst case 

occurs.

• Best Case Complexity: O(n2)
  It occurs when the array is already sorted

• Average Case Complexity: O(n2)
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

The time complexity of the selection sort is the same in all cases. At every step, you have to find the 

minimum element and put it in the right place. The minimum element is not known until the end of the 

array is not reached.

• Space Complexity:

Space complexity is O(1) because an extra variable temp is used.

---

Selection Sort Applications

The selection sort is used when:

• a small list is to be sorted

• cost of swapping does not matter

• checking of all the elements is compulsory

• cost of writing to a memory matters like in flash memory (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)

Insertion sort

This sorting technique involves inserting a particular element in proper position. In the first iteration, 

the second element is compared with the first. In second iteration, the third element is compared with 

second and then the first. Thus in every iteration, the element is compared with all the elements before it. 

If the element is found to be greater than any of its previous elements, then it is inserted at that position and

 all other elements are moved to one position towards right, to create the space for inserting element. The 

procedure is repeated till we get the sorted list.

A =

38

47

24

42

89

        0      1        2        3      4

1st iteration:

38	47	24	42	17	Compare A[0] and A[1]  38<47,
					so consider 38 as  First position

38

47

24

42

17

First 2 elements are sorted order

2nd iteration:

38	47	24	32	89	Compare A[2] with A[1] and A[2]  24<38,
					so insert 24 at 0th position

24

38

47

32

17

First 3 elements are sorted order

3rd iteration:

24	38	47	32	89	Compare A[3] with A[1] and A[2] and A[3]
					32>24, nothing done                     32<38 insert 32 at 1st position

24

32

38

47

89

First 4 elements are in sorted order

4th iteration:

24	38	47	32	89	Compare A[4] with A[0….3] element
					89>24, nothing done                     89>38, nothing done                     89>47, nothing done                     89>32, nothing done

24

32

38

47

89

First 5 elements are in sorted order

Algorithm:insertion sort(A[0…..n-1])

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

{

item=a[i];

for(j=i-1;j>=0 && item<a[j];j--)

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

a[j+1]=item;

}

Program:

#include<stdio.h>

#include<conio.h>

void main()

{

int a[10],n,i,item,j;

clrscr();

printf("Enter the size of the array:");

scanf("%d",&n);

printf("\nEnter array elements:\n");

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

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

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

{

item=a[i];

for(j=i-1;j>=0 && item<a[j];j--)

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

a[j+1]=item;

}

printf("\nSorted list is:\n");

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

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

getch();

}

Time Complexities:

• Worst Case Complexity: O(n2)
  Suppose, an array is in ascending order, and you want to sort it in descending order. In this case, 

worst case complexity occurs.
Each element has to be compared with each of the other elements so, for every nth element, (n-1) 

number of comparisons are made.
Thus, the total number of comparisons = n*(n-1) ~ n2

• Best Case Complexity: O(n)
  When the array is already sorted, the outer loop runs for n number of times whereas the inner loop 

does not run at all. So, there are only n number of comparisons. Thus, complexity is linear.

• Average Case Complexity: O(n2)
  It occurs when the elements of an array are in jumbled order (neither ascending nor descending).

• Space Complexity

Space complexity is O(1) because an extra variable key is used.

Insertion Sort Applications

The insertion sort is used when:

• the array is has a small number of elements

• there are only a few elements left to be

Merge sort

The procedure for merge sort contains two main parts viz. divide and merge.

 Divide: The original array is divided into two equal parts. Then each sub-array is divided into two equal 

parts. This method is continued till each sub array contains only one element.

 Merge: The first element of first sub-array is compared with first element of the second sub-array. The 

lesser among these is put into result-array. The remaining element is compared with the second element 

of the other array. The procedure is continued till both the arrays get exhausted.

 The divide and merge parts are done recursively on given array to get sorted list.

Consider an array A[0...7] element:

	0	1	2	3	4	5	6
A=	35	10	15	45	25	20	40

Low = 0 , high = 6 , n = 7, mid = (low+high)/2 = (0+6)/2 = 3

Algorithm:

Algorithm:merge_sort(A,low,high)

//sort the elements in ascending order.

//low and high=first and last elements 

if(low<high)

mid=(low+high)/2

Call merge_sort(A,low,mid)

Call merge_sort(A,mid+1,high)

Call merge(A,low,mid,high)

Exit

Algorithm:merge(a,low,mid,high)

Set i=low

      j=mid+1

      k=low

while((i<=mid)&&(j<=high)) do

if(a[i]<a[j])

   Res[k]=a[i]

   k=k+1

   k=k+1

   i=i+1

else

              Res[k]=a[j]

  K=K+1

  J=J+1

End while

while(i<=mid)

Res[k]=a[i]

k=k+1

i=i+1

End while

while(j<=high)

Res[k]=a[j]

k=k+1

j=j+1

End while

For i=low to k-1

a[i]=Res[i]

End for

Return

Program:

#include<stdio.h>

#include<conio.h>

void merge(int a[10], int low,int mid,int high)

{

Int i,j,Res[30];

 i=low;

 j=mid+1; 

 k=low;

while((i<=mid)&&(j<=high)) 

{

if(a[i]<a[j])

{

   Res[k]=a[i]

   k++;

   i++;

}

else

{

              Res[k]=a[j]

  k++;

  j++;

}

}

while(i<=mid)

{

Res[k]=a[i]

  k++;

  i++;

}

while(j<=high)

{

 Res[k]=a[j]

  k++;

  j++;

}

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

a[i]=Res[i];

}

void merge_sort(int a[],int low,int high)

{

int mid;

if(low<high)

{

mid=(low+high)/2

merge_sort(A,low,mid)

merge_sort(A,mid+1,high)

merge(A,low,mid,high)

}

}

void main()

{

int a[20],n,i;

clrscr();

printf("Enter the size of array:");

scanf("%d",&n);

printf("\nEnter elements:\n");

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

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

merge_sort(a,0,n-1);

printf("\nSorted list is:\n");

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

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

getch();

}

Time Complexity:

• Best Case Complexity: O(n*log n)

• Worst Case Complexity: O(n*log n)

• Average Case Complexity: O(n*log n)

• Space Complexity:O(n)

Merge Sort Applications

• Inversion count problem

• External sorting

• E-commerce applications