Valgrind 报告排序算法的分区函数堆栈溢出：无法弄清楚原因

Question

我正在实施排序算法。调用分区函数。我在这里遇到堆栈溢出，但我不知道为什么。这是错误报告：

==2744== Memcheck, a memory error detector
==2744== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2744== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==2744== Command: ./pa5 -q 1M.b outputMq.b
==2744==
==2744== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==2744==
==2744== Process terminating with default action of signal 11 (SIGSEGV)
==2744==  Access not within mapped region at address 0x1FFE801FF8
==2744== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==2744==    at 0x400A1C: partition (sorting.c:7)
==2744==    by 0x400BA3: qhelper (sorting.c:39)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==    by 0x400BE0: qhelper (sorting.c:42)
==2744==  If you believe this happened as a result of a stack
==2744==  overflow in your program's main thread (unlikely but
==2744==  possible), you can try to increase the size of the
==2744==  main thread stack using the --main-stacksize= flag.
==2744==  The main thread stack size used in this run was 8388608.
==2744== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==2744==
==2744== Process terminating with default action of signal 11 (SIGSEGV)
==2744==  Access not within mapped region at address 0x1FFE801FC0
==2744== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==2744==    at 0x4A24735: _vgnU_freeres (vg_preloaded.c:77)
==2744==  If you believe this happened as a result of a stack
==2744==  overflow in your program's main thread (unlikely but
==2744==  possible), you can try to increase the size of the
==2744==  main thread stack using the --main-stacksize= flag.
==2744==  The main thread stack size used in this run was 8388608.
==2744==
==2744== HEAP SUMMARY:
==2744==     in use at exit: 8,000,000 bytes in 1 blocks
==2744==   total heap usage: 2 allocs, 1 frees, 8,000,568 bytes allocated
==2744==
==2744== LEAK SUMMARY:
==2744==    definitely lost: 0 bytes in 0 blocks
==2744==    indirectly lost: 0 bytes in 0 blocks
==2744==      possibly lost: 0 bytes in 0 blocks
==2744==    still reachable: 8,000,000 bytes in 1 blocks
==2744==         suppressed: 0 bytes in 0 blocks
==2744== Rerun with --leak-check=full to see details of leaked memory
==2744==
==2744== For counts of detected and suppressed errors, rerun with: -v
==2744== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
make: *** [test1] Segmentation fault (core dumped)

这些是相关函数：

 6 int partition (long *Array,int low,int high)
  7 {
  8   //int mid = (high-low)/2;
  9   long pvt = Array[low];
 10   int down = low;
 11   int up = high;
 12   while (down < up)
 13   {
 14     while((Array[down] <= pvt) && down < high)
 15     {
 16       down++;
 17     }
 18     while (Array[up] > pvt)
 19     {
 20       up--;
 21     }
 22     if (down < up)
 23     {
 24       long temp = Array[down];
 25       Array[down] = Array[up];
 26       Array[up] = temp;
 27     }
 28   }
 29   Array[low] = Array[up];
 30   Array[up] = pvt;
 31   return up;
 32 }
 33 void qhelper(long *Array,int low,int high,int Size,int pvtidx)
 34 {
 35   if (Size == 0 || Size == 1)
 36   {
 37     return;
 38   }
 39   pvtidx = partition(Array,low,high);
 40   if ((high - pvtidx) > (pvtidx - low))
 41   {
 42     qhelper(Array,low,pvtidx-1,Size,pvtidx);
 43     qhelper(Array,pvtidx+1,high,Size,pvtidx);
 44   }
 45   else
 46   {
 47     qhelper(Array,pvtidx+1,high,Size,pvtidx);
 48     qhelper(Array,low,pvtidx-1,Size,pvtidx);
 49   }
 50 }
 51 void Quick_Sort(long *Array, int Size)
 52 {
 53   int high = Size - 1;
 54   int low = 0;
 55   int pvtidx = 0;
 56   qhelper(Array,low,high,Size,pvtidx);
 57   return;
 58 }

有没有人知道为什么会发生这种情况/如何解决这个问题？据我所知，我的实现很好，我找不到任何错误。

Answer 1

我认为你有无限递归。

在 qhelper 的顶部，您的 if (Size == 0 || Size == 1) return; 将不起作用，因为 Size 是不变的。

也就是说，对于 [递归] 子调用，您永远不会相应地减少 Size，因此顶部的早期转义 if 将始终为假。

我见过的大多数实现都使用（例如）if (low >= high) 等。阿尔。并且根本不传递大小参数。

Valgrind 报告排序算法的分区函数堆栈溢出：无法弄清楚原因

Valgrind reporting stack overflow at partition function for sorting algorithim: can't figure out why

c

stack-overflow

sorting

valgrind