Untitled

 avatar
unknown
plain_text
3 years ago
5.8 kB
4
Indexable
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int main()
{
    srand(time(0));
    FILE* fptr = NULL;
    int i;
    fptr = fopen("thousandRand.txt","w");
    for(i=0; i<1000; i++)
    {
        fprintf(fptr,"%d ",(rand()%1000+1));
    }
    fclose(fptr);
    fptr = fopen("thousandInc.txt","w");
    for(i=0; i<1000;i++)
    {
        fprintf(fptr,"%d ",i+1);
    }
    fclose(fptr);
    fptr = fopen("thousandDec.txt","w");
    for(i=0;i<1000;i++)
    {
        fprintf(fptr,"%d ",(1000-i));
    }
    fclose(fptr);
    fptr = fopen("tenThousandRand.txt","w");
    for(i=0; i<10000; i++)
    {
        fprintf(fptr,"%d ",(rand()%10000+1));
    }
    fclose(fptr);
    fptr = fopen("tenThousandInc.txt","w");
    for(i=0; i<10000;i++)
    {
        fprintf(fptr,"%d ",i+1);
    }
    fclose(fptr);
    fptr = fopen("tenThousandDec.txt","w");
    for(i=0;i<10000;i++)
    {
        fprintf(fptr,"%d ",(10000-i));
    }
    fclose(fptr);
    fptr = fopen("oneLacRand.txt","w");
    for(i=0; i<100000; i++)
    {
        fprintf(fptr,"%d ",(rand()%100000+1));
    }
    fclose(fptr);
    fptr = fopen("oneLacInc.txt","w");
    for(i=0; i<100000;i++)
    {
        fprintf(fptr,"%d ",i+1);
    }
    fclose(fptr);
    fptr = fopen("oneLacDec.txt","w");
    for(i=0;i<100000;i++)
    {
        fprintf(fptr,"%d",(100000-i));
    }
    fclose(fptr);
    return 0;
}
\\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;
}
Editor is loading...