Как предотвратить переполнение стека в моей реализации QuickSort? - PullRequest
Новая
       7

Как предотвратить переполнение стека в моей реализации QuickSort?

0 голосов
/ 10 октября 2019

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

Мой код: 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h> 
#include <time.h>
#include <stdbool.h>
#include <assert.h>
int Icmp(void* x, void* y);
bool SpecTest(int (*cmp)(const void*, const void*), int (*dcmp)(const void*, const void*));
int Dcmp(void* x, void* y);
void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*));

int main(void)
{
    int (*cmp)(void* x, void* y) = Icmp;
    int (*dcp)(void* x, void* y) = Dcmp;
    assert(SpecTest(cmp, dcp));
    return 0;
}

bool SpecTest(int (*cmp)(const void*, const void*), int (*dcmp)(const void*, const void*))
{
    typedef struct testArr {
        int* arr;
        size_t size;
    }testArr;
    testArr s3;//Back sorted array struct
    s3.size = 100;
    if ((s3.arr = (int*)malloc(sizeof(int) * s3.size)) == NULL) {
        return false;
    }
    for (int i = 0; i < s3.size; i++) {
        s3.arr[i] = s3.size - i;
    }
    my_qsort(s3.arr, s3.size, sizeof(s3.arr[0]), cmp);
    return checksortInt(s3.arr, s3.size, cmp);
}
int Icmp(void* x, void* y)
{
    return (*(int*)x > * (int*)y) - (*(int*)x < *(int*)y);
}

int Dcmp(void* x, void* y)
{
    return (*(double*)x > * (double*)y) - (*(double*)x < *(double*)y);
}

void Swapper(void* x, void* y, size_t size)
{
    for (size_t i = 0; i < size; i++) {
        char tmp = ((char*)x)[i];
        ((char*)x)[i] = ((char*)y)[i];
        ((char*)y)[i] = tmp;
    }
}

bool checksortInt(int* parray, size_t size)
{
    for (size_t i = 0; i < size - 1; i++)
        if (parray[i] > parray[i + 1])
            return false;
    return true;
}

void my_qsort(const void* ptr, size_t count, size_t size, int (*cmp)(const void*, const void*))
{
    Quick_Sort(ptr, 0, count - 1, size, cmp);
}

void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i = low;
    int j = high;
    char* pivot = (char*)ptr + low * size;
    while (i <= j)
    {
        while (i < high && (cmp((char*)ptr + i * size, pivot) == -1))
            i++;
        while (j > low && cmp((char*)ptr + j * size, pivot) == 1)
            j--;
        if (i <= j) {
            Swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
            i++;
            j--;
        }
    }
    if (j > low)
        Quick_Sort(ptr, low, j, size, cmp);
    if (i < high)
        Quick_Sort(ptr, i, high, size, cmp);
}

Пример:

Input []: Массив чисел в порядке убывания

Вывод []: Необработанное исключение при 0x005D1889 в QuickSout.exe: 0xC00000FD: переполнение стека (параметры: 0x00000001, 0x008A2F24).

1 Ответ

1 голос
/ 11 октября 2019

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

void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i;
    int j;
    char *pivot;
    while(low < high){
        i = low;
        j = high;
        pivot = (char*)ptr + ((low+high)/2) * size;
        while (i <= j)
        {
            while (cmp((char*)ptr + i * size, pivot) == -1)
                i++;
            while (cmp((char*)ptr + j * size, pivot) ==  1)
                j--;
            if (i <= j) {
                Swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
                i++;
                j--;
            }
        }
        if (j < low)                  // adjust so low <= j <= i <= high
            j = low;
        if (i > high)
            i = high;
        if(j - low <= high - i){
                Quick_Sort(ptr, low, j, size, cmp);
            low = j + 1;
        } else {
            if (i < high)
                Quick_Sort(ptr, i, high, size, cmp);
            high = i - 1;
        }
    }
}

Эта альтернативная версия немного проще. 

void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i;
    int j;
    char *pivot;
    while(low < high){
        i = low-1;
        j = high+1;
        pivot = (char*)ptr + ((low+high)/2) * size;
        while (1)
        {
            while (cmp((char*)ptr + ++i * size, pivot) == -1);
            while (cmp((char*)ptr + --j * size, pivot) ==  1);
            if (i >= j)
                break;
            Swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
        }
        if(j - low <= high - j){
            Quick_Sort(ptr, low, j, size, cmp);
            low = j+1;
        } else {
            Quick_Sort(ptr, j+1, high, size, cmp);
            high = j;
        }
    }
}

Альтернативная версия без предотвращения переполнения стека: 

void Quick_Sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i;
    int j;
    char *pivot;
    if(low >= high)
        return;
    i = low-1;
    j = high+1;
    pivot = (char*)ptr + ((low+high)/2) * size;
    while (1)
    {
        while (cmp((char*)ptr + ++i * size, pivot) == -1);
        while (cmp((char*)ptr + --j * size, pivot) ==  1);
        if (i >= j)
            break;
        Swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
    }
    Quick_Sort(ptr, low, j, size, cmp);
    Quick_Sort(ptr, j+1, high, size, cmp);
}
...