Design and Analysis of Algorithms - 7

by

Implement program of Counting Sort.


Code:


#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

int count1=0;

void count_s(int arr1[],int n,int max);

 

int main()

{

    int n,i;

    float t1,t2;

    printf("Enter the length of array: ");

    scanf("%d",&n);

    int arr[n],ar[n];

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

    {

        ar[i]=i;

    }

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

    {

        arr[i] = rand()%n;

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

    }

    int max=0;

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

    {

        if(arr[i]>max)

        {

            max = arr[i];

        }

    }

    clock_t st2 = clock();

    count_s(arr, n, max);

    clock_t et2 = clock();

    t2 = ((double)(et2-st2))/CLOCKS_PER_SEC;

 

    printf("\nThe Count step is: %d",count1);

    count1=0;

    clock_t st1 = clock();

    count_s(ar,n,n-1);

    clock_t et1 = clock();

    t1 = ((double)(et1-st1))/CLOCKS_PER_SEC;

    printf("\nThe Count step is: %d",count1);

 

    printf("\n\n");

    printf("Time taken for Sorted Data:- %f\n",t1);

    printf("Time taken for Random Data:- %f",t2);

    return 0;

}

 

void count_s(int arr1[],int n,int max)

{

    int i,j,count=0;

    int max_arr[max+1];

    for(i=0;i<max+1;i++)

    {

        count1++;

        max_arr[i] = 0;

    }

    for(i=0;i<=max+1;i++)

    {

        count1++;

        count = 0;

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

        {

            count1++;

           if(arr1[j] == i)

           {

               count1++;

               count++;

           }

        }

        if(count == 0)

        {

            count1++;

            max_arr[i]=0;

        }

        else

        {

            count1++;

            if(i==max)

            {

                count1++;

                max_arr[i]=count;

            }

            else{

                    count1++;

                max_arr[i]=count;

            }

        }

    }

    printf("\n");

 

    for(i=0;i<max+1;i++)

    {

        count1++;

        int a=i;

        if(i==0)

        {

            count1++;

            max_arr[i]=a;

        }

        else

        {

            count1++;

            max_arr[i]=max_arr[i]+max_arr[a-1];

        }

    }

    int arr[n],a,b;

    printf("\n");

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

    {

        count1++;

        a = arr1[i];

            count1++;

            b = max_arr[a];

            count1++;

            max_arr[a]=max_arr[a]-1;

            count1++;

            arr[b] = a;

    }

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

    {

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

    }

}

 

Output:


 





 

 

 

 


Analysis Table

 

Time

N

Sorted Data

Random Data

5

0.000004

0.000015

50

0.000029

0.000038

500

0.000684

0.000678

5000

0.066813

0.064291

50000

5.517792

5.450424

 

 Step Count

N

Sorted Data

Random Data

5

87

76

50

3102

3083

500

256002

255828

5000

25060002

25058179

50000

1794367294

1794375673

 

 

 

 

 

 Analysis Chart:







Conclusion:


In this Practical, I understand to Implement program of Counting Sort.

Here counting sort is effective when range is not greater than number of objects to be sorted.

Counting sort used to sort the negative input values.

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 - 6

by
Image
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;     ...
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