How to prevent stackoverflow in my implementation QuickSort?

0

I have problem with my QuickSort. When I try sort array of numbers in descending order my pointers don't go through the array, and my stack overflow. Maybe problem isn't in the pointers, but I don't see solution of this problem.

My code:

#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);
}

Example:

Input[]: Array of numbers in descending order

Output[]: Unhandled exception at 0x005D1889 in QuickSout.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x008A2F24).

c
quicksort
asked on Stack Overflow Oct 10, 2019 by Skiv Hisink • edited Oct 11, 2019 by Skiv Hisink

1 Answer

1

If you need to sort large arrays, and are concerned about worst case data patterns causing stack overflow, quicksort could recurse on the smaller partition and loop back for the larger partition, which will avoid stack overflow, but worst case time complexity will still be 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;
        }
    }
}

This alternate version is a bit simpler.

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;
        }
    }
}

Alternate version without the stack overflow prevention:

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);
}
answered on Stack Overflow Oct 11, 2019 by rcgldr • edited Oct 12, 2019 by rcgldr

User contributions licensed under CC BY-SA 3.0