João Rodrigues João Rodrigues - 3 years ago 54
C Question

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!

Answer Source

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);
  }
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download