Article 1: Basic Sorting Programs

 We are going to see  5 basic sorting algorithms in implementations.

(1) Bubble Sort

(2) Selection Sort

(3) Insertion Sort

(4) Merge Sort

(5) Quick Sort

Bubble Sort

 

Theory: Compare each pair of adjacent items and swap them if they are in wrong order.

Repeat this process until no swaps are needed.

 

Algorithm:

                      Bubble Sort Algorithm:

                      1. for i = 0 to n-1

                      2. for j = 0 to n-2

                     3. if A[j] > A[j+1]

                     4. temp = A[j]

                      5. A[j] = A[j+1]

                     6. A[j+1] = temp

 

Program:

 

// Lab Assignment 1

//Implementation and Time analysis of sorting Algorithms

// Bubblesort

 

#include<stdio.h> // Importing various header files for operation

#include<time.h>

#include<stdlib.h>

 

void bubble_sort(long[],long); // defining Bubble sort function

 

int main()

{

   long a[10000],n,c,d,swap;

   clock_t start_time,end_time;

   printf("Enter number of elements: "); // taking input from users

   scanf("%ld",&n);

   int i;

   int randomnumber;

 

   for(i=n-1;i>=0;i--) // for loop for generating random numbers using rand function

   {

       randomnumber=rand();

       a[i]=randomnumber;  

   }

 

   start_time=clock(); // Time analysis technique for sorting algorithm using time.h header file

   bubble_sort(a,n);

   end_time = clock() - start_time;

   double time_taken=((double)end_time)/CLOCKS_PER_SEC;

   printf("bubble_sort() took %f seconds to execute \n ",time_taken);

   return 0;

}

 

void bubble_sort(long list[],long n) //Using Swapping with temp variables for sorting

{

   

 long c,d,temp;

   

 

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

    {

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

        {

            if(list[d] > list[d+1])

            {

                temp=list[d]; //value of d index transfers to temp variable

                list[d]=list[d+1]; //value of d+1 index transfers to d index

                list[d+1]=temp;//value of temp variable transfers to d+1 index

 

            }

 

        }

    }

}

Selection Sort

 

Theory:  Scan array to find out the smallest element and swap it with the first element. Repeat this procedure for the remainder of the list starting at the second position and advancing each time.

 

Algorithm:                 Selection Sort Algorithm:

1. for i = 0 to n-1

2. for j = i + 1 to n

3. if A[i] > A[j]

4. temp = A[i]

5. A[i] = A[j]

6. A[j] = temp

 

Program:

 

// Lab Assignment 1

//Implementation and Time analysis of sorting Algorithms

// Selection Sort

 

#include<stdio.h> // Importing various header files for operation

#include<time.h>

#include <stdlib.h>

 

void selection_sort(int[],int); // defining Selection sort function

int main()

{

    int n;

   

    printf("Enter total no. of elements : ");  //taking input of how many elements user wants

    scanf("%d",&n);

   

    int a[n], i;

    int randomNumber;

   

    clock_t start_time,end_time;

   

    for(i=n-1;i>=0;i--) // for loop for generation of random number elements  using rand function.

    {

        randomNumber = rand() ;

        a[i]=randomNumber;

    }

 

    start_time=clock(); // time analysis technique using time.h header file

    selection_sort(a,n);

    end_time=clock()-start_time;

 

    double time_taken=((double)end_time)/CLOCKS_PER_SEC;

   

    printf("selection_sort() took %f seconds to execute \n",time_taken);

    return 0;

}

 

void selection_sort(int arr[],int n) //Selection sort function

{

    //Scan array to find out the smallest element and swap it with the first element

    //Repeat this procedure for the remainder of the list starting at the second position and advancing each time

   

    int i, j, a, t, p;

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

    {

        p = i;

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

        {

            if (arr[p] >arr[j])

            p = j;

        }

        if (p != 1)

        {

            t = arr[i];

            arr[i] = arr[p];

            arr[p] = t;

        }

    }

}

