реализация quicksort в c

Question

void qkSort (int *arr,int size) 
{ 
    if (size>1) 
    { 
     int p = partition(arr,size); 
    qkSort(arr,p); 
    qkSort(arr+p+1,size-(p-1)); 
    } 
    return; 
} 

int partition(int *arr,int size) 
{ 
    int i,j,pivot,temp; 
    pivot = size-1; 
    for(i=0,j=-1;i<size-1;++i) 
    { 
     if (arr[i]<arr[pivot]) 
     { 
      ++j; 
      if(i!=j) 
      { 
       temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 
      } 
     } 
    } 

    temp = arr[pivot]; 
    arr[pivot] = arr[j+1]; 
    arr[j+1] = temp; 

    pivot = j+1; 

    return pivot; 
} 

Программа зависает. Мониторинг переменных с помощью gdb показывает, что второй рекурсивный вызов не передаёт его аргумент правильно. Пожалуйста помоги! Заранее спасибо!

Answer 1

Ваш расчет размера 2-го массива неправильный.

qkSort(arr+p+1,size-(p-1)); 

Это будет работать.

qkSort(arr+p+1,(size-p)-1); 

Answer 2

Пожалуйста, обратитесь к: http://p2p.wrox.com/visual-c/66347-quick-sort-c-code.html

Этот пример должен помочь вам начать работу.