Бесконечное вычисление qsort

Question

Я использую алгоритм qsort, согласно Корману. Но есть бесконечные вычисления, когда я пытаюсь запустить его. Полагаю, эта проблема находится в разделе. Мои ПРОГРАММЫ считывает из файла, первый номер в файле-линии подсчета чисел для сортировки, а затем идут все номера

#include <stdio.h> 
#include <stdlib.h> 

int swap(int &a, int &b); 
int sorting(int *array, int &b, int &l); 
int partition(int *array ,int &begin, int &last); 


int main() 
{ 
    FILE* pFile=fopen("input.txt", "r"); 
    //fopen("input.txt", "r"); 
    //fopen("output.txt", "w"); 
    int n; 
    int begin=0; 
    fscanf(pFile, "%d", &n); 
    int* array=(int*)malloc(n*sizeof(int)); 
    for (int i=0; i<n; ++i) 
     fscanf(pFile,"%d", &array[i]); 
    int n1=n-1; 
    sorting(array, begin, n1); 
    printf("JJJJ"); 
    for (int i=0; i<n; ++i) 
     printf("%d ", array[i]); 
    printf("\n"); 
    fclose(pFile); 
    free(array); 
    return 0; 
} 

int sorting(int* array, int &b, int &l) 
{ 
    int pivot,pivot1; 
    if(b<l) 
    { 
     pivot=partition(array, b, l); 
     printf("MAXMAX321"); 
     int a=pivot-1; 
     sorting(array, b, a); 
     printf("MAXMAX123"); 
     pivot1=pivot+1; 
     sorting(array, pivot1, l); 
     printf("MAXMAX"); 
    } 
    return 0; 
} 

int partition(int* array, int &b, int &l) 
{ 
    int x=array[b]; 
    int i=b; 
    int j=l; 
    while(true) 
    { 
     while(array[j]>x){ 
      printf("AHAH"); 
      --j; 
     } 
     while(array[i]<x){ 
      printf("AZAZA"); 
      ++i; 
     } 
     if(i<j) 
      swap(array[i],array[j]); 
     else 
      return j; 

    } 
} 

int swap(int &x, int &y) 
{ 
    x=x+y; 
    y=x-y; 
    x=x-y; 
    return 0; 
} 

Спасибо заранее.

Answer 1

Я не могу понять, что вы делаете в функции раздела, но делать это, как это должно работать:

int partition(int* array, int &b, int &l) 
{ 
    int pivot_index = l;//You can take here everything between b and l 
    //swap(array[l], array[pivot_index]); decomment this if your pivot is between b and l 
    int current_pos = b; 
    for(int i = b;i < l - 1; ++i) 
     if(array[i] <= array[pivot_index]) 
      swap(array[i], array[current_pos++]); 
    swap(array[l], array[current_pos]); 
    return current_pos; 
} 

Answer 2

Эта часть очень опасный код:

while(true) 
{ 
    while(array[j]>x){ 
     printf("AHAH"); 
     --j; 
    } 
    while(array[i]<x){ 
     printf("AZAZA"); 
     ++i; 
    } 
    if(i<j) 
     swap(array[i],array[j]); 
    else 
     return j; 

} 

1. Избегайте while (true) столько, сколько возможно, за исключением особого случая, у вас должно быть четкое условие, указанное в цикле. Здесь он ведет к возврату. Это прояснит цель цикла.
2. При тестировании значения массива как while(array[i]<x) сравните i с размером массива раньше! Вы никогда не будете уверены, что вы всегда будете удовлетворены в массиве, убедитесь, что у вас есть пояс безопасности.