Quicksort算法崩溃&调试帮助 [英] Quicksort algorithm crashing & debugging help

问题描述

亲爱的，



我被困在下面的代码上似乎无法弄清楚为什么它会一直崩溃。它应该是C语言中的一个简单的快速排序算法，但它在给我输入分段错误并在输入后崩溃。我用Dev C ++调试它，它表明它在quicksort的递归调用中崩溃了。任何人都可以指出在哪里？



此外，对于这样的程序，任何人都可以指出一个调试器或技术来帮我解决这个问题吗？我有其他这样的程序，我需要测试/练习，我不想继续像这样发布。提前全部谢谢。

Dear all,

I'm stuck on code below and can't seem to figure out why it keeps crashing. It's supposed to be a simple quicksort algorithm in C but it's giving me a segmentation fault and crashing after I enter the input. I debugged it with Dev C++ and it shows that it's crashing in the recursive calls of quicksort. Can anyone point out where?

Also, for a program like this, can anyone point out a debugger or technique that will help me fix this myself? I have other such programs that I will need to test / practice and I don't want to keep having to post like this. Thanks all in advance.

/* includes and macros */
// required for input / output with minGW GCC
#include <stdio.h>
#define printf __mingw_printf

// required for the random integer generator functions
#include <stdlib.h>
#include <time.h>


/* global declarations */
static unsigned short n;

/* function prototypes */
void swapSort(int *, int *);
void quickSortMid(int [], unsigned short, unsigned short);


int main()
{
    /* variable array declaration */
    printf("How many integers do you want sorted by Quick Sort? ");
    scanf("%hu", &n);
    int arrayInput[n];

    /* for rand() */
    srand(time(NULL));

    /* array input */
    printf("\n");
    for(register unsigned short i = 0; i <= n-1; i++)
        arrayInput[i] = rand();

    /* sort using the Quick Sort Medium algorithm */
    quickSortMid(arrayInput, 0, n-1);

    /* print the sorted array */
    printf("\n");
    for(register unsigned short i = 0; i <= n-1; i++)
        printf("[%d] ", arrayInput[i]);
    printf("\n");

    return 0;
}


/* function definitions */
void swapSort(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


void quickSortMid(int intArray[], unsigned short low, unsigned short high)
{
    unsigned short e = high / 2, hole = e, ul = high;
    int temp = intArray[e];
    while(low < high)
    {
        if(hole >= e)
        {
            if(intArray[low] > temp)
            {
                swapSort(&intArray[low], &intArray[hole]);
                hole = low;
            }
            else low++;
        }
        else
        {
            if(intArray[high] < temp)
            {
                swapSort(&intArray[high], &intArray[hole]);
                hole = high;
            }
            else high--;
        }
    }
    intArray[hole] = temp;

    // recursive calls of Quick Sort to completely sort the array
    if(e >= 2 && (ul-e) >= 2)
    {
        quickSortMid(intArray, 0, e-1);
        quickSortMid(intArray, e+1, ul);
    }
}

我的尝试：



我尝试使用Dev C ++进行调试，并将问题缩小到函数的递归调用，但似乎无法弄清楚逻辑有什么问题。



下载了许多不同的调试器并阅读了很多关于调试但没有什么能帮助我正确学习如何调试我自己的程序。如果这是一个简单的逻辑问题，那么我可以使用printf来查看排序错误的原因以及为什么程序崩溃。

What I have tried:

I have tried debugging with Dev C++ and have narrowed the problem to the recursive calls of the function but can't seem to figure out what's wrong with the logic.

Downloaded many different debuggers and read much on debugging but nothing that will help me learn properly how to debug my own programs. If this were a simple logic problem, then I could use printf to see where the sorting was wrong and why but the program is crashing.

推荐答案

引用：

另外，对于像这样的程序，有人能指出一个调试器或技术来帮我解决这个问题吗？

Also, for a program like this, can anyone point out a debugger or technique that will help me fix this myself?

任何调试器都可以。

你知道你的程序应该做什么以及变量应该如何表现。



你需要执行你的程序在调试器上逐行显示。

通过在程序运行时检查变量，你会看到变量是否按预期运行。

你找到程序的位置停止按预期行事，你接近错误。

当你有一个复杂的表达式给出错误的结果时，最好添加虚拟线条，将表达式的一部分暴露出来中间计算。



[更新]

w如果您在调试器中启动程序，您可以像平常一样运行它（或者像您一样）或者您可以告诉调试器（在菜单中）您想要单独执行该程序。

我不喜欢你不知道你的调试器菜单中的名字。

通常你有像步骤或跟踪

调试器允许你设置断点，它会在每次到达该点时停止程序。

Any debugger will do.
You know what your program should do and how the variables should behave.

You need to execute your program line by line on debugger.
By inspecting the variables while the program runs, you will see if variable behave as expected or not.
where you find where the program stops to behave as expected, you are close to the bug.
When you have a complex expression that give wrong results, it is a good idea to add dummy lines that take parts of the expression just to expose the intermediate calc.

[Update]
when you start a program in debugger, you can run it like normal (like you do) or you can tell the debugger (in the menus) that you want to single step in the program.
I don't know the name in your debugger menu.
usually you have" names like step or trace
the debugger allow you to set breakpoints that will stop the program each time it reach that point.

您可以通过这种方式分配arrayinput，因为n必须是常量才能完成。



像这段代码一样动态：

You can allocate the arrayinput this way, because n MUST be a constant to do it.

Make it dynamic like this code:

int *arrayInput = new int[n];
//do your stuff

//cleanup
delete arrayInput;

提示：不要混合ushort和int。它不是更快，但会导致奇怪的错误。

Tip: dont mix ushort and int. It isnt faster, but leads to strange bugs.

这篇关于Quicksort算法崩溃&调试帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！