Быстрая сортировка рекурсивной функции в C - не работает с большим количеством элементов - PullRequest
Новая
       18

Быстрая сортировка рекурсивной функции в C - не работает с большим количеством элементов

0 голосов
/ 19 октября 2018

Правильно ли написана эта функция?

Кажется, что-то не так, когда я пытаюсь запустить функцию с большим количеством элементов в массиве (например, 1000).

Затем кажется, что он останавливается. 

int quick_sort(int n, int tablica[],int b, int a)
    {   
        if(a==n-1 || n==0) return;
        if(b==n-1) 
        {
            b=0;
            a++;        
        }

        if(tablica[b]>tablica[b+1])
        {
            bufor=tablica[b];
            tablica[b]=tablica[b+1];
            tablica[b+1]=bufor;
        }
        b++;
        return quick_sort(n,tablica,b,a);
    }

1 Ответ

0 голосов
/ 20 октября 2018

Приведенный выше код не будет работать даже для небольшого массива, если только небольшой массив не отсортирован определенным образом.Он сравнивает один элемент со следующим.Если массив скажет {4,3,8,7,1}, сортировка не удастся, потому что у него нет механизма, чтобы выдвинуть 1 в начало массива.

Для больших массивов слишком много рекурсии, и программа попадает в стекограничить и просто потерпеть неудачу.

Вы можете использовать рекурсию в быстрой сортировке, но количество рекурсий необходимо контролировать.Например, для массива размером 1000 вы не хотите иметь более 1000 рекурсий.Пример: 

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

void quicksort(int arr[], int low, int high)
{
    if(low < high)
    {
        int pivot = arr[high];    
        int i = (low - 1);  
        for(int j = low; j <= high - 1; j++)
        {
            if(arr[j] <= pivot)
            {
                i++;    
                swap(&arr[i], &arr[j]);
            }
        }
        swap(&arr[i + 1], &arr[high]);
        int pi = i + 1;

        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

int main()
{
    int arr[] = { 7,3,6,1,4,8,9,2 };
    int arrsize = sizeof(arr) / sizeof(*arr);
    quicksort(arr, 0, arrsize - 1);
    for(int i = 0; i < arrsize; i++)
        printf("%d\n", arr[i]);
    return 0;
}
...