Thursday, November 24, 2011

Array [VI] [Insertion Sort!]


Insertion Sort - Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In this technique instead swapping value is shifted to the correct position.
Worst-Case Analysis
·       The outer loop is always done N – 1 times
·       The inner loop does the most work when the next element is smaller than the past elements
·       On each pass, the next element is compared to all earlier elements, giving:
·       Running time in this case?
·       inner loop test executes p+1 times for each p
           N-1
              Σ i = 2 + 3 + 4 + … + N = θ(N2)
           i=1
Insertion sort is O(N2) on average
Insertion Sort Source Code and Algorithm.

#include <stdio.h>
#include <conio.h>

// INSERTION SORT

//Function Called for Sorting

  void InsertionSort(int a[],int size)
      {
           int i,j;
           int e;
           for(i=1;i<size;i++)
              {
                   e = a[i];
                   j=i;
                   while(j>0 && a[j-1]>e)
                        {
                            a[j] = a[j-1];
                            j--;
                        }
                   a[j]=e;
              }
      }

//Main Function

  void main()
      {
           int i,n,c=0;
           int a[20];
           clrscr();
           printf("\n\tEnter size of Array [Below 20] : ");
           scanf("%d",&n);
           for(i=0 ;i<n;i++)
              {
                   printf("\tEnter Nos. at [%d] : ",i);
                   scanf("%d",&a[i]);
              }
           printf("\n\tBefore Sort : ");
           for(i=0 ;i<n;i++)
              {
                   printf("%d  ",a[i]);
              }
           printf("\nA\tfter Sort : ");
           InsertionSort(a,n);
           for(i=0 ;i<n;i++)
              {
                   printf("%d  ",a[i]);
              }
           getch();
      }

Algorithm.

  for i ← 1 to n-1 do
      do
           value ← A[i];
           j ← i;
           while j>0  &&  A[j-1] > value
              do
                   A[j ] ← A[j-1];
                   j ← j - 1;
           end
           A[j] ← value;
      end for i
Insertion Sort using Recursive Function.

#include <stdio.h>
#include <conio.h>

//Recursive Insertion Sort

  int a[20];

// Function for inner loop

  void Isrt(int a[], int j, int num)
      {
           int flag = 0;
           if (a[j] > num)
              {
                   a[j + 1] = a[j];
                   if (--j < 0)
                        {
                            flag = 1;
                        }
              }
           else
              {
                   flag = 1;
              }
           if (flag)
              {
                   a[j + 1] = num;
              }
           else
              {
                   Isrt(a, j, num);
              }
}

// Finction for outer loop

  void ISort(int a[], int n)
      {
           static int i;
           int j = i, num;
           if (++i < n)
              {
                   num = a[i];
                   Isrt(a, j, num);
                   ISort(a, n);
              }
           else
              {
                   i = 0;
              }
      }

// Main function
  void main()
      {
           int i, j, n,t;
           int a[20];
           clrscr();
           printf("\n\tEnter Size of Arry (Below 20) : ");
           scanf("%d",&n);
           for(i=0;i<n;i++)
              {
                   printf("\nEnter %d Values ",n);
                   scanf("%d",&a[i]);
              }
           printf("\n\tOriginal  : ");
           for(i=0;i<n;i++)
              {
                   printf(" %d ",a[i]);
              }
           ISort(a, n);
           printf("\n\tSorted    ");
           for(i=0;i<n;i++)
              {
                   printf(" %d  ",a[i]);
              }
           getch();
      }

Posted by at No comments:
Labels:

Thursday, November 17, 2011

Array [V] [Bubble Sort, Selection Sort]



Bubble Sort –  Bubble sort is a simple sorting algorithm. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass.

•         Let n =  array length = size of the array
•         The outer loop is executed n-1 times
•         Each time the outer loop is executed, the inner loop is executed
–        Inner loop executes n-1 times at first, linearly dropping to  just once
–        On average, inner loop executes about n/2 times for each execution of the outer loop
–        In the inner loop, the comparison is always done (constant time), the swap might be done (also constant time)
•         Result is n * n/2 * k, that is, O(n2/2 + k) = O(n2)

