Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
4.4 kB
1
Indexable
Never
/*merge sort*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int comp = 0;
void print(int *arr,int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
}

void merge(int *arr,int s,int e)
{

    int i;
    int mid = (s + e)/2;
    int len1 = mid -s + 1;
    int len2 = e - mid;
    int mainArrIdx = s;
    int *arr1 = (int *)malloc(sizeof(int)*len1);
    int *arr2 = (int *)malloc(sizeof(int)*len2);
    for(i=0;i<len1;i++)
    {
        arr1[i] = arr[mainArrIdx++];
    }
    for(i=0;i<len2;i++)
    {
        arr2[i] = arr[mainArrIdx++];
    }
    mainArrIdx = s;
    int idx1,idx2;
    idx1=idx2=0;
    while(idx1<len1 && idx2<len2)
    {
        if(arr1[idx1]<= arr2[idx2])
        {
            arr[mainArrIdx++] = arr1[idx1++];
                comp++;
        }
        else
        {
            arr[mainArrIdx++] = arr2[idx2++];
                comp++;
        }
    }
    while(idx1 < len1)
    {

        arr[mainArrIdx++]=arr1[idx1++];
    }
    while(idx2<len2)
    {
        arr[mainArrIdx++] = arr2[idx2++];
    }
    free(arr1);
    free(arr2);
}

void mergesort(int *arr,int s,int e)
{
    if(s>=e)
    {
        return;
    }
    int mid = (s+e)/2;
    mergesort(arr,s,mid);
    mergesort(arr,mid+1,e);
    merge(arr,s,e);
}

int main()
{
    FILE* fptr = NULL;
    printf("\n For 1000 thousand elements \n");
    int i = 0;
    int n = 1000;
    int* arr = (int*)malloc(sizeof(int)*n);
    fptr = fopen("thousandRand.txt", "r");
    while(fscanf(fptr, "%d", &arr[i]) != EOF) i++;
    mergesort(arr, 0, n - 1);
    printf("No of comparisions (When elements are random) : %d \n", comp);
    comp = 0;
    fclose(fptr);

    i = 0;
    n = 1000;
    arr = (int*)malloc(sizeof(int)*n);
    fptr = fopen("thousandInc.txt", "r");
    while(fscanf(fptr, "%d", &arr[i]) != EOF) i++;
    mergesort(arr, 0, n - 1);
    printf("No of comparisions (When elements are in increasing order) : %d \n", comp);
    comp = 0;
    fclose(fptr);

    i = 0;
    n = 1000;
    arr = (int*)malloc(sizeof(int)*n);
    fptr = fopen("thousandDec.txt", "r");
    while(fscanf(fptr, "%d", &arr[i]) != EOF) i++;
    mergesort(arr, 0, n - 1);
    printf("No of comparisions (When elements are decreasing order) : %d \n", comp);
    comp = 0;
    fclose(fptr);

    printf("\n For 10000 elements \n");
    i = 0;
    n = 10000;
    arr = (int*)malloc(sizeof(int)*n);
    fptr = fopen("tenThousandRand.txt", "r");
    while(fscanf(fptr, "%d", &arr[i]) != EOF) i++;
    mergesort(arr, 0, n - 1);
    printf("No of comparisions (When elements are random) : %d \n", comp);
    comp =0;
    fclose(fptr);

    i = 0;
    n = 10000;
    arr = (int*)malloc(sizeof(int)*n);
    fptr = fopen("tenThousandInc.txt", "r");
    while(fscanf(fptr, "%d", &arr[i]) != EOF) i++;
    mergesort(arr, 0, n - 1);
    printf("No of comparisions (When elements are in increasing order) : %d \n", comp);
    comp = 0;
    fclose(fptr);

    i = 0;
    n = 10000;
    arr = (int*)malloc(sizeof(int)*n);
    fptr = fopen("tenThousandDec.txt", "r");
    while(fscanf(fptr, "%d", &arr[i]) != EOF) i++;
    mergesort(arr, 0, n - 1);
    printf("No of comparisions (When elements are decreasing order) : %d \n", comp);
    comp = 0;
    fclose(fptr);

    printf("\n For 100000 elements \n");
    i = 0;
    n = 100000;
    arr = (int*)malloc(sizeof(int)*n);
    fptr = fopen("oneLacRand.txt", "r");
    while(fscanf(fptr, "%d", &arr[i]) != EOF) i++;
    mergesort(arr, 0, n - 1);
    printf("No of comparisions (When elements are random) : %d \n", comp);
    comp = 0;
    fclose(fptr);

    i = 0;
    n = 100000;
    arr = (int*)malloc(sizeof(int)*n);
    fptr = fopen("oneLacInc.txt", "r");
    while(fscanf(fptr, "%d", &arr[i]) != EOF) i++;
    mergesort(arr, 0, n - 1);
    printf("No of comparisions (When elements are in increasing order) : %d \n", comp);
    comp = 0;
    fclose(fptr);

    i = 0;
    n = 100000;
    arr = (int*)malloc(sizeof(int)*n);
    fptr = fopen("oneLacDec.txt", "r");
    while(fscanf(fptr, "%d", &arr[i]) != EOF) i++;
    mergesort(arr, 0, n - 1);
    printf("No of comparisions (When elements are decreasing order) : %d \n", comp);
    fclose(fptr);

    return 0;
}