Почему переменная "q" в функции быстрой сортировки равна 7 после первой процедуры (вызова)

Question

Я реализовал алгоритм быстрой сортировки в C, но я не знаю, как q и r работают в функции quick_sort.Когда функция разделения возвращает i, то есть 1, она присваивает это значение q, но затем по какой-то причине q становится 7 и r становится 0.

int partitioning(int A[10], int p, int r);
void quick_sort(int A[10], int p, int r);

int main() {

    int A[10] = { 8, 7, 0, 20, 60, 5, 3, 7, 45, 1}, i;

    for (i = 0; i <= 9; i++) {
        printf(" %d ", A[i]);
    }
    printf("\n\nFinal Array\n\n");
    quick_sort(A, 0, 9);
    for (i = 0; i <= 9; i++) {
        printf(" %d ", A[i]);
    }

    return 0;
}

int partitioning(int A[10], int p, int r) {

    int tmp, i, x, j;
    x = A[r];
    i = p - 1;
    for (j = p; j <= r; j++) {
        if (A[j] < x) {
            i++;
            tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }
    i++;
    tmp = A[i];
    A[i] = A[r];
    A[r] = tmp;

    return i;
}

void quick_sort(int A[10], int p, int r) {
    int q;
    printf("%d\n", q);

    if (p < r) {
        q = partitioning(A, p, r);
        quick_sort(A, p, q - 1);
        quick_sort(A, q + 1, r);
    }
}

Answer 1

Когда вы используете переменную стека без инициализации, вы получаете любое значение в стеке:

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

#define ARRAY_SIZE(array) \
    (sizeof(array) / sizeof((array)[0]))

void print_array(int array[], size_t length) {
    printf("address of array = %p\n", array);
    for (int index = 0; index < length; index++) {
        printf("%10d ", array[index]);
    }
    printf("\n");
}

void a(void) {
    int array[] = {1, 2, 3, 4};
    print_array(array, ARRAY_SIZE(array));
}

void b(void) {
    int array[4];
    print_array(array, ARRAY_SIZE(array));
}

void c(int offset) {
    int array[4];
    // Now we try to access the stack of the caller
    print_array(&array[offset], ARRAY_SIZE(array));
}

int main(int argc, char *argv[]) {
    int offset = atoi(argv[1]);
    int array[] = {5, 6, 7, 8};
    print_array(array, ARRAY_SIZE(array));
    a();
    b();
    c(offset);
    return 0;
}

Вывод Linux (gcc)

$ ./scratch 20
address of array = 0x7ffcab0a85c0
         5          6          7          8 
address of array = 0x7ffcab0a8570
         1          2          3          4 
address of array = 0x7ffcab0a8570
         1          2          3          4 
address of array = 0x7ffcab0a85c0
         5          6          7          8 

Выход MacOS (LLVM)

$ ./scratch 20
address of array = 0x7ffee91b0a50
         5          6          7          8 
address of array = 0x7ffee91b0a00
         1          2          3          4 
address of array = 0x7ffee91b0a00
         1          2          3          4 
address of array = 0x7ffee91b0a50
         5          6          7          8 

Вывод Windows 10 (Visual Studio 2019 - выпуск - x64)

C:> scratch.exe -4
address of array = 000000116676F830
         5          6          7          8 
address of array = 000000116676F820
         1          2          3          4 
address of array = 000000116676F820
         1          2          3          4 
address of array = 000000116676F830
         5          6          7          8 

Примечание

Мне нужно было создать версию Release проекта Visual Studio, чтобы заставить это работать. Версия «Отладка» имела защиту стека. Также обратите внимание, что смещение, необходимое для доступа к родительскому стеку, очень отличается.

Назначение

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

Неопределенное поведение

Многие опытные программисты на Си будут жаловаться на этот пример из-за "неопределенного поведения". Однако авторам компилятора приходится выбирать поведение. Таким образом, для данного компилятора поведение становится определенным.

Реализация против спецификации

Я думаю, что для программистов важно понимать, как разные компиляторы реализуют вещи, которые не определены в спецификации. Макеты стеков - это именно то, что авторы вредоносных программ исследуют при разработке своих программ. Есть причина, по которой этот сайт называется переполнением стека.