CODEWITHSUNDEEP
cinfinite-loopquicksort
João Rodrigues
João Rodrigues

Reputation: 63

Language C - QuickSort

I was trying to code a quick sort program in c, and my recursive function is in an infinite loop.

The problem is:

You have been given an array A of size N.This array contains integers ranging from 1 to 10^9. You need to sort the contents of this array by their value and then print the contents of it.

Input Format:

The first line contains a single integers N denoting the size of the array. The next line contains N space separated integers denoting the contents of the array.

Output Format:

Print N space separated integers, i.e. the final sorted array.

Constraints:

1≤N≤10^6

1≤A[i]≤10^9

void fill_vet(unsigned int a[], unsigned int n){
    int i;
    for(i=0; i<n; i++)
        scanf("%u", &a[i]);
}

void print_vet(unsigned int a[], unsigned int n){
    int i;
    for(i=0; i<n; i++)
        printf("%u ", a[i]);
}

int partition(unsigned int a[], int start, int end){
    int i, j;
    unsigned int pivot, n_swap;
    i = start + 1;
    pivot = a[start];
    for(j = start+1; j<=end; j++){
        if(a[j] < pivot){
            n_swap = a[j];
            a[j] = a[i];
            a[i] = n_swap;
            i++;
        }
    } 
    n_swap = a[i-1];
    a[i-1] = a[start];
    a[start] = n_swap;
    return i-1;
}

void sort_array(unsigned int a[], int start, int end){
    while(start < end){
        int pos_piv = partition(a, start, end);
        sort_array(a, start, pos_piv-1);
        sort_array(a, pos_piv+1, end);
    }
}

int main()
{
    unsigned int n, a[100000];
    scanf("%u", &n);
    fill_vet(a, n);
    sort_array(a, 0, n-1);
    print_vet(a, n);
    return 0;
}

Can you tell me where is the error pls!

Upvotes: 0

Views: 54

Answers (1)

Geoduck
Geoduck

Reputation: 9005

You are using recursion so you don't need a loop:

void sort_array(unsigned int a[], int start, int end){
  if(start < end){
    int pos_piv = partition(a, start, end);
    sort_array(a, start, pos_piv-1);
    sort_array(a, pos_piv+1, end);
  }
}

Upvotes: 2

Related Questions