Sorting program #3 : Insertion sort !

Insertion_sort(k,N): Vector K with N elements

Brief Explanation :

    Here we maintain our array in two sub-arrays , i.e. 1. Sorted 2. Unsorted
    Initially , first element is the only member of sorted array.
    Then we move further , pick next element i.e. first element of the unsorted array and insert it to appropriate position .

    This is how , the sorted array is growing and unsorted is shrinking with every pass and hence at last the whole array is sorted .

---

ALGO :-

  o) PASS - pass number and index of first unsorted data
  o) HOLE - Index of element to be pick up for insertion
  o) VALUE - The element to picked up for insertion

---

step 1 : [loop on PASS index]
    Repeat thru step 4 for PASS = 1,2,...,N
   
step 2 : [Initialize VALUE and HOLE]
    VALUE <- K[PASS]
    HOLE <- PASS

step 3 : [Inserting the current value in sorted sub-array at appropriate index]
    Repeat steps 3.1 and 3.2 while HOLE>0 and K[HOLE-1]>VALUE
   
    3.1 : [Shifting the greater element to right side]
        K[HOLE] <- K[HOLE-1]
    3.2 : [Shifting the index HOLE to left ]
        HOLE <- HOLE-1

step 4 : [Inserting value after necessary shifts made]
    K[HOLE] <- VALUE
       
step 4 : [Finished] 

---

By following algorithm you can easily implement a program for it . Else , You can refer the following code and check the implementation !

---

Implementation of Insertion sort in C : 

---

#include<stdio.h>
#define max 200

int main()
{   
    int a[max],n,i;   
    printf("Enter the number of elements : ");
    scanf("%d",&n);
    printf("Enter array elements :\n");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);   
    }
   
    //insertion sort
    int value,hole,k;
    for(k=1;k<n;k++)
    {
        value = a[k];/*Here a[k] is the element which is to be inserted into sorted part*/
        hole = k;
        while(hole>0 && a[hole-1]>value)//shifting all greater elements
        {
            a[hole] = a[hole-1];
            hole--;
        }
        a[hole] = value;/*now, hole is the perfect index where we can insert the value.*/
    }   
    printf("Array : ");
    for(i=0;i<n;i++)
    {
        printf(" %d ",a[i]);   
    }
    printf("\n");
}

---

Thanking you !

Sorting : Arranging the data

Formally ,

Sorting is arranging the elements of data/list/arrays in increasing or decreasing order of desired property .

In general maximum sorting orders are numerical or lexicographical .

Now , the question arise : Why sorting ?

Consider an array of data having 2^100 elements in it .

Now if we need to pick a particular element from it , we need to perform a search operation . If data is sorted , we'll perform binary search and if data is not sorted we'll perform linear search .

Lets check the difference between binary search and linear search !

1. Linear search 

A linear search is a simple searching algorithm. It searches the desired element by comparing the each element with the given element in the sequence . So , in the worst case , it will make n number of comparisons . Particularly for this example , it will perform 2^100 comparisons. And if one comparison is done in microsecond , still it will take years to complete the process .

2. Binary Search

Unlike linear search binary search can be performed on sorted data only . It follows the logic as follows :

• It compares the middle element first 
• If the required element is greater or smaller than that it skips the other half 
• In every step it checks with this "middle element" logic.

So , number of searches reduces to log ₂ n for total n elements !

• So , for the required case it will make log ₂ n = log ₂ 2^100 = 100 comparisons only!

So , for same case , i.e. microsecond for comparison the whole procedure will be completed in less than a millisecond !

So , clearly we can conclude that sorting make this much difference .

Now , the main question : How to sort ?

There are many sorting algorithms like :

• Bubble sort 
• Selection sort
• Quick sort 
• Insertion sort 
• Merge sort .
• Radix sort etc.

We , in our future posts will discuss few of them in detail .

---

Thank you !

Sorting program #1 : Bubble sort !

Bubble Sort :

        Name suggest that there must be something bubbling in the process . If you think so , you are correct . For array of n elements the comparison is done (n-1)*(n-1) times . Means every single element is compared with its adjacent element and swapped(if needed)  n-1 times.

For understanding in better way -

---

ALGO :- Bubble_sort(K,N)

o) Given a vector K with N elements .

o) PASS - pass counter
o) LAST - position of the last unsorted element
o) I - index of the vector element
o) SWAP - for counting the number of swapping made

step 1 : [Initialize]
    LAST <- N (Entire list is unsorted initially)
   
step 2 : [Loop on pass index]
    Repeat thru step 5 for PASS = 1,2,3,...,N-1

step 3 : [Initialize swapping counter for this PASS]
    SWAP <- 0
   
step 4 : [Perform pairwise comparisons on unsorted elements]
    Repeat for I = 1,2,3,...,LAST-1
    If K[I] > k[I+1]
    Then K[I] <-> k[I+1]
         SWAP = SWAP + 1

step 5 : [Where any swapping done ?]
    If SWAP = 0
    Then Return ( Sorted )
    Else LAST = LAST -1 (reduce the size of unsorted part)

step 6 : [Finished]
    Return (Maximum nnumber of passes required)

Isn't is so simple ?

Try to make the C program according to this algorithm or copy the code given below :

---

C program : Bubble sort 

---

#include < stdio.h > 
int main()
{
    int i,j,k,n,temp,flag;
    printf("Enter number of elements \n");
    scanf("%d",&n);
    int array[n];
    printf("Enter elements : \n");
    for(i=0;i < n;i++)
    {
        printf("Element %d : ",i+1);
        scanf("%d",&array[i]);
    }
    for(i=0;i < n-1;i++)
    {   flag = 0;
        for(j=0;j < n-i-1;j++)
        {

            if(array[j] > array[j+1])
            {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                flag = 1;
            }
        }
        if(flag == 0)
        {
            break;
        }
    }

    printf("\n\nShorted list:\n");
    for(i=0;i < n;i++)
    {
        printf(" %d ",array[i]);
    }

}

Extra :

Bubble sort is very easy to understand and follow , but there are limitations regarding to time complexity of sorting algorithm .

for detailed information about time complexity and improvisation in bubble sort , go through my article "Analysis of Bubble Sort."

Link to :
* Selection Sort 

---

Thank you !

Sorting program #2 : Selection Sort

Selection sort 

is also very easy and time taking fundamental algorithm of  sorting .
The logic behind this is simple . Like , we need to select the smallest element and assign that value to the appropriate index .
It follows the following algorithm :

* Selection sort :

Given a vector K with N elements :
 o) PASS : pass number position of the first element of vector to be examined in pass
 o) iMin : index of the smallest number
 o) I :    idices !

---

Step 1 : [Loop on pass index]
    Repeat thru step 4 for PASS = 1,2,3,...,N-1
   
Step 2 : [Initialize minimum index]
    iMin = PASS
   
Step 3 : [Make a pass and obtain element with smallest value]
    Repeat for I = PASS+1,PASS+2,...,N
    If K[I] < K[iMin]
    Then iMin = I
   
Step 4 : [Exchange elements]
    If iMin =/= PASS
    Then K[PASS] <-> K[iMin]
   
Step 5 : [Finished]

Try to write a code for it , else copy the code given below and check !

---

C Program : Selection Sort 

---

//selection sort
#include < stdio.h >
void main()
{
    int i,iMin,j,k,temp,n;// declaring required variables 
    printf("Enter number of elements :");
    scanf("%d",&n);
    int array[n];
    printf("Enter the elements :\n");
    for(i=0;i < n;i++)//getting input from user as usual
    {
        printf("Element %d : ",i+1);
        scanf("%d",&array[i]);
    }
    /* Selection sort */
    for(i=0;i < n-1;i++)// outer loop : lets call it a pass
    {
        iMin = i;/* Changing index for minimum of the array elements */
        for(j=i+1;j < n;j++)/*for j < i+1 , all indices are sorted with the appropriate value*/
        {
            if(array[j] < array[iMin])/* choosing the minimum */
            {
                iMin = j;
            }
        }
        temp = array[i];
        array[i] = array[iMin];/*Swapping of minimum value to appropriate index*/
        array[iMin] = temp;
    }
    printf("Here is the sorted array !\n");// printing result 
    for(i=0;i < n;i++)
    {
        printf("%d ",array[i]);
    }

}

---

For addition details :

You can always see what computer is doing .

For ex. add another loop printing the array after every pass , like this ->

Keep in mind , there is a chance of silly mistake 

### Don't use iterator " i " for printing intermediate results , this disturbs the value of i and cause an Error .

After printing intermediates we can clearly see that , each time the lowest one is replaced to an appropriate index !

I hope you enjoyed reading this !

Any suggestions and comments are always accepted .

---

Thank you !

Analysis of Bubble Sort :

Here is the observable :

Analysis of Bubble Sort !

For understanding the algorithm of bubble sort .
click the link below :
Bubble sort

In several ways we can modify our algorithm , this first is :

1. Clearly the sorting is done by bubbling the greatest unsorted element to a higher indices each time . So , this makes a two different parts of the array .

1. Sorted 
2. Unsorted 

If we put a loop to print the array[] , after each pass , we will clearly understand how the list is divided in two parts . 1. sorted 2. unsorted .

So, What if we exclude the the sorted portion in our algorithm . For sure this will reduce the number of loops and hence time !

As with every loop elements are getting sorted from the end , We can decrease the running of inner loop with every pass . 

This can be done by replacing condition

j<n-1 with j<n-i-1 !

Eg.

This will reduce the compilation time and result is still as it was !

2. Another thing we can do is adding a variable - "flag".

Our intention is to terminate the loop if the list is sorted .

We can do this by checking , whether swapping is done or not . Like , if swapping is not done means the list is sorted , and we can terminate the loop .

So , for this ,

•  initialize a variable "flag = 0" , in outer for loop.
• Change value of flag to 1 , "flag = 1" in the Swapping block .
• and In outer for loop at the end give a conditional if statement such as , if flag=0 -> break;
• This will terminate the loop if no swapping is done, i.e. If list is already sorted !

Ex.

So , In this way Bubble sort  WAS so time consuming , we made it better than before !

Any suggestions and modifications are always accepted !

link to :
1.Bubble sort
2.Selection sort 

---

Thank you !