hoaresQuickshort

 avatar
user01
plain_text
2 years ago
1.6 kB
0
Indexable
Never
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int count=0;

void swap(int *x, int *y)
{
    int temp = *x;
    *x=*y;
    *y=temp;
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[low];
    int i = low - 1, j = high + 1;

    while (i<j)
    {
        do{i++;}while (arr[i] < pivot);
        do{j--;}while (arr[j] > pivot);

        if (i >= j)
        {
            return j;
        }
        swap(&arr[i], &arr[j]);
    }
}

void quickSort(int A[], int p, int r)
{
    if(p<r)
    {
        int q=partition(A,p,r);
        quickSort(A,p,q-1);
        quickSort(A,q+1,r);
    }
}

void display(int A[], int n)
{
    int i=0;
    for(i=0;i<=(n-1);i++)
        printf("%d ",A[i]);
}

int main()
{
    int n=10,i;


    int *A=(int *)malloc(sizeof(int)*n);

    FILE *fp;
    fp = fopen("Rand.txt", "r");
    i = 0;
    while (fscanf(fp, "%d", &A[i]) != EOF)
        i++;
    quickSort(A, 0, n-1);

    printf ("Comparisons for random elements: %d\n", count);
    fclose(fp);

    count = 0;

    fp = fopen("asc.txt", "r");
    i = 0;
    while (fscanf(fp, "%d", &A[i]) != EOF)
        i++;
    quickSort(A, 0, n-1);

    printf ("Comparisons for ascending elements: %d\n", count);
    fclose(fp);

    count = 0;
    fp = fopen("des.txt", "r");
    i = 0;
    while (fscanf(fp, "%d", &A[i]) != EOF)
        i++;
    quickSort(A, 0, n-1);

    printf ("Comparisons for descending elements: %d\n", count);
    fclose(fp);

    count = 0;

    return 0;
}