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.

Также, если вы используете сортировку выбора, начиная с конца массива, тогда следует также искать максимальный элемент, начиная с конца массива. В этом случае алгоритм сортировки будет более стабильным.

Вот демонстративная программа, которая использует ваш подход, но вместо поиска максимального элемента он ищет минимальный элемент. Вы можете переписать его таким образом, чтобы он искал максимальный элемент, если хотите.

#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; 
} 

Выход программы может выглядеть

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