c再帰によるソート

Question

再帰だけでソート関数を記述しようとしています。

lvalue required as unary '&' operand 

これは私が使用している機能は次のとおりです：

void sorter_rec (int a[], int n) { 
    if (n ==1) return; 
    else { 
     swap(&(maximumrec(a,n)), &a[n-1]); 
     sorter_rec(a,n-1); 
     return; 
    }; 
} 

エラーがsorter_recである私はエラーを得続けます。

void swap(int *px, int *py) 
{ int z = *px; 
    *px = *py; 
    *py = z; 
    return; 
} 

int maximumrec(int ar[], int n) 
{ 

    if (n == 1) { 
     return ar[0]; 

    } else { 
     int max = maximumrec(ar, n-1); 
     return ar[n-1] > max ? ar[n-1] : max; 
    } 
} 

どうすればこの問題を解決できますか？

Answer 1

基本的なアルゴリズムが機能します。私がしなければならなかったのは、あなたがポインタを渡したやり方を修正して初めてでした！お役に立てれば。私は自分のスタイルに合わせていくつかの名前を変更し、いくつかの便利なもの（マクロとロギングメソッド）とmain（）を追加しました。配列の名前が&配列と同じである

注[0]

#include <stdio.h> 
#define INT_COUNT(n) (sizeof(n)/sizeof(int)) 

void dumpIntArray(int *array, int n) { 
    printf("{ "); 
    for (int i = 0; i < n; i++) { 
     printf("%d ", array[i]); 
    } 
    printf(" }\n"); 
} 

void swap(int *px, int *py) { 
    int z = *px; 
    *px = *py; 
    *py = z; 
    return; 
} 

int *ptrToMax(int *sortable, int n) { 
    if (n == 1) { 
     return sortable; 
    } else { 
     int *maximum = ptrToMax(sortable, n - 1); 
     return sortable[n - 1] > *maximum ? &sortable[n - 1] : maximum; 
    } 
} 

void quicksort(int *sortable, int n) { 
    if (n == 1) { 
     return; 
    } else { 
     swap(ptrToMax(sortable, n), &sortable[n - 1]); 
     quicksort(sortable, n - 1); 
     return; 
    } 
} 

int main(int argc, char **argv) { 
    int foo[] = { 1, 5, 3, 2, 4, 9, 10, 8, 7 }; 

    printf("Before:\n"); 
    dumpIntArray(foo, INT_COUNT(foo)); 

    quicksort(foo, INT_COUNT(foo)); 

    printf("After:\n"); 
    dumpIntArray(foo, INT_COUNT(foo)); 
} 

Answer 2

あなたが機能maximumrecによって返される一時的なオブジェクトにオペレータ&を適用しなくてもよいです。

また、配列の最後から選択したソートを使用している場合は、arrayの最後から最大要素も検索する必要があります。この場合、ソートアルゴリズムはより安定します。

ここでは、あなたのアプローチを使用する例示的なプログラムですが、検索する最大要素の代わりに最小要素を検索します。必要に応じて最大要素を検索するように書き直すことができます。

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

#define N 20 

int * min_element(int a[], size_t n) 
{ 
    int *min = a; 

    if (!(n < 2)) 
    { 
     min = min_element(a + 1, n - 1); 
     min = *min < *a ? min : a; 
    } 

    return min; 
} 

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

void sort(int a[], size_t n) 
{ 
    if (!(n < 2)) 
    { 
     int *min = min_element(a, n); 
     if (min != a) swap(a, min); 
     sort(a + 1, n - 1); 
    } 
} 

int main(void) 
{ 
    int a[N]; 

    srand((unsigned int)time(NULL)); 

    for (size_t i = 0; i < N; i++) a[i] = rand() % N; 

    for (size_t i = 0; i < N; i++) printf("%d ", a[i]); 
    printf("\n"); 

    sort(a, N); 

    for (size_t i = 0; i < N; i++) printf("%d ", a[i]); 
    printf("\n"); 

    return 0; 
} 

プログラムの出力は、 ``（、n）はint型maximumrecを機能させる

17 9 12 15 1 17 19 17 6 2 14 19 2 8 5 19 0 12 16 8 
0 1 2 2 5 6 8 8 9 12 12 14 15 16 17 17 17 19 19 19