Complexity :
Best-Case Analysis
•         If the elements start in sorted order, the for loop will compare the adjacent pairs but not make any changes
•         So the swapped Elements variable will still be false and the while loop is only done once
•         There are N – 1 comparisons in the best case
Worst-Case Analysis
•         If in the best case the while loop is done once, in the worst case the while loop must be done as many times as possible
•         Each pass of the for loop must make at least one swap of the elements
•         The number of comparisons will be:
Average-Case Analysis
•         We can potentially stop after any of the (at most) N – 1 passes of the for loop
•         This means that we have N – 1 possibilities and the average case is given by where C(i) is the work done in the first i passes
•         On the first pass, we do N – 1 comparisons
•         On the second pass, we do N – 2 comparisons

Bubble Sort Source Code and Algorithm.

#include <stdio.h>
#include <conio.h>

//BUBBLE SORT

//Function to Sort the List
  void BubbleSort(int a[],int size)
      {
           int i,j,tmp;
           for(i=0;i<size;i++)
              {
                   for(j=0;j<size-i-1;j++)
                        {
                            if( a[j]>a[j+1] )
                                {
                                      tmp = a[j];
                                      a[j] = a[j+1];
                                      a[j+1] = tmp;
                                }
                        }
              }
      }

//Main Function
  int main()
      {
           int i,n,c=0;
           int a[20];
           printf("\n\tEnter size of Array [Below 20] : ");
           scanf("%d",&n);
           for(i=0 ;i<n;i++)
              {
                   printf("\tEnter Nos. at [%d] : ",i);
                   scanf("%d",&a[i]);
              }
        printf("\n\tBefore Sort : ");
        for(i=0 ;i<n;i++)
           {
              printf("%d  ",a[i]);
           }
        printf("\n\tAfter Bubble  Sort : ");
        BubbleSort(a,n);
        for(i=0 ;i<n;i++)
           {
              printf("%d  ",a[i]);
           }
      getch();
  }
Algorithm

  for i ← 0 to n-1
      do
      for j ← 0 to n-i-1
      do
           If A[j] > A[j-1]  then
                        A[j-1]↔ A[j]
            end for j
  end for i
Sorting string using bubble sort technique.

#include <stdio.h>
#include <conio.h>
#include <string.h>

//String Sorting

  int main()
      {
           char arr[5][20]={"Delhi","Kolkata","Bangalore","Agra","Mumbai",};
           char temp[20];
           int n=5,i,j;
           printf("\n\n\tOriginal  : ");
           for(i=0;i<n;i++)
              {
                   printf("%s  ",arr[i]);
              }
           for(i=0; i<n-1; i++)
              {
                   for(j = 0; j<n-i-1;j++)
                        {
                            if(strcmpi(arr[j],arr[j+1])>0)
                                {
                                      strcpy(temp,arr[j]);
                                      strcpy(arr[j],arr[j + 1]);
                                      strcpy(arr[j + 1] ,temp);
                                }
                        }
              }
           printf("\n\n\tSorted List  : ");
           for(i=0;i<n;i++)
              {
                   printf("%s  ",arr[i]);
              }
      getch();
  }
Bubble Sort Using Recursive Function.

#include <stdio.h>
#include <conio.h>

//Recursive Bubble Sort

  int n;

//Recursive Function for Second Loop
  void bsort(int a[],int j,int k)
      {
          int t;
          if(k<n-j-1)
              {
                   if(a[k]>a[k+1])
                        {
                            t=a[k];
                           a[k]=a[k+1];
                            a[k+1]=t;
                        }
                        bsort(a,j,k+1);
                   }
      }

//Recursive Function for First Loop
  void sort(int a[],int i)
      {
         
          if(i<n-1)
              {
                   bsort(a,i,0);
                    sort(a,i+1);
              }
      }

