Quick Sort In C

 
#include<stdio.h>

int partition(int a[], int left, int right, int n)
{
    int piv, i, j, temp;
    piv = left;
    i = piv + 1;
    j = right;
    while(i<=j)
    {
        while(a[piv] < a[j] && piv < j)
        {
            j--;
        }
        if(a[piv] > a[j] && piv < j)
        {
            temp = a[piv];
            a[piv] = a[j];
            a[j] = temp;
            piv = j;
            j--;
        }
        while(a[i] < a[piv] && i < piv)
        {
            i++;
        }
        if(a[i] > a[piv] && i < piv)
        {
            temp = a[piv];
            a[piv] = a[i];
            a[i] = temp;
            piv = i;
            i++;
        }
    }
    return piv;
}
void QuickSort(int a[], int left, int right, int n)
{
    if(left < right)
    {
        int ind = partition(a, left, right, n);
        /*printf("ind = %d\n", ind);
        for(int i=0;i<n;i++)
            printf("%d ", a[i]);
        printf("\n");*/
        QuickSort(a, left, ind-1, n);
        QuickSort(a, ind+1, right, n);
    }
}
int main()
{
    int i, n, numbers[100];
    scanf("%d", &n);
    for(i=0;i<n;i++)
        scanf("%d", &numbers[i]);
    QuickSort(numbers, 0, n-1, n);
    printf("Sorted Output:\n");
    for(i=0;i<n;i++)
        printf("%d ", numbers[i]);
    printf("\n");
    return 0;
}

/*
Sample Input:
10 /*Number of integers*/
12 33 44 55 555 66 77 88 99 100

Sample Output:
Sorted Output:
12 33 44 55 66 77 88 99 100 555

*/

Attention: Quicksort time complexity has been discussed in this topic.

Post a Comment

Previous Post Next Post