Quick Sort

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

Quick sort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst case complexity are of Ο(n²), where n is the number of items.

Algorithm For Quick Sort:-

PARTITION ( A,p,r)

{

X=a[r]

i = p-1

For(j=p to r-1)

{

If(a[j]<=x)

{

I=i+1

Exchange a[i] with a[j]

}

}

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

Return i+1

}

QUICKSORT(A, p, r)

{

If(p<r)

{

S=PARTITION (A, p, r)

QUICKSORT(A,p,S-1)

QUICKSORT(A,S-1,r)

}

}

Program For Quick Sort:-

#include <stdio.h>

void quick_sort(int[],int,int);

int partition(int[],int,int);

int main()

{

    int a[50],n,i;

    printf("enter size of array");

    scanf("%d",&n);

    printf("\n enter elements of array:");

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

        scanf("%d",&a[i]);

    quick_sort(a,0,n-1);

    printf("\nArray after quick sorting:");

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

        printf("%d ",a[i]);

    return 0;

}

void quick_sort(int a[],int l,int u)

{

    int j;

    if(l<u)

    {

        j=partition(a,l,u);

        quick_sort(a,l,j-1);

        quick_sort(a,j+1,u);

    }

}

int partition(int a[],int l,int u)

{

    int v,i,j,temp;

    v=a[l];

    i=l;

    j=u+1;

    do

    {

        do

            i++;

        while(a[i]<v&&i<=u);

        do

            j--;

        while(v<a[j]);

        if(i<j)

        {

            temp=a[i];

            a[i]=a[j];

            a[j]=temp;

        }

    }while(i<j);

    a[l]=a[j];

    a[j]=v;

    return(j);

}

Output Of Program:-

Read More

Insertion Sort

An element which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n²), where n is the number of items.

Algorithm OF Insertion_Sort

Insertion_sort (A)

For (j=2 to a.length)

{

Key=a[j];

I=j-1;

While(i>=0 and a[i]>key)

{

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

I=i-1;

}

A[i+1]=key;

}

Program Of Insertion Sort

#include <stdio.h>

int main()

{

  int n, array[1000], c, d, t;

  printf("Enter number of elements\n");

  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++) {

    scanf("%d", &array[c]);

  }

  for (c = 1 ; c <= n - 1; c++) {

    d = c;

    while ( d > 0 && array[d] < array[d-1]) {

      t          = array[d];

      array[d]   = array[d-1];

      array[d-1] = t;

      d--;

    }

  }

  printf("Array sorted by insertion sort technic is :\n");

  for (c = 0; c <= n - 1; c++) {

    printf("%d\n", array[c]);

  }

  return 0;

}

output Of Program:-

Read More

Linear search Algorithm

Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one.
Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.

Algorithm Of  Linear Search

Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found

Step 8: Exit

Program Of Linear Search


#include <stdio.h>

int main()
{
   int array[100], search, c, n;

   printf("Enter the number of elements in array\n");
   scanf("%d",&n);

   printf("Enter %d integer(s)\n", n);

   for (c = 0; c < n; c++)
      scanf("%d", &array[c]);

   printf("Enter the number to search\n");
   scanf("%d", &search);

   for (c = 0; c < n; c++)
   {
      if (array[c] == search)     /* if required element found */
      {
         printf("%d is present at location %d.\n", search, c+1);
         break;
      }
   }
   if (c == n)
      printf("%d is not present in array.\n", search);

   return 0;
}

Output:-

Read More