Learn 6 Sorting Algorithm in ONE CODE!

Mahmudul Hasan December 03, 2020 0

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<limits.h>
#include<stdbool.h>

int n;
int* input;

void swap(int* a, int* b)
{
    int temp=*a;
    *a=*b;
    *b=temp;
}
//Taking User input
void userinput()
{
    printf("Enter array size:");
    scanf("%d\n",&n);
    input = (int*)malloc(n*sizeof(int));
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&input[i]);
    }
}
//Printing result
void result()
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%d ",input[i]);
    }
    free(input);
    printf("\n");
}
//1. Insertion Counting
void insertion()
{    
    int i,j,key;
    for(i=1;i<n;i++)
    {
        key=input[i];
        j=i-1;
        while(j>=0 && input[j]>key)
        {
            input[j+1]=input[j];
            j--;
        }
        input[j+1]=key;
    }
}
//2. Bubble Sorting
void bubble()
{
    int i,j;

    for(int i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if(input[j]>input[j+1])
            {
                swap( &input[j], &input[j+1] );
            }
        }
    }
}
//3. Selection sort
void selection()
{
    int i,j;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(input[i]>input[j])
            {
                swap( &input[i], &input[j]);
            }
        }
    }    
}
//4. Counting Sorting
void counting()
{    
    int i,j;
    int mx= INT_MIN;
    int mn= INT_MAX;

    for(i=0;i<n;i++)
    {
        if(input[i]>mx) mx=input[i];
        if(input[i]<mn) mn=input[i];
    }
    int range=mx-mn+1;
    int* aux;
    aux=(int*)calloc(range,sizeof(int));

    for(i=0;i<n;i++)
    {
        aux[input[i]-mn]+=1;
    }
    for(i=1;i<range;i++)
    {
        aux[i]+=aux[i-1];
    }
    int* output;
    output=(int*)calloc(n,sizeof(int));
    for(i=n-1;i>=0;i--)
    {
        output[aux[input[i]-mn]-1]=input[i];
        aux[input[i]-mn]-=1;
    }
    free(aux);
    for(i=0;i<n;i++)
    {
        input[i]=output[i];
    }
    free(output);
}
//using for radix sort
void cntSort(int e)
{
    int* aux;
    int i,j;
    aux = (int*)calloc(10,sizeof(int));

    for(i=0;i<n;i++)
    {
        aux[ (input[i]/e) % 10]+=1;
    }
    for(i=1;i<10;i++)
    {
        aux[i]+=aux[i-1];
    }
    int* output;
    output = (int*)calloc(n,sizeof(int));
    for(i=n-1;i>=0;i--)
    {
        output[ aux[(input[i]/e)%10]-1] = input[i];
        aux[(input[i]/e)%10]--;
    }
    for(i=0;i<n;i++)
    {
        input[i]=output[i];
    }
    free(output);
    free(aux);
}
//5. Radix Sort
void radix()
{  
    int i,j;
    int mx= INT_MIN;

    for(i=0;i<n;i++)
    {
        if(input[i]>mx) mx=input[i];
    }
    int e;
    for(e=1;mx/e>0;e*=10)
    {
        cntSort(e);
    }
}
// 6. Bucket sort
void bucket()
{  
    int i,j,k,num;
    printf("Enter the Array size:");
    scanf("%d",&num);
    
    double* arr=(double*)malloc(num*sizeof(double));

    for(i=0;i<num;i++)
    {
        scanf("%lf",&arr[i]);
    }

    double b[30][100];
    int cnt[30];
    memset(cnt,0,sizeof(int));

    for(i=0;i<num;i++)
    {
        int bi=num*arr[i];
        
        b[bi][cnt[bi]++]=arr[i];
    }

    for(i=0;i<30;i++)
    {
        for(k=1;k<cnt[i];k++)
        {
            double key= b[i][k];
            j=k-1;
            while(j>=0 && b[i][j]>key)
            {
                b[i][j+1]=b[i][j];
                j--;
            }
            b[i][j+1]=key;
        }
    }
    int index=0;

    for(i=0;i<30;i++)
    {
        for(j=0;j<cnt[i];j++)
        {
            arr[index++]=b[i][j];
        }
    }

    for(i=0;i<num;i++)
    {
        printf("%0.3lf ",arr[i]);
    }
    free(arr);
    printf("\n");
}


int main()
{
    int a;
    printf("Enter your Choice:\n1. Insertion Sort\n2. Bubble Sort\n3. Selection Sort\n4. Counting Sort\n5. Radix Sort\n6. Bucket Sort\n***Enter 0 to exit.\n");
    while(1)
    {
        scanf("%d",&a);
        switch(a)
        {
            case 1:
            {
                printf("Insertion sort\n");
                userinput();
                insertion();
                result();
                break;
            }
            case 2:
            {
                printf("Bubble sort\n");
                userinput();
                bubble();
                result();
                break;
            }
            case 3:
            {
                printf("Selection sort\n");
                userinput();
                selection();
                result();
                break;
            }
            case 4:
            {
                printf("Counting sort\n");
                userinput();
                counting();
                result();
                break;
            }
            case 5:
            {
                printf("Radix sort\n");
                userinput();
                radix();
                result();
                break;
            }
            case 6:
            {
                printf("Bucket sort\n");
                bucket();
                break;
            }
            
            case 0:
            {
                //printf("Program Terminated.\n");
                break;
            }
            default:
            {
                //printf("Program Terminated.\n");
                break;
            }

        }
        if(a==0)
        {
            printf("Program Terminated.\n");
            break;
        }
               
    }

    return 0;
}

No comments

Subscribe to: Post Comments ( Atom )