Быстрая сортировка в C - указатели и память

Question

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

1. В основной функции, когда я вызываю раздел, я получил Несовместимые типы указателей

2. В функции обмена: поток 1: EXC_BAD_ACCESS (код = 1, адрес = 0x200000007)

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


void partition(int* array[], int size){
    int pivot = size;
    int i = - 1;
    for(int j = 0 ; j < size - 1 ; j++){
        if(array[j] < array[pivot]){
            i++;
            swap(array[i],array[j]);
        }
    }
}

int main() {
    int array[] = {7,2,1,8,6,3,5,4};
    int size = sizeof(array)/sizeof(array[0]);
    partition(&array,size);
    return 0;
}

Answer 1

Для начала, если массив имеет N элементов, тогда допустимый диапазон индексов равен [0, N-1]

Таким образом, есть попытка получить доступ к памяти вне массива

int pivot = size;
int i = - 1;
for(int j = 0 ; j < size - 1 ; j++){
    if(array[j] < array[pivot])
                       ^^^^^^^

Ваша функция подкачки не имеет смысла.

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

После первого выражения выражения

    *i = *j;

оба объекта, на которые указывают указатели i и j, будут иметь одинаковое значение.

Функция может быть определена следующим образом.

void swap( int *p, int *q )
{
    int tmp = *p;
    *p = *q;
    *q = tmp;
} 

и называется как

swap( &array[i], &array[j] );

Функциональный раздел также недействителен. Помимо некорректно используемого алгоритма, по крайней мере, его первый параметр объявлен также неправильно.

вместо

void partition( int* array[], int size );

функция должна быть объявлена ​​как

void partition( int *array, int size );

или более правильно, как

void partition( int *array, size_t size );

и функция должна вызываться как

int array[] = {7,2,1,8,6,3,5,4};
size_t size = sizeof(array)/sizeof(array[0]);
partition( array,size );

С другой стороны, функция partition должна возвращать позицию, которая делит массив на две части. Таким образом, окончательное объявление функции будет выглядеть как

size_t partition( int array[], size_t size );

Ниже приведена демонстрационная программа, показывающая, как можно быстро написать рекурсивную функцию быстрой сортировки с использованием функций swap и partition.

#include <stdio.h>

void swap( int *p, int *q )
{
    int tmp = *p;
    *p = *q;
    *q = tmp;
}

size_t partition( int a[], size_t n, int pivot )
{
    size_t i = 0;

    while ( i != n )
    {
        while ( i != n && a[i] < pivot ) i++;
        while ( i != n && !( a[--n] < pivot ) );

        if ( i != n ) swap( a + i, a + n );
    }

    return i;
}

void quick_sort( int a[], size_t n )
{
    if ( n != 0 )
    {
        size_t pos = partition( a, n - 1, a[n - 1] );
        swap( a + pos, a + n - 1 );

        quick_sort( a, pos );
        quick_sort( a + pos + 1, n - pos - 1 );
    }
}

int main(void) 
{
    int a[] = { 7, 2, 1, 8, 6, 3, 5, 4 };
    const size_t N = sizeof( a ) / sizeof( *a );

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

    putchar( '\n' );

    quick_sort( a, N );

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

    putchar( '\n' );

    return 0;
}

Вывод программы

7 2 1 8 6 3 5 4 
1 2 3 4 5 6 7 8 

Answer 2

pointers

Я не был уверен, задавался ли вопрос о быстрой сортировке на основе указателей, поэтому вот пример использования схемы разбиения Lomuto.В цикле разбиения он повторяется в меньшей части и возвращается в большую часть, ограничивая пространство стека O (log (n)), но сложность времени в худшем случае остается равной O (n ^ 2).

void QuickSort(int *lo, int *hi)
{
int *pi;
int *pj;
int pv;
int t;
    while (lo < hi){
        pv = *hi;                       /* pivot */
        pi = lo;                        /* partition */
        for (pj = lo; pj < hi; ++pj){
            if (*pj < pv){
                t = *pi;                /*  swap *pi, *pj */
                *pi = *pj;
                *pj = t;
                ++pi;
            }
        }
        t = *pi;                        /* swap *pi, *hi */
        *pi = *hi;                      /*  to place pivot */
        *hi = t;
        if(pi - lo <= hi - pi){         /* recurse on smaller part */
            QuickSort(lo, pi-1);        /*  loop on larger part */
            lo = pi+1;
        } else {
            QuickSort(pi+1, hi);
            hi = pi-1;
        }
    }
}

Answer 3

Здесь есть несколько проблем:

1. Обозначение указателя имеет странный эффект, что звезда идет после того, на что она указывает, поэтому раздел int* array[] - это массив указателей.к целым числам, в то время как то, что вы называете в main, это указатель на массив целых чисел.
2. Массив [] на самом деле сам по себе является указателем (хотя и с некоторыми незначительными техническими отличиями, но в целом это то, что принимаетуказатель также примет массив).Вы в основном используете массив в разделе как массив целых чисел (array[j] < array[pivot] должен быть сравнением содержимого, но с int* array[] это сравнение адреса), поэтому вы должны изменить его на int array[].Обратите внимание, что это также поможет с разрешением пункта 1, так как вам просто нужно удалить лишние ссылки, когда вы вызываете раздел.
3. Когда вы индексируете массив, это считается разыменованием, поэтому, когда вы вызываете swap(array[i],array[j]) (при условии, что вы внесли поправки, предложенные выше) вы передаете int с, а не int* с, вам нужно изменить его на swap(&array[i],&array[j]).
4. В свопе вы устанавливаете оба их значения на j,Это происходит потому, что информация о том, что находится внутри, уничтожается, когда вы пишете поверх него.Есть несколько способов справиться с этим, два основных - сохранить информацию во временную переменную, а второй - через битовый хакер.Вот 2 примера:

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

Версия, использующая эксклюзив или:

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