Design and Analysis of Algorithms - 6

by

Implement program for randomized version of quick sort and compare its performance with normal version of quick sort using steps count on various number of inputs.

 

Code:


#include<stdio.h>

#include<stdlib.h>

#include<time.h>

 

int count=0;

int r_count=0;

void quick_sort(int a[],int start,int n)

{

    int i,j,pivot,temp;

    count++;

    if(start<n)

        {

            count++;

            pivot=start;

            count++;

            i=start;

            count++;

            j=n;

            count++;

            while(i<j)

                {

                    count++;

            while(a[i]<=a[pivot] && i<n)

                {

                    count++;

                    i++;

                    count++;

                }

                while(a[j]>a[pivot])

                    {

                        count++;

                        j--;

                        count++;

                    }

                    if(i<j)

                        {

                            count++;

                            temp=a[i];

                            count++;

                            a[i]=a[j];

                            count++;

                            a[j]=temp;

                            count++;

                         }

                }

                temp=a[pivot];

                count++;

                a[pivot]=a[j];

                count++;

                a[j]=temp;

                count++;

                quick_sort(a,start,j-1);

                count++;

                quick_sort(a,j+1,n);

                count++;

        }

}

 

void sorting_time(int a[],int start,int n)

{

    int i,j,pivot,temp;

    if(start<n)

        {

            pivot=start;

            i=start;

            j=n;

            while(i<j)

                {

                    while(a[i]<=a[pivot] && i<n)

                    {

                        i++;

                    }

                    while(a[j]>a[pivot])

                    {

                        j--;

                    }

                    if(i<j)

                        {

                            temp=a[i];

                            a[i]=a[j];

                            a[j]=temp;

                        }

                 }

                 temp=a[pivot];

                 a[pivot]=a[j];

                 a[j]=temp;

                 sorting_time(a,start,j-1);

                 sorting_time(a,j+1,n);

         }

}

 

void quick_sort_rand(int a[],int start,int n)

{

    int i,j,temp,pivot;

    r_count++;

    if(start<n)

        {

            r_count++;

            pivot=pivot=start+ rand()%(n-start+1);

            r_count++;

            i=start;

            r_count++;

            j=n;

            r_count++;

            while(i<j)

            {

                r_count++;

                while(a[i]<=a[pivot] && i<n)

                    {

                        r_count++;

                        i++;

                        r_count++;

                    }

                    while(a[j]>a[pivot])

                        {

                            r_count++;

                            j--;

                            r_count++;

                        }

                        if(i<j)

                            {

                                r_count++;

                        temp=a[i];

                        r_count++;

                        a[i]=a[j];

                        r_count++;

                        a[j]=temp;

                        r_count++;

                        }

                        }

                        temp=a[pivot];

                        r_count++;

                        a[pivot]=a[j];

                        r_count++;

                        a[j]=temp;

                        r_count++;

                        quick_sort(a,start,j-1);

                        r_count++;

                        quick_sort(a,j+1,n);

                        r_count++;

                        }

}

 

void rand_sorting_time(int a[],int start,int n)

{

    int i,j,pivot,temp;

    if(start<n)

        {

            pivot=pivot=start+ rand()%(n-start+1);

            i=start;

            j=n;

    while(i<j)

        {

            while(a[i]<=a[pivot] && i<n)

            {

                i++;

            }

        while(a[j]>a[pivot])

            {

                j--;

            }

        if(i<j)

            {

                temp=a[i];

                a[i]=a[j];

                a[j]=temp;

            }

        }

        temp=a[pivot];

        a[pivot]=a[j];

        a[j]=temp;

        sorting_time(a,start,j-1);

        sorting_time(a,j+1,n);

       }

}

int main ()

