クイックソートアルゴリズム（再帰）

Question

私は見たyoutubeのアルゴリズムの視覚的な提示からクイックソートアルゴリズムを作りましたが、私の再帰は全く機能しません。私は、これらの2行をコメントアウトした場合:(

quicksort(array,0,start-1); 
quicksort(array,start+1,temp); 

は..プログラムがクラッシュしないと出力は、部分的に正しいです2,1,3,5,4となります..しかし、それは入ったときにそれがクラッシュします再帰クラッシャーへ

#include <stdio.h> 
#include <conio.h> 

void swap(int *a, int *b){ 

int temp = *a; 
*a = *b; 
*b = temp; 
} 

void quicksort(int *array, int start, int end){ 

int pivot = start; 
int temp = end;  
while(start != end){ 

if(pivot==start){ 
    if(array[pivot] > array[end]){ 
    swap(&array[end],&array[pivot]); 
    pivot = end; 
    start++; 
    } 
    else 
    end--; 
} 
else{ 
if(array[pivot] < array[start]){ 
    swap(&array[start],&array[pivot]); 
    pivot = start; 
    end--; 
} 
else 
start++; 

}    
} 

quicksort(array,0,start-1); 
quicksort(array,start+1,temp); 
} 




main(){ 

int x[5] = {3,1,5,2,4}; 
int i; 
quicksort(x,0,4); 
for(i=0;i<5;i++) 
printf("%d ", x[i]); 
getch(); 
} 

Answer 1

欠落している点は、アルゴリズムをキャンセルする点です。関数の制御フローをチェックすると、アプリケーションはこのパスに進むことができるすべてのパスに、quicksort関数が再び呼び出されることがわかります。あなたが終わった時を知ることは簡単です。パラメータstartとendが等しい場合には、をなしで終了して、quicksortを再度呼び出す必要があります。それはトリックを行う必要があります。

Answer 2

..スタートは終了と同じループになりながら、全体の後：あなたのコードでは、再帰のための終了条件が欠落していることは、入力範囲が空でもあることを意味します。 、あなたはまだ再帰呼び出しを入力します（アレイに負の符号が付いているため、クラッシュが発生する可能性があります）。

のような条件を追加する必要があります

if(there's at most 1 element in the input range) 
    return; // already sorted 

Answer 3

QuickSort Algorithm: 

    - QuickSort(A[], l, r) 
     - P = A[l] // Select pivot as the beginning element from array or you can do better //with good pivots. 
     - i = l + 1 // index i to be next of pivot 
     - for j = l + 1 to r 
     - if A[j] < P 
      - swap (A[j], A[i]) 
      - increment i 
     - end if 
    - end for 
    - swap (A[i-1], A[l]); 
    -- Call recursive on left partitioned array 
    -- Call recursive on right partitioned array. 




// QuickSort_2.cpp : Defines the entry point for the console application. 
// 

#include "stdafx.h" 

#define ARR_SIZE   200 
#define PR_ARR_SIZE   200 
unsigned int input_arr[ARR_SIZE]; 

void swap(unsigned int *a, unsigned int *b) 
{ 
    unsigned int tmp; 
    tmp = *a; 
    *a = *b; 
    *b = tmp; 
} 

void print_input(unsigned int input[], unsigned int l, unsigned int n) 
{ 
    unsigned int i; 
    for (i = l; i < n; i++) 
     printf("%d ", input[i]); 
    printf("\n"); 
} 

void QuickSort(unsigned int input[], unsigned int l, unsigned int r) 
{ 
    unsigned int i = l + 1, j; 
    unsigned int pivot = input[l]; 
    if (l + 1 < r) { 
     for (j = l + 1; j < r; j++) { 
      if (input[j] < pivot) { 
       swap(&input[j], &input[i]); 
       i++; 
      } 
     } 
     swap(&input[i - 1], &input[l]); 

     QuickSort(input, l, i); 
     QuickSort(input, i, r); 
    } 
} 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    unsigned int i = 0; 
    unsigned int val; 
    FILE *fp; 

    errno_t err = fopen_s(&fp, "IntegerArray.txt", "r+"); 
    if (err) { 
     printf("unable to open a file\n"); 
     return -1; 
    } 
    while (fscanf_s(fp, "%ld\n", &val) != EOF) { 
     input_arr[n++] = val; 
    } 

    print_input(input_arr, 0, n); 
    QuickSort(input_arr, 0, n); 
    print_input(input_arr, 0, n); 

    return 0; 
} 

Put these values in "IntegerArray.txt" file and 

2 
3 
4 
5 
6 
10 
11 
12 
1 
17 
18 
19 
20 
7 
8 
9 
13 
14 
15 
16