sorting

sorting:

sorting is a process of arranging items in either ascending or descending order. This process can be implemented by different types of algorithms. 

 

Different types of basic sorting algorithms are as follows:

• bubble sort

• selection sort

• insertion sort 

• merge sort

• quick sort

• count sort

bubble sort:

    This algorithm is based on repeatedly comparing the adjacent elements and switching their positions if they exist in wrong order. The code for bubble sort is as follows:

void bubble_sort(int a[], int n)

{

  int temp;

  for(int k=0;k<n-1;k++)

  {

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

     {

       if(a[i]>a[i+1])

       {

          temp=a[i];

          a[i]=a[i+1];

          a[i+1]=temp;

       }

     } 

  }

}

    

pictorial representation of the above code is as follows:

This bubble sort compares with the adjacent element. In the first step 7 is compared with 4 and since 7 is greater than 4 both got swapped. and if it is in ascending order the elements stay on the same position and the process repeats for the next iteration.

  The complexity of bubble sort is worst and average case i.e,, 0(n^2). This is because for every iteration element needs to be verified.

selection sort:

    This algorithm is based on the idea of selecting the maximum or minimum element in the given unsorted list of array and placing the selected element in the correct position to get a sorted array.

consider the given array of elements a[]={7,5,4,2}. now we need to sort the given array in ascending order.

 now, according to selection sort algorithm we need to select the minimum element in the list. minimum element in the list is 2. so we should replace it with the first position. i.e, 2 will be swapped with 7. now we should find the second minimum element in the list and replace it with a[1] th position. this process should be repeated until we get the exact result.

let's have look on the code:

n= number of elements in the array

code:

void selection_sort(int a[],int n)

{

  int minimum;

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

  {

     minimum=i;

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

     {

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

       {

         minimum=j;

       }

     }

     swap(a[minimum],a[j]);

  }

}

here is the pictorial representation of the above pseudo code:

complexity:

      To find the minimum number of  n elements , we require (n-1) number of comparisons. Putting minimum element to it's proper position size of unsorted array reduces to n-1 and then to n-2 comparisons are required to find the minimum in the unsorted array. therefore complexity is o(n^2).

insertion sort:

 According to this algorithm the element has to be inserted at it's correct position after each iteration. It consumes one element from the input elements removes it and find the correct position.i.e, where it  belongs in the sorted list and places it.

   It checks the current element with the largest value in the sorted list. If the current element is larger, then it leaves the element as it's place and moves to the next element, else it finds it's current position in the sorted list and moves it to that position.

implementation of the code is as follows:

pseudo code:

void insertion_sort(int a[], int n )

{

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

  {

    int temp=a[i];

    int j=1;

    while(temp<a[j-1] && j>0)

     {

       a[j]=a[j-1];

       j=j-1;

     }

    a[j]=temp;

  }

}

pictorial representation of the above pseudo code is as follows:

Since 7 is the first element and it is the largest element, so it's position cannot be changed.since 4 is less than 7 it changes it's position to first. and this process repeats and so on we can get the sorted list.

complexity:

o(n^2) is the final complexity of insertion sort.

merge sort:

  This sorting algorithm depends on divide and rule principle. first divide the array into two halves. Repeatedly sort each half, then merge two halves again.

let's take an example to solve merge sort.

a[]={9,7,8,3,2,1}

In this array "a" first divide it into two halves a1={9,7,8} and a2={3,2,1}. again divide these two halves into sub halves. Repeat the process until they cannot be divided. sort all the parts. now compare a1,  a2 and merge them.