Sorting in C Programming

Introduction

  • Arranging the data in ascending or descending order is known as sorting.
  • Sorting is very important from the point of view of our practical life.
  • The best example of sorting can be phone numbers in our phones. If, they are not maintained in an alphabetical order we would not be able to search any number effectively.

Sorting Methods

Many methods are used for sorting, such as:
1. Bubble sort
2. Selection sort
3. Insertion sort
4. Quick sort
5. Merge sort
6. Heap sort
7. Radix sort
8. Shell sort

Generally a sort is classified as internal only if the data which is being sorted is in main memory.

It can be external, if the data is being sorted in the auxiliary storage.

The user will decide which sorting method can be used depending on the following conditions:
a) Time required by a programmer for coding a particular sorting program.
b) The machine time required for running the program.
c) Space required by the program.

Let us see the sorting methods one by one.

1. Bubble sort

  • This is one of the most simple algorithm.
  • The logic for this sort is that if the numbers are to be arranged in an ascending order then the largest number will be pushed at the end of the list.
  • This process will be continued till all the numbers are placed in the proper order.
  • Every number will be scanned with the succeeding number and they are swapped if the top number is larger than the succeeding number.
  • If the list is scanned once, it is called as a pass.
  • Even if the list is passed once only the largest number is pushed at the end the rest of the numbers are still not placed.
  • For this, we may have to repeat this step many times to get the list sorted properly.

Program for bubble sort

void bubblesort(int a[ ], int n)
{
     int p, c, i, j, temp;
     p = n-1;
     c = n;
     for(i=1; i<=p; i++)
     {
          for(j=1; j<=c; j++);
          {
               if(a[j] > a[j+1])
               {
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
               }
          }
     }
}

2. Selection sort

  • This method of sorting is faster than the bubble sort as the movement of data is minimized.
  • Say we want to arrange data in ascending order, the largest number is selected and placed at the end of the list.
  • When the next pass takes place the second largest number is selected and placed second last.
  • This process is repeated until all the elements are placed in the correct order.
  • With each pass the elements are reduced by 1 as one element is sorted and placed in a position.

Program for selection sort

void selectionsort (int x[], int n)
{
     int i, index, j, l;
     for (i=n ; i>0; i--)
     {
           l=x[1];
           i=1;
           for(j=1; j<=i; j++)
           {
                if(x[j] > l)
                {
                      l = x[j];
                      index = j;
                }
           }
           x[index] = x[i];
           x[i]=l;
     }
}

3. Insertion sort

There are three types of insertion sort:
a) Simple insertion sort
b) List insertion sort
c) Insertion sort using binary search.

  • It is more efficient than bubble sort.
  • The logic for this is that every element is picked up and inserted in the proper place i.e. if we pick up one element for inserting, all the other elements will be put in the proper order.

Program for simple insertion sort

void insertionsort (int x[], int n)
{
     int i,j,k;
     for (i=1 ; i<=n; i++)
     {
          k=x[i];
          for(j=i-1; j>=i && k<x[j]; j--)
          {
                x[j+1] = x[j];
          }
          x[j+1] = y;
     }
}


Note: The above three sorting methods i.e. bubble sort, selection sort and insertion sort are the most common methods used for sorting. All the other methods are used rarely.
▲