C Programming Tutorial: searching and sorting

searching and sorting

Showing posts with label searching and sorting. Show all posts

Insertion Sort Algorithm, Time Complexity And Program In C

In Insertion Sort we select a key i.e an element one by one from any given list of element ( array ) and then we insert it in its appropriate position. We can either scan the list from left to right or right to left to find an appropriate position. But usually we scan list from right to left because it is better in case of sorted and almost sorted arrays. Insertion sort is an efficient algorithm for sorting small number of elements. Though Insertion Sort is based on recursive idea, it is more efficient to implement this algorithm by bottom up approach i.e iteratively.

Need Programming Help visit: Get Programming Help Online

Consider the elements to be sorted by insertion sort are : 89, 45, 68, 90, 29, 34, 17

As shown in Figure below, starting with A[1] and ending with A[n - 1], A[i] is inserted in its appropriate place among the first i elements of the array that have been already sorted (but, unlike selection sort, the elements are generally not in their final positions).

Insertion Sort In C : Showing insertion of elements

Insertion Sort In C : Showing how elements are sorted

The above figure shows how elements 89, 45, 68, 90, 29, 34, 17 are sorted by insertion sort. A vertical bar separates the sorted part of the array from the remaining elements; the element being inserted is in bold.

Note : Refer to algorithm for better understanding.

INSERTION SORT ALGORITHM

Back to Insertion Sort

InsertionSort(int a[ ], int n)

   for i=1 to n-1
       key = a[i]
       j = i-1


       while j>=0 and key < a[j]
           a[j+1]=a[j]; 
           j=j-1;
   
       a[j+1] =  key

Note : The operation of the algorithm can be understood with the help of above figure.

TIME COMPLEXITY OF INSERTION SORT

Back to Insertion Sort

Time Complexity Of Insertion Sort - Best Case

The best case input in an array is such that the array is already sorted.
In this case insertion sort has linear running time i.e O(n)

Time Complexity Of Insertion Sort - Worst Case

The worst case input in an array is such that the array is sorted in reverse order.
In this case insertion sort has quadratic running time i.e O(n²)

Time Complexity Of Insertion Sort - Average Case

Input in this case is a random input.
In this case also insertion sort has quadratic running time i.e O(n²)
Insertion Sort is very efficient in sorting very small arrays.
Its impractical to sort very large arrays using insertion sort due to its time complexity of O(n²)

INSERTION SORT PROGRAM IN C

Back to Insertion Sort

// Insertion sort program in c

#include<stdio.h> 

void InsertionSort(int a[],int n) ;

int main() 
{ 
 int a[20],i,n; 
 printf("Enter number of elements in array : "); 
 scanf("%d",&n);
  
 // Inputting elements
 for(i=0;i<n;i++) 
 { 
    printf("Enter number %d: ",i+1); 
    scanf("%d",&a[i]);
 } 
 
 // Displaying Elements before insertion sort
 printf("Items in the array are : "); 
 for(i=0;i<n;i++)
 { 
    printf("%d ",a[i]); 
 } 
 
 //Applying insertion sort
 InsertionSort(a,n); 
 
 // Displaying elements after insertion sort
 printf("\nElements after insertion sort : "); 
 for(i=0;i<n;i++) 
 { 
    printf("%d ",a[i]); 
 } 
 return 0; 
} 

void InsertionSort(int a[],int n) 
{ 
 int i,key,j; 
 
 for(i=1;i<n;i++) 
 { 
  key=a[i]; 
  j=i-1;

  // Finding appropriate position to insert key
  while((key<a[j])&&(j>=0))  
  { 
   a[j+1]=a[j]; 
   j=j-1; 
  }

  // Inserting key
  a[j+1]=key; 
 } 
}

More Informative Posts :

Heap Sort Program In C

searching and sorting

Mantu Kumar 13:23 Add Comment

Mantu Kumar

HEAP SORT

HEAP SORT IN C

Back To Heap Sort

Heap sort uses a binary heap, which is a complete binary tree.

Binary Tree : A Binary Tree is a hierarchical structure that is either empty or consists of an element, called the root, and two distinct binary trees, called the left subtree and right subtree.

Need HTML Homework Help: Get Best HTML CSS JavaScript Homework Help

Example :

Heap Sort : Binary Tree

Heap is a binary tree with the following properties :

It is a complete binary tree.
Each node is greater than or equal to any of its children.

Complete Binary Tree : A binary tree is complete if each of its levels is full, except that the last level may not be full and all the leaves on the last level are placed leftmost.

Example :

Heap Sort : Complete Binary Tree

Heap Example :

Heap Sort : Heap

Note : We represent heaps in level order, going from left to right. The array corresponding to the heap above is :

[45, 24, 32, 16,19,12, 21].

PSEUDOCODE TO ADD NODE IN HEAP

Back To Heap Sort

To add a new node to the heap, first add it to the end of the heap and then rebuild the tree as follows:

Let the last node be the current node;

while (the current node is greater than its parent) {

Swap the current node with its parent;

Now the current node is one level up;

}

Suppose we want to insert 3, 5, 1, 19, 11, 22. We assume that the heap is initially empty.

Heap Sort : Adding Node In Heap

Now lets insert a new node 88 in the above heap.

Heap Sort : Rebuilding of Heap after adding a new node

PSEUDOCODE TO REMOVE ROOT FROM HEAP

Back To Heap Sort

Often you need to remove the max element, which is the root in a heap. After the root is removed, the tree must be rebuilt to maintain the heap property. The algorithm for rebuilding the tree can be described as follows:

Move the last node to replace the root;

Let the root be the current node;

while (the current node has children and the current node is smaller than one of its children) {

Swap the current node with the larger of its children;

Now the current node is one level down;

}

Heap Sort : Removing Root and Rebuilding Heap

HOW HEAP SORT IS PERFORMED

Back To Heap Sort

First we take input in an array.
Then we insert these element in heap.
As we know that root of the heap is maximum element so we remove root and rebuild heap so that the next maximum element is at root. Rebuilding ensures that our tree is in the form of heap.
We store the root ( maximum element ) in decreasing order of array length. We could have used another array as well to store the root.

HEAP SORT PROGRAM IN C

Back To Heap Sort

// C Program ( Code ) for Heap sort

#include<stdio.h>

void insert(int a[], int n, int item);
int deleteheap(int a[],int n);

int main()
{
   int a[20],i,n,item;
   printf(" Enter number of elements in array : ");
   scanf("%d",&n);
   for(i=0;i<n;i++)
   {
     printf(" Enter number %d : ",i+1);
     scanf("%d",&a[i]);  
   }
 
   for(i=0;i<n;i++)
   {

     item=a[i];
     insert(a,i,item);
   }
   printf("\n Heap is : ");
   for(i=0;i<n;i++)
   {
     printf("%d ",a[i]);
   }


   for(i=n;i>=1;i--)
   { 
     item=deleteheap(a,i);
         
     // Stores item=Maximum element in decreasing order of array length
     a[i-1]=item;
   }


   printf("\n SORTED LIST IS!!!!\n");
   for(i=0;i<n;i++)
   {
     printf(" %d ",a[i]);
   }
 
 }
 
  // Used to Build Heap
  void insert(int a[], int n, int item)
  {
     int ptr,par,temp;
 
     ptr=n;
     while(ptr>=1)
     { 
       par=(ptr-1)/2;
 
       if(a[par]>=item)
       { 
         a[ptr]=item;
         return;
       }
       else
       {
         a[ptr]=a[par];
         ptr=par;
       }
    
       a[ptr]=item;
     }
 }
 
  /* Remove root which is the maximum element in Heap and rebuild heap 
     so that the next maximum element is at root. Rebuilding ensures 
     that our tree is in the form of heap.
     Returns item = a[0] wcich contains the root of the heap.
   */
  int deleteheap(int a[],int n)
  {
    int i=0,item,temp;
    
    // a[0] - contains the root of the heap
    item=a[0];
    a[0]=a[n-1];
    n=n-1;
    while(((a[i]<a[2*i+1])||(a[i]<a[2*i+2]))&&((2*i+1)<n))
    {
      if(a[2*i+1]>a[2*i+2])
      {
        temp=a[i];
        a[i]=a[2*i+1];
        a[2*i+1]=temp;
        i=2*i+1;
      }
 
      else
      {
        temp=a[i];
        a[i]=a[2*i+2];
        a[2*i+2]=temp;
        i=2*i+2;
      }
    }
    
    // Root of the heap is returned
    return item;
  }

HEAP SORT PROGRAM OUTPUT

Back To Heap Sort

Heap Sort Output

More Informative Posts :

Counting Sort Program In C

searching and sorting

Mantu Kumar 08:39 3 Comments

Mantu Kumar

COUNTING SORT

COUNTING SORT IN C

Back To Counting Sort

In the code for counting sort, we assume that the input is an array A[1 . . . n] and we require two other arrays: the array B[1 . . . n] holds the sorted output, and the array C[0 . . . k] provides temporary working storage. Here k = maximum element present in array.

Consider following elements to be sorted using counting sort : 2, 5, 3, 0, 2, 3, 0, 3

So we have in array A[1 . . . 8 ] :

Now what we have to do is initialize the auxiliary array C[0 . . . k] with 0. Here k = 5.

So C[0 . . . 5] becomes :

Next step is to count the frequency of each element and store it in their respective index position i.e here frequency of 0 = 2. So we place '2' at index position '0'. Similarly we place each element and the array becomes C[0 . . . 5] :

Now we add the current index position with its previous index position and store it in the current index position i.e C[ i ] = C[ i ] + C[ i - 1 ] where 'i' starts from '1'.

So C[ 0 . . . 5 ] becomes :

The final step is to place the elements in B[ 1 . . . 8 ] with reference to C[ 0 . . . 5 ] i.e Now we treat elements in C[ 0 . . . 5 ] as index of B[ 1 . . . 8 ] and index of C[ 0 . . . 5 ] as elements of B[ 1 . . . 8 ]. So at index position '8' we have element '5' so we place '5' at index position of '8' of B[ 1 . . . 8 ] ( B[ 8 ] = 5 ) and we reduce the index position by '1' i.e 8-1 = 7. Now note that we have element '7' in C[ 4 ] position but '4' is not present in the original array so we skip it and move to C[ 3 ] position, so we place '3' at index position '7' of B[ 1 . . . 8 ]. Similarly we place each element in B[ 1 . . . 8 ] and we get sorted array.

So the sorted array B[ 1 . . . 8 ] is :

COUNTING SORT ALGORITHM

Back To Counting Sort

// Counting Sort algorithm

CountingSort(A,B,n,k)

   int C[0 . . . k ]

   for i=0 to k

      C[i]=0

   for j=1 to n

      C[A[j]] = C[A[j]] + 1;

   for i=1 to k

      C[i] = C[i] + C[i-1];

   for j=n downto 1

      B[C[A[j]]] = A[j];
      C[a[j]] = C[A[j]] - 1;

COUNTING SORT PROGRAM IN C

Back To Counting Sort

// Counting sort program in c


#include<stdio.h> 

void CountingSort(int a[], int sorted_array[], int max_element, int n);

int main() 
{ 
 int a[20],i,n; 
 int max_element, sorted_array[20];
 
 printf("Enter number of elements in array : "); 
 scanf("%d",&n);
  
 // Inputting elements
 for(i=1;i<=n;i++) 
 { 
    printf("Enter number %d: ",i+1); 
    scanf("%d",&a[i]);
 } 
 
 // Displaying Elements before counting sort
 printf("Items in the array are : "); 
 for(i=1;i<=n;i++)
 { 
    printf("%d ",a[i]); 
 } 
 
 // Finding Maximum element
 max_element=a[1];
 
 for(i=2;i<=n;i++)
 {
  if(a[i] > max_element)
  {
           max_element = a[i];
  }
 }
 
 //Applying counting sort
 CountingSort(a, sorted_array, max_element, n); 
 
 // Displaying elements after count sort
 printf("\nElements after count sort : "); 
 for(i=1;i<=n;i++) 
 { 
    printf("%d ",sorted_array[i]); 
 } 
    
 return 0; 
} 

void CountingSort(int a[],int sorted_array[],int max_element, int n)
{
 int aux_array[max_element];
 int i,j;
 
 // Initializing auxiliary array

        for(i=0;i<=max_element;i++)
 {
  aux_array[i]=0;
 }

        // Placing Frequency of each element in aux_array
 for(j=1;j<=n;j++)
 {
  aux_array[a[j]]=aux_array[a[j]]+1;
 }

        // Adding elements of current and previous index position
 for(i=1;i<=max_element;i++)
 {
  aux_array[i]=aux_array[i]+aux_array[i-1];
 }

        // Placing elements in sorted_array 
 for(j=n;j>=1;j--)
 {
  sorted_array[aux_array[a[j]]] = a[j];
  aux_array[a[j]] = aux_array[a[j]] - 1;
 }
}

More Informative Posts :

Selection Sort Program In C

searching and sorting

Mantu Kumar 22:34 Add Comment

Mantu Kumar

Selection Sort

SELECTION SORT IN C

We start Selection Sort by scanning the entire given list to find its smallest element and exchange it with the first element, putting the smallest element in its final position in the sorted list. Then we scan the list, starting with the second element, to find the smallest among the last n - 1 elements and exchange it with the second element, putting the second smallest element in its final position. Generally, on the ith pass through the list, which we number from 0 to n - 2, the algorithm searches for the smallest item among the last n - i elements and swaps it with A[i].

Consider the following element that is to be sorted using selection sort : 89, 45, 68, 90, 29, 34, 17.
The analysis of selection sort is straightforward. The input's size is given by the number of elements 'n' and the algorithm's basic operation is the key comparison A[j] < A[min]. The number of times it is executed depends only on the array's size.

Selection Sort In C : Showing how elements are sorted

The above figure shows how given elements 89, 45, 68, 90, 29, 34, 17 are sorted according to selection sort. Each line corresponds to one iteration of the algorithm i.e. a pass through the list tail to the right of the vertical bar. An element in bold indicates the smallest element found. Elements to the left of the vertical bar are in their final positions and are not considered in this and subsequent iterations.

SELECTION SORT ALGORITHM

SelectionSort(int a[],int n)

   for i=0 to n-2

     min=i

     for j=i+1 to n-1

        if a[min] > a[j]

           min = j

     swap a[i] with a[min]

SELECTION SORT PROGRAM IN C

// Selection sort program in c

#include<stdio.h> 

void SelectionSort(int [],int); 
 

int main() 
{ 
 int a[20],i,n; 
 printf("Enter number of elements in array : "); 
 scanf("%d",&n);
  
 // Inputting elements
 for(i=0;i<n;i++) 
 { 
    printf("Enter number %d: ",i+1); 
    scanf("%d",&a[i]);
 } 
 
 // Displaying Elements before selection sort
 printf("Items in the array are : "); 
 for(i=0;i<n;i++)
 { 
    printf("%d ",a[i]); 
 } 
 
 //Applying selection sort
 SelectionSort(a,n); 
 
 // Displaying elements after selection sort
 printf("\nElements after selection sort : "); 
 for(i=0;i<n;i++) 
 { 
 printf("%d ",a[i]); 
 } 
 return 0; 
} 

void SelectionSort(int a[],int n) 
{ 
 int i,loc,j,min,temp; 
 for(i=0;i<=n-2;i++) 
 { 
   min = i;
 
   for(j=i+1;j<=n-1;j++) 
   {   
     // Finding minimum element
     if(a[min] >a[j])  
     { 
       min=j;  
     } 
   }
  
   //Swapping a[i] with a[min]
   temp=a[i]; 
   a[i]=a[min]; 
   a[min]=temp;
 } 
}

More Informative Posts :

Bubble Sort Program In C

searching and sorting

Mantu Kumar 01:35 Add Comment

Mantu Kumar

Bubble Sort

BUBBLE SORT IN C

Back To Bubble Sort

Bubble Sort is a popular but inefficient sorting algorithm. Bubble Sort is another brute-force application to the sorting problem that compares adjacent elements of the list and exchange them if they are out of order. By doing it repeatedly, we end up "bubbling up" the largest element to the last position on the list. The next pass bubbles up the second largest element, and so on until, after n - 1 passes, the list is sorted. Pass i (0 <= i <= n - 2) of bubble sort can be represented by the following diagram:

Consider element to be sorted are : 89, 45, 68, 90, 29, 34, 17

Quick Sort In C : Showing how elements are sorted

First two passes of bubble sort on the given list 89, 45, 68, 90, 29, 34, 17 is shown in above figure. A new line is shown after a swap of two elements is done. The elements to the right of the vertical bar are in their final positions and are not considered in subsequent iterations of the algorithm.

BUBBLE SORT ALGORITHM

Back To Bubble Sort

// Algorithm for Bubble Sort

BubbleSort(int a[],int n)

  for i=0 to n-2

    for j=0 to n-2-i

      if a[j] > a[j+1]

        swap a[j] with a[j+1]

BUBBLE SORT PROGRAM IN C

Back To Bubble Sort

// Bubble sort program in c

#include<stdio.h> 

void bubblesort(int a[],int n);

int main() 
{ 
 int a[20],i,n; 
 printf("Enter number of elements in array : "); 
 scanf("%d",&n);
  
 // Inputting elements
 for(i=0;i<n;i++) 
 { 
 printf("Enter number %d: ",i+1); 
 scanf("%d",&a[i]);
 } 
 
 // Displaying Elements before bubble sort
 printf("Items in the array are : "); 
 for(i=0;i<n;i++)
 { 
 printf("%d ",a[i]); 
 } 
 
 //Applying bubble sort
 bubblesort(a,n); 
 
 // Displaying elements after bubble sort
 printf("\nElements after bubble sort : "); 
 for(i=0;i<n;i++) 
 { 
   printf("%d ",a[i]); 
 } 
 return 0; 
} 

void bubblesort(int a[],int n) 
{ 
  int i,j;
  for(i=0; i<=n-2; i++) 
  { 
    for(j=0;j<=n-i-2;j++) 
    { 
       // Swapping elements
       if(a[j]>a[j+1]) 
       { 
         int temp=a[j]; 
         a[j]=a[j+1]; 
         a[j+1]=temp; 
      } 
   } 
 } 
}

More Informative Posts :

Quick Sort Program In C

searching and sorting

Mantu Kumar 03:10 2 Comments

Mantu Kumar

Quick Sort

QUICK SORT IN C

Back to Quick Sort

Quick Sort is another sorting algorithm that is based on divide and conquer approach. Unlike merge sort that divides input elements according to their position in array, quick sort divides input element according to their values. Here is a three-step divide and conquer process for sorting a typical sub-array.

Need Python Homework Help: Get Python Homework Help from Epert

Divide : Partition or rearrange the array a[p . . r] into two sub-arrays a[ p . . q-1 ] and a[q+1 . . r] such that a[ p . . q-1 ] <= a[q] <= a[q+1 . . r] . Compute the index q as part of this partition procedure. Here a[q] is called the pivot element.

Conquer : Sort the two sub-arrays a[ p . . q-1 ] and a[q+1 . . r] by recursive calls to quick sort.

Combine : Because the sub-arrays are already sorted, no work is needed to combine them : the entire array a[ p . . r ] is now sorted.

Lets understand Quick Sort with the help of an example :

Array Elements ( List ) : 2 8 7 1 3 5 6 4

Steps :

Select the pivot element ( 4 in this case )
Rearrange elements such that elements before pivot element are less than it and element after pivot element are greater than it. This arrangement of elements in accordance with the pivot element is called partition operation.
Sort the sub-array recursively.

Steps for Quick Sort

The above image shows the partition of Array elements ( Initial list ).
Similarly the two sub-array before and after pivot element are partitioned.
The complete steps of quick sort is shown below.

Quick Sort

QUICK SORT ALGORITHM

Back to Quick Sort

// Algorithm for Quick Sort

QUICKSORT(a, p, r)
  if p<r
    q = PARTITION(a, p, r)
    QUICKSORT(a, p, q-1)

    QUICKSORT(a, q+1, r)

Partitioning the array :

PARTITION(a, p, r)
  x=a[r]
  i=p-1

  for j=p to r-1
     if(a[j]<=x)
        i=i+1
        swap a[i] with a[j]

  end loop

  
  swap a[i+1] with a[r]

  return i+1

QUICK SORT PROGRAM IN C

Back to Quick Sort

//Quick sort program ( code ) in c

#include<stdio.h> 

void quicksort(int a[],int p, int r); 
int partition(int a[],int p, int r); 

int main() 
{ 
 int a[20],i,n; 
 printf("Enter number of elements in array : "); 
 scanf("%d",&n);
  
 // Inputting elements
 for(i=0;i<n;i++) 
 { 
    printf("Enter number %d: ",i+1); 
    scanf("%d",&a[i]);
 } 
 
 // Displaying Elements before quick sort
 printf("Items in the array are : "); 
 for(i=0;i<n;i++)
 { 
    printf("%d ",a[i]); 
 } 
 
 //Applying quick sort
 quicksort(a,0,n-1); 
 
 // Displaying elements after quick sort
 printf("\nElements after quick sort : "); 
 for(i=0;i<n;i++) 
 { 
    printf("%d ",a[i]); 
 } 
 return 0; 
} 

void quicksort(int a[],int p, int r) 
{
   int q;
   if(p<r)
   {

     // q - index at which pivot element lies
     q=partition(a,p,r);

     // Sorting sub-array recursively
     quicksort(a,p,q-1);
     quicksort(a,q+1,r);
   }
}

int partition(int a[],int p, int r)
{
   int temp;

   int i=p-1;

   int j;

   // pivot element around which partition is done
   int x=a[r];

 
   for(j=p;j<=r-1;j++)
   {
     if(a[j]<=x)
     {
       i=i+1;
       temp=a[i];
       a[i]=a[j];
       a[j]=temp;
     }
   }
 
   temp=a[i+1];
   a[i+1]=a[r];
   a[r]=temp;
   return (i+1);
}

Quick Sort Program Output

Quick Sort : Quick Sort Program Output

More Informative Posts :

Searching And Sorting In C

searching and sorting

Mantu Kumar 00:55 Add Comment

Mantu Kumar

Other Searching and Sorting technique will be published soon.

SORTING

Merge Sort Program In C

searching and sorting

Mantu Kumar 00:49 Add Comment

Mantu Kumar

Here I am providing you with Merge Sort program in c.

#include<stdio.h> 

void mergesort(int a[],int i, int j); 
void merge(int a[],int p , int q, int r1); 

int main() 
{ 
 int a[20],i,n,item; 
 printf("Enter number of elements in array : "); 
 scanf("%d",&n);
  
 // Inputting elements
 for(i=0;i<n;i++) 
 { 
   printf("Enter number %d: ",i+1); 
   scanf("%d",&a[i]);
 } 
 
 // Displaying Elements before merge sort
 printf("Items in the array are : "); 
 for(i=0;i<n;i++)
 { 
   printf("%d ",a[i]); 
 } 
 
 //Applying merge sort
 mergesort(a,0,n-1); 
 
 // Displaying elements after merge sort
 printf("\nElements after merge sort : "); 
 for(i=0;i<n;i++) 
 { 
   printf("%d ",a[i]); 
 } 
 return 0; 
} 

void mergesort(int a[],int i, int j) 
{ 
 int mid; 
 if(i>=j) 
 return; 
 
 else 
 { 
   mid=(i+j)/2; 
   mergesort(a,i,mid); 
   mergesort(a,mid+1,j); 
   merge(a,i,mid,j);  
 } 
} 

void merge(int a[],int p , int q, int r) 
{ 
 int n1=q-p+1; 
 int n2=r-q;
 int left[n1+1];
 int right[n2+1]; 

 int i=0;
 int j=0;
 int k=0;
 
 
 for(i=0;i<n1;i++) 
 {
   left[i]=a[p+i]; 
 }
 
 for(i=0;i<n2;i++) 
 {
   right[i]=a[q+i+1];
 }
 
 left[n1]=9999; 
 right[n2]=9999;  
 
 i=0;
 j=0;
 
 for(k=p;k<=r;k++) 
 { 
 
   if(left[i]<right[j]) 
   { 
     a[k]=left[i]; 
     i++; 
   } 
 
   else 
   { 
     a[k]=right[j]; 
     j++; 
   } 
 }

More Informative Posts :