{

    int i;

    time_t t;

    clock_t start,end;

    double time_taken,r_time_taken;

    int n;

    srand((unsigned)time(&t));

    printf("Enter size of array: ");

    scanf("%d",&n);

    int a[n];

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

    a[i]=rand()%10000;printf("\nFor Random Array \nArray size: %d",n);

    quick_sort(a,0,n);

    printf("\nTotal steps of Quick sort: %d",count);

    count=0;

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

        {

            a[i]=rand()%100000;

        }

    quick_sort_rand(a,0,n);

    printf("\nTotal steps of Randomized Quick sort: %d",r_count);

    r_count=0;

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

        {

            a[i]=rand()%100000;

        }

    start=clock();

    sorting_time(a,0,n);

    end=clock();

    time_taken=((double)(end-start))/CLOCKS_PER_SEC;

    printf("\nTime with Quick sort: %f",time_taken);

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

        {

            a[i]=rand()%100000;

        }

    start=clock();

    rand_sorting_time(a,0,n);

    end=clock();

    r_time_taken=((double)(end-start))/CLOCKS_PER_SEC;

    printf("\nTime with Randomized Quick sort: %f",r_time_taken);

    printf("\n\nFor Sorted Array");

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

        {

            a[i]=i;

        }

    printf("\nArray size: %d",n);

    quick_sort(a,0,n);

    printf("\nTotal steps of Quick sort: %d",count);

    quick_sort_rand(a,0,n);

    printf("\nTotal steps of Randomized Quick sort: %d",r_count);

    start=clock();

    sorting_time(a,0,n);

    end=clock();

    time_taken=((double)(end-start))/CLOCKS_PER_SEC;

    printf("\nTime with Quick sort: %f",time_taken);

    time_taken=0;

    start=clock();

    rand_sorting_time(a,0,n);

    end=clock();

    r_time_taken=((double)(end-start))/CLOCKS_PER_SEC;

    printf("\nTime with Randomized Quick sort: %f",r_time_taken);

    r_time_taken=0;

}


Output:





















































































Conclusion:

 

In this Practical, I understand to Implement program for randomized version of quick sort.

And also, compare its performance with normal version of quick sort using steps count on various number of inputs.


Comments

Post a Comment

Popular posts from this blog

Computer Architecture and Organization - 4

by
Image
Aim:  To implement various 4-bit arithmetic Micro-operations           using arithmetic unit.   Theory Arithmetic micro operation of the form L:   R A  ( R A + R B ) refers to two data items contained in R A and R B input to a parallel adder with the result being stored back in R A (Fig.). Loading      of the result in R A is subject to the availability   of the control   signal designated as L   (that   is   load control of R A ) . Note that adder being a combinational logic, the adder output is available after a delay of the associated combinational circuit. Input to adder may be also controlled by providing AND word gates on the data paths from R A and R B to the adder under the control signal C (Fig.). the control signals `C' and 2's complement are at logic `0' for add operation.   The subtract micro operation L:   R A  ( R A - R B ) in 2's comp...
Read more

Design and Analysis of Algorithms - 2

by
Image
Implement functions to print n th Fibonacci number using iteration and recursive method. Compare the performance of two methods by counting number of steps executed on various inputs. Also draw a comparative chart. Code:   #include<stdio.h>   int count_ite=0; int count_rec=0; void febo_ite(int ); int febo_rec(int );   int main() {     int n,ans;     printf("Enter position of number: ");     scanf("%d",&n);     febo_ite(n);     ans=febo_rec(n);     printf("Using Recursion: %d th number is = %d\n",n,ans);     printf("No of Steps= %d\n\n",count_rec); }   void febo_ite(int n) {     count_ite++;     int next,i, first=0,second=1;     count_ite++;     if(n==0)     {         count_ite++;  ...
Read more

Design and Analysis of Algorithms - 1

by
Image
Implement a function for each of following problems and count the  number of steps executed/Time taken by each function on various  inputs and write complexity of each function. Also draw a  comparative chart. In each of the following function N will be passed  by user.                     1. To calculate sum of 1 to N number using loop.                     2. To calculate sum of 1 to N number using equation.                     3. To calculate sum of 1 to N numbers using recursion. Code:   #include <stdio.h> int count_loop=0; int count_rec=0; int count_eq=0;   int sum_loop(int n) {     int i,sum=0;     count_loop++;     for(i=1;i<=n;i++)     {         count_loop++; ...
Read more

Artificial Intelligence - 7

by
Image
  AIM: Write a program to build Multi-layer Perceptron to implement any Boolean functions as mentioned below without using any python packages. AND, OR, XOR, XNOR, NOR, NAND, NOT x1, NOT x2, NULL, IDENTITY, INHIBITION ( 𝑥 1 ∧ ¬ 𝑥 2), INHIBITION ( 𝑥 2 ∧ ¬ 𝑥 1), TRANSFER x1, TRANSFER x2, IMPLICATION ( 𝑥 1 ∨ ¬ 𝑥 2), IMPLICATION ( 𝑥 2 ∨ ¬ 𝑥 1)   Program: class  perceptronNeuron:      def   __init__ ( self ,  x ,  w ,  w0 ):         l = [ww  for  ww  in  x]         l.insert( 0 ,  1 )          self .x = l          self .y =  0         l = [ww  for  ww  in  w]         l.insert( 0 ,...
Read more