//Main Function
  int main()
      {
           int a[50],i;
           printf("\n\tEnter the Size [Below 20] : ");
           scanf("%d",&n);
           for(i=0;i<n;i++)
              {
                   printf("Enter the Element at [%d] ",i+1);
                   scanf("%d",&a[i]);
              }
                   printf("\n\tOriginal : ");
          for(i=0;i<n;i++)
              {
                   printf("%d  ",a[i]);
              }
          sort(a,0);
          printf("\n\tAfter Sort : ");
          for(i=0;i<n;i++)
              {
                   printf("%d  ",a[i]);
              }
          getch();
      }

Selection Sort – This form of sorting algorithms finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. It does no more than n swaps.
•         Let n = array length = size of the array
•         The outer loop is executed n-1 times
•         Each time the outer loop is executed, the inner loop is executed
–        Inner loop executes n-1 times at first. On average, inner loop executes about n/2 times for each execution of the outer loop.
–        Every time inner loop executer it find the least value from the list then swap it with the value in ‘i’ position.
•         Result is n * n/2 * k, that is, O(n2/2 + k) = O(n2)

The Complexity of Selection Sort will be same as Bubble Sort.
Selection Sort Source code and Algorithm.

#include <stdio.h>
#include <conio.h>

// SELECTION SORT

//Function for Sorting the list

  void SelectionSort(int a[],int size)
      {
          int i,j,min,pos,t;
          for(i = 0;i<size-1;i++)
              {
                   min = a[i];
                   pos = i;
                   for(j = i+1;j<size;j++)
                        {
                            if(a[j]<min)
                                {
                                       min = a[j];
                                       pos = j;
                                }
                            t=a[i];
                            a[i]=a[pos];
                           a[pos]=t;
                        }
              }
      }


//Main Function
  int main()
      {
           int i,n,c=0;
           int a[20];
           printf("\n\tEnter size of Array [Below 20] : ");
           scanf("%d",&n);
           for(i=0 ;i<n;i++)
              {
                   printf("\tEnter Nos. at [%d] : ",i);
                   scanf("%d",&a[i]);
              }
        printf("\n\tBefore Sort : ");
        for(i=0 ;i<n;i++)
           {
              printf("%d  ",a[i]);
           }
        printf("\n\tAfter Selection  Sort : ");
        SelectionSort(a,n);
        for(i=0 ;i<n;i++)
           {
              printf("%d  ",a[i]);
           }
      getch();
  }

Algorithm
  for i ←1 to n-1
      min ←  i;
      x ← A[i]
      for j = i + 1 to n
           do
              If A[j] < min  then
                   m← j
                   x← A[j]
              end if
      end for j
      A[i] ↔ A [m]
  end for i
Selection Sort using Recursive Function

#include <stdio.h>
#include <conio.h>

//Recursive Selection Sort

  int n,p;

//Function for First Loop
  void ssort(int a[],int min,int j,int k,int p)
      {
          int t;
          if(k<n)
              {
                   if(a[k]<min)
                        {
                            min=a[k];
                             p=k;
                        }
                   ssort(a,min,j,k+1,p);
              }
          else
              {
                   t=a[j];
                   a[j]=a[p];
                   a[p]=t;
              }
      }

// Function for Second loop
  void sort(int a[],int i)
      {
           p=i;
           if(i<n-1)
              {
                   ssort(a,a[i],i,i+1,p);
                   sort(a,i+1);
              }

// Main Function
  int main()
      {
          int a[20],i,c,k=0;
          printf("\n\tSize of Array [below 20] : ");
          scanf("%d",&n);
          printf("Enter the no.");
          for(i=0;i<n;i++)
              {
                   printf("\tEnter the value for [%d] Position   ",i+1);
                   scanf("%d",&a[i]);
              }
          printf("\n\tOriginal :  ");
          for(i=0;i<n;i++)
              {
                   printf("%d  ",a[i]);
              }
          sort(a,0);
          printf("\n\tAfter Sort : ");
          for(i=0;i<n;i++)
              {
                   printf("%d  ",a[i]);
              }
          getch();
      }

Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)