Реализация быстрой сортировки на C приводит к значению мусора в arr [0]

Question

Рассмотрим следующий алгоритм:

void qsort(int arr[], int left, int right) {
        if (left < right) {
        int index = partition(arr, left, right);
        qsort(arr, left, index - 1);
        qsort(arr, index + 1, right);
    }
}

int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            ++i;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}

inline void swap(int* i, int* j) {
    int temp = *i;
    *i = *j;
    *j = temp;
}

После того, как я исправил ошибки сегмента, я заметил, что алгоритм всегда выдает значение мусора при arr[0].Таким образом, если входной массив: 5 5 1 3 7 0 0 0 3, то вывод будет -858993460 0 0 0 1 3 3 5 5.Я неоднократно запускал это через отладчик, и, тем не менее, до сих пор не знаю, откуда берется значение мусора.Более интересно то, что в Java почти такой же алгоритм работает отлично.

edit Начальная функция вызывается так: qsort(arr, 0, 9); где 9 - длина массива - 1.

Answer 1

Я подозреваю, что у вас возникла ошибка, когда вы инициализируете arr или как вы звоните qsort().Скорее всего, он вызывается с мусорным (неинициализированным) элементом либо в начале, либо в конце массива.Это также, вероятно, объясняет, почему наибольшее значение 7 отсутствует в выводе.

Если бы я продолжил рассуждать, я бы предположил, что в Java массив инициализируется нулями и, таким образом, вы получаете дополнительный ноль в выводе (что, возможно, вы пропускаете среди других нулей?)

edit: начальная функция вызывается так: qsort(arr, 0, 9); где 9 -длина массива - 1.

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

Моя следующая гипотеза состоит в том, что, отсортировав массив из десяти элементов (9 вещественных + 1 мусор), вы затем распечатываете только первые девять элементов.Это будет учитывать отсутствие в вашем выводе 7 (оно является самым большим и поэтому помещается в последнее место, которое не распечатывается).

PS Если я могу предложить некоторыенежелательный совет для будущих вопросов, размещение Minimal, Complete и Verifiable пример сделает всю эту отладку по предположению совершенно ненужной, так как мы сможем сразу увидеть, что точно происходит с вашим кодом.:)

Answer 2

Если вы вызываете функцию с размером вместо индекса самого правого элемента (который является size - 1), вы получаете доступ к массиву за пределами.

Этот код работает:

#include <stdio.h>

static
inline void swap(int *i, int *j)
{
    int temp = *i;
    *i = *j;
    *j = temp;
}

static
int partition(int arr[], int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++)
    {
        if (arr[j] <= pivot)
        {
            ++i;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}

static
void qsort(int arr[], int left, int right)
{
    if (left < right)
    {
        int index = partition(arr, left, right);
        qsort(arr, left, index - 1);
        qsort(arr, index + 1, right);
    }
}

static void dump_array(const char *tag, int size, int *arr)
{
    printf("%s (%d):", tag, size);
    for (int i = 0; i < size; i++)
        printf(" %d", arr[i]);
    putchar('\n');
}

int main(void)
{
    int arr[] = { 5, 5, 1, 3, 7, 0, 0, 0, 3, };
    enum { ARR_SIZE = sizeof(arr) / sizeof(arr[0]) };

    dump_array("Before", ARR_SIZE, arr);
    qsort(arr, 0, ARR_SIZE - 1);
    dump_array("After", ARR_SIZE, arr);
    return 0;
}

Вывод:

Before (9): 5 5 1 3 7 0 0 0 3
After (9): 0 0 0 1 3 3 5 5 7