Insertion Sort

Theory:

Remove a data item from the input list, insert it into the correct position in the already sorted list until no input elements remain.

 

Algorithm:                   Insertion Sort Algorithm:

                                       1. for j = 2 to n

                                      2. key = A[j] //insert A[j] into sorted

                                                      sequence A[1….j-1]

                                      3. i = j – 1

                                      4. while i > 0 and A[i] > key

                                      5. A[i+1] = A[i]

                                      6. i = i – 1

                                      7.A[i+1] = key

 

Program:

 

// Lab Assignment 1

//Implementation and Time analysis of sorting Algorithms

// Insertion Sort

 

 

#include<stdio.h> //importing header files

#include<stdlib.h>

#include<time.h>

 

void insertion_sort(int[],int); // defining insertion sort function

 

int main()

{

   int a[10000];

   clock_t start_time,end_time;

   int i,n;

 

   printf("Enter total number of elements: "); //taking input of how many elements user wants

   scanf("%d",&n);

 

   int randomnumber;

 

   for(i=n-1;i>=0;i--) // for loop for generation of random number elements  using rand function.

   {

       randomnumber=rand();

       a[i]=randomnumber;

   }

 

   start_time = clock(); // time analysis technique using time.h header file

   insertion_sort(a,n);

   end_time = clock() - start_time;

 

   double time_taken = ((double)end_time)/CLOCKS_PER_SEC;

   printf("insertion_sort() took %f seconds to execute \n",time_taken);

   return 0; 

 

}

 

void insertion_sort(int arr[], int size) //Insertion sort function

{

    //Remove a data item from the input list, insert it into the correct position in the already sorted list until no input elements remain

   

    int i,j,temp;

   

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

    {

        for(j=i-1;j>=0;j--)

        {

            if(arr[j]>arr[j+1])

            {

                temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

            }

 

            else

            {

                break;

            }

        }

    }

}

Merge Sort

Theory:

 Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. 

 

Algorithm:                     Merge Sort Algorithm:

(1).MERGE-SORT(A, p, r)

(2).if p < r then q ← (p + r)/2

(3).MERGE-SORT(A, p, q)

(4).MERGE-SORT(A, q + 1, r)

(5).MERGE(A, p, q, r)

 

Program:

// Lab Assignment 1

//Implementation and Time analysis of sorting Algorithms

// Merge Sort

 

#include<stdio.h> //importing header files

#include<stdlib.h>

#include<time.h>

 

int arr[10000], n, b[10000];

 

void MergeSort(int low, int high); // defining Merge sort function

void Merge(int low, int mid, int high); // defining Merge function for merging the elements.

 

int main()

{

    int i;

    clock_t start_time,end_time;

   

    printf("Enter number of elements:"); //taking input of how many elements user wants

    scanf("%ld",&n);

   

    int randomNumber;

   

    for(i=n-1;i>=0;i--) // for loop for generation of random number elements  using rand function.

    {

        randomNumber = rand() ;

        arr[i]=randomNumber;

    }

   

    start_time=clock(); // time analysis technique using time.h header file

    MergeSort(0, n-1);

    end_time=clock()-start_time;

   

    double time_taken=((double)end_time)/CLOCKS_PER_SEC;

   

    printf("Merge_sort() took %f seconds to execute \n",time_taken);

    return 0;

}

 

void MergeSort(int low, int high) //Merge Sort Function

{

    if(low<high)

    {

    int mid=(low+high)/2;

    MergeSort(low, mid);

    MergeSort(mid+1, high);

    Merge(low, mid, high);

    }

}

 

void Merge(int low, int mid, int high)

//To sort A[p . . r]:

// Divide by splitting into two subarrays A[p . . q] and A[q + 1 . . r], where q is the halfway point of A[p . . r].

// Conquer by recursively sorting the two subarrays A[p . . q] and A[q + 1 . . r].

 //Combine by merging the two sorted subarrays A[p . . q] and A[q + 1 . . r] to produce a single sorted subarray A[p . . r].

