Insertion Sort

By -

Sorting : -
Input: A Sequence of n numbers (a1,a2 …….an).
Output: A permutation (recording) <a’1,a’2,….a’n> of the input sequence such that a’1 <=a’2<=,….<=a’n.

Insertion Sort

Insertion sort is an efficient sorting algorithm for sorting a small number of elements. Insertion sort works the way people sort a hand of playing card. We start with empty hand and card face down on the table. We remove one card at a time from the table and insert it into the correct position in the left hand. For correct position of card we compare it with each of the card already in the hand in left.

algorthms-cormen


Algorithm 

INSERT-SORT(A)

  1. for j <-- 2 to length[A]
  2.   do key <-- A[j]
  3.      Insert A[j] into the sorted sequence A[1.... j-1]
  4.      i <-- 1
  5.      while i > 0 and A[j] > key
  6.          do A[i+1] <-- A[i]
  7.              i <-- i-1
  8.      A[i+1] <-- key



Ex: A = (5,2,4,6,1,3)  the index j indicate the current card being inserted into the hand. At the beginning  of each iteration of teh outer loop, which is indexed by j,the subarra consisting of elements A[1...j-1] constitute the currently stored hand, and elements A[j+1..n] correspond to the pile of card stil on table. A[1...j-1] elements oroginally at position 1 through j-1, but now in sorted order. 

Ex: A[6,5,3,1,8,7,2,4] 


wikipedia



Time Complexity: O(n*2)
Auxiliary Space: O(1)
Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
Sorting In Place: Yes
Stable: Yes


  C PROGRAM FOR INSERTION SORT ALGORITHM

        #include <stdio.h>
        int main()
        {
          int n, array[1000], i, j, t;
          printf("Enter number of elements: \n");
          scanf("%d", &n);
          printf("Enter %d integers\n", n);
          for (i = 0; i < n; i++)
            scanf("%d", &array[i]);
          for (i = 1 ; i <= n - 1; i++)
          {
            j = i;
            while ( j > 0 && array[j-1] > array[j]) {
              t          = array[j];
              array[j]   = array[j-1];
              array[j-1] = t;
              j--;
            }
          }
          printf("Sorted list in ascending order:\n");
          for (i = 0; i <= n - 1; i++)
          {
            printf("%d  ", array[i]);
          }
          return 0;
        }

    OUTPUT

        Enter number of elements:
        8
        Enter 8 integers
        67 -2 0 12 87 45 5 1
        Sorted list in ascending order:
        -2  0  1  5  12  45  67  87













Comments

Post a Comment

Popular posts from this blog

C program that contains a string XOR each character in this string with 0 ,127

By -
Write a C program that contains a string (char pointer) with a value \Hello World’. The program should XOR each character in this string with 0 and displays the result. Program: #include<stdlib.h> main() { char str[]="Hello World"; char str1[11]; int i,len; len=strlen(str); for(i=0;i<len;i++) { str1[i]=str[i]^0; printf("%c",str1[i]); } printf("\n"); } Q.2 Write a C program that contains a string (char pointer) with a value \Hello World’. The program should AND or and XOR each character in this string with 127 and display the result. PROGRAM: #include <stdio.h> #include<stdlib.h> void main() { char str[]="Hello World"; char str1[11]; char str2[11]=str[]; int i,len; len = strlen(str); for(i=0;i<len;i++) { str1[i] = str[i]&127; printf("%c",str1[i]); } printf("\n"); for(i=0;i<len;i++) { str3[i] = str2[i]^127; printf("%c",str3[i]); } pri
Read more

Queue in Data Structure(DS)

By -
Image
Queue Queues are data structures that follow the First In First Out (FIFO) i.e. the first element that is added to the queue is the first one to be removed. Elements are always added to the back(rear) and removed from the front. Think of it as  a line of people waiting for a bus. The person who is at the beginning of the line is the first one to enter the bus.   Basic features of Queue Like a stack, the queue is also an ordered list of elements of similar data types. A queue is a FIFO( First in First Out ) structure. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue  must be removed, to remove the new element. In a simple queue, there is a disadvantage after deleting element we cannot insert the element in the queue because of insertion  is possible from the rear but deletion is performed from the front.                                           insertion                                     ------------------
Read more

Implementation of stack Using Array

By -
Implementation  of stack Using Array #include<stdio.h> void pop(); void push(); void display(); int i,n,ch=0,top,item,stack[50]; int main() {     printf("Enter the number of element in Stack:\t");     scanf("%d",&n);     top=-1;     printf("Stack Operations");     printf("\n1.Push\n2.Pop\n3.Display\n4.Exit\n");    do     {         printf("Enter the choice: ");         scanf("%d",&ch);         switch(ch)         {             case 1:push();                    break;             case 2:pop();                    break;             case 3:display();                    break;             case 4:exit(0);                    break;             default:printf("!!Wrong choice!!\n");         }     }     while(ch!=4);     return 0; } void push(int item) {     if(top==n-1)         printf("Overflow\n");     else     {        
Read more