{

    int h=low;

    int i=low;

    int j=mid+1;

    int k;

 

    while((h<=mid) && (j<=high))

    {

        if(arr[h]<=arr[j])

        {

            b[i]=arr[h];

            h++;

        }

        else

        {

            b[i]=arr[j];

            j++;

        }

        i++;

    }

 

    if(h>mid)

    {

        for(k=j; k<=high;k++)

        {

            b[i]=arr[k];

            i++;

        }

    }

 

    else

    {

        for(k=h; k<=mid; k++)

        {

            b[i]=arr[k];

            i++;

        }

    }

 

    for(k=low; k<=high; k++)

    {

        arr[k]=b[k];

    }

}

Quick Sort

Theory: Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of Quick Sort that pick pivot in different ways. 

1.   Always pick first element as pivot.

2.   Always pick last element as pivot

3.   Pick a random element as pivot.

4.   Pick median as pivot.

 

Algorithm:                            Quick Sort Algorithm:

QUICKSORT(A, p, r)

if p < r

then q ←PARTITION(A, p, r)

QUICKSORT(A, p, q − 1)

QUICKSORT(A, q + 1, r)

 

Initial call is QUICKSORT(A, 1, n).

 

PARTITION(A, p, r)

x ← A[r]

i ← p − 1

for j ← p to r − 1

do if A[ j ] ≤ x

then i ← i + 1

exchange A[i ] ↔ A[ j ]

exchange A[i + 1] ↔ A[r]

return i + 1

 

 

Program:

// Lab Assignment 1

//Implementation and Time analysis of sorting Algorithms

// Quick Sort

 

#include<stdio.h>  //importing header files

#include<time.h>

#include<stdlib.h>

 

int arr[10000], n;

int partition(int arr[], int m, int p); //defining partition function

void swaping(int arr[], int i, int j); //defining swapping function

void QuickSort(int arr[], int p, int q); //defining Quick Sort Function

 

int main()

{

    int i;

   

    int randomNumber;

    clock_t start_time,end_time;

   

    printf("Enter number of elements: \n"); //taking input of how many elements user wants

    scanf("%ld",&n);

   

    for(i=n-1;i>=0;i--) // for loop for generation of random number elements  using rand function.

    {

        randomNumber = rand() ;

        arr[i]=randomNumber;

    }

   

    start_time=clock();  // time analysis technique using time.h header file

    QuickSort(arr, 0, n-1);

    end_time=clock()-start_time;

   

    double time_taken=((double)end_time)/CLOCKS_PER_SEC;

 

    printf("quick_sort() took %f seconds to execute \n",time_taken);

    return 0;

}

//Quicksort is based on the three-step process of divide-and-conquer.

//To sort the subarray A[p . . r]:

int partition(int arr[], int m, int p) //Partition Function

{

   // Divide: Partition A[p . . r], into two (possibly empty) subarrays A[p . . q − 1] and A[q + 1 . .r],

   //such that each element in the first subarray A[p . . q − 1] is ≤ A[q] and A[q] is ≤ eachelement in the second subarray A[q + 1 . . r]

 

    int v=arr[m];

    int i=m;

    int j=p;

    do

    {

        do

        i++;

        while(arr[i]<v);

        do

        j--;

        while(arr[j]>v);

        if(i<j)

        swaping(arr, i, j);

    }

    while(i<=j);

    arr[m]=arr[j];

    arr[j]=v;

    return j;

}

 

void swaping(int arr[], int i, int j)

{

    int p;

    p=arr[i];

    arr[i]=arr[j];

    arr[j]=p;

}

void QuickSort(int arr[], int p, int q)

//The quicksort algorithm is a sorting algorithm that works by selecting a pivot point, and thereafter partitioning the number set, or array, around the pivot point

{

    if(p<q)

    {

        int j=partition(arr, p, q+1);

        QuickSort(arr, p, j-1);

        QuickSort(arr, j+1, q);

    }

}