快速排序的分段错误-解网

问：

我需要对我的大学作业进行快速排序。以下是我用 c++ 编写的快速排序实现：

#include <iostream>
#include <algorithm>
#include <cstddef>
#include <utility>

template<typename T, std::size_t S>
void quick_forward_order(T(&container)[S], std::size_t lower_bound = std::size_t(0), std::size_t upper_bound = S - 1)
{
    if(lower_bound >= upper_bound)
    {
        return;
    }

    // Choosing the last element as the pivot
    const T& pivot_element = container[upper_bound];

    std::size_t rhs_pointer = upper_bound;
    std::size_t lhs_pointer = lower_bound;

    while (lhs_pointer < rhs_pointer)
    {
        while(container[lhs_pointer] <= pivot_element && lhs_pointer < rhs_pointer)
        {
            ++lhs_pointer;
        }

        while(container[rhs_pointer] >= pivot_element && rhs_pointer > lhs_pointer)
        {
            --rhs_pointer;
        }

        std::swap(
            container[lhs_pointer],
            container[rhs_pointer]
        );
    }

    std::swap(
        container[lhs_pointer],
        container[upper_bound]
    );

    quick_forward_order(container, lower_bound, lhs_pointer - 1);
    quick_forward_order(container, lhs_pointer + 1, upper_bound);
};

template<typename T, std::size_t S>
void quick_reverse_order(T(&container)[S], std::size_t lower_bound = std::size_t(0), std::size_t upper_bound = S - 1)
{
    if(lower_bound >= upper_bound)
    {
        return;
    }

    // Choosing the last element as the pivot
    const T& pivot_element = container[upper_bound];

    std::size_t rhs_pointer = upper_bound;
    std::size_t lhs_pointer = lower_bound;

    while (lhs_pointer < rhs_pointer)
    {
        while(container[lhs_pointer] >= pivot_element && lhs_pointer < rhs_pointer)
        {
            ++lhs_pointer;
        }

        while(container[rhs_pointer] <= pivot_element && rhs_pointer > lhs_pointer)
        {
            --rhs_pointer;
        }

        std::swap(
            container[lhs_pointer],
            container[rhs_pointer]
        );
    }

    std::swap(
        container[lhs_pointer],
        container[upper_bound]
    );

    quick_reverse_order(container, lower_bound, lhs_pointer - 1);
    quick_reverse_order(container, lhs_pointer + 1, upper_bound);
};

这是我尝试并测试的代码：

int main(void)
{
    int array[5] = {3, 1, 5, 7, 6};
    
    std::cout << "Before sorting:" << "\n\n";
    
    for(std::size_t index = 0; index < 5; ++index)
    {
        std::cout << array[index] << "\n";
    }
    
    std::cout << std::flush;
    
    
    quick_forward_order(array);
    
    
    std::cout << "After sorting:" << "\n\n";
    
    for(std::size_t index = 0; index < 5; ++index)
    {
        std::cout << array[index] << "\n";
    }
    
    std::cout << std::flush;
    
    return (0);
}

对于每种方法，我不断在这一行周围收到分段错误：

while(container[lhs_pointer] <= pivot_element && lhs_pointer < rhs_pointer)

不过，我无法弄清楚问题出在哪里。这是否与我正在使用一个并且它进入负值的事实有关？如果是这样，那么我该如何解决这个问题？std::size_t

C++ 分段错误快速排序

将来，可以使用错误检查、断言、异常、调试器和/或日志记录来查找这些类型的错误。例如，如果添加了对 lhs 和 rhs 的值为 <0 或 >= 初始数组大小的检查，则可以输出日志消息、引发异常、在测试失败时运行的代码中设置断点。

答：

2赞 LiuYuan 10/2/2023 #1

以下是完整的调试日志：

Process 12582 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x1d6fdfe67c)
    frame #0: 0x0000000100003148 test`void quick_forward_order<int, 5ul>(container=0x000000016fdfe7c0, lower_bound=0, upper_bound=12884901893) [5ul], unsigned long, unsigned long) at test.cpp:26:12
   23         ++lhs_pointer;
   24       }
   25
-> 26       while (container[rhs_pointer] >= pivot_element &&
   27              rhs_pointer > lhs_pointer) {
   28         --rhs_pointer;
   29       }
Target 0: (test) stopped.

您可以看到访问冲突，因为访问冲突太大，并且您的猜测是正确的。一旦某一类型的值减少，其值将被设置为可以在该大空间中表示的最大整数值。upper_boundsize_t01

如果我们继续调试：

(lldb) bt <============ print calling sequence, which is backtrace(bt)
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x1d6fdfe67c)
  * frame #0: 0x0000000100003148 test`void quick_forward_order<int, 5ul>(container=0x000000016fdfe7c0, lower_bound=0, upper_bound=12884901893) [5ul], unsigned long, unsigned long) at test.cpp:26:12
    frame #1: 0x00000001000031f0 test`void quick_forward_order<int, 5ul>(container=0x000000016fdfe7c0, lower_bound=0, upper_bound=1) [5ul], unsigned long, unsigned long) at test.cpp:36:3
    frame #2: 0x00000001000031f0 test`void quick_forward_order<int, 5ul>(container=0x000000016fdfe7c0, lower_bound=0, upper_bound=2) [5ul], unsigned long, unsigned long) at test.cpp:36:3
    frame #3: 0x00000001000031f0 test`void quick_forward_order<int, 5ul>(container=0x000000016fdfe7c0, lower_bound=0, upper_bound=4) [5ul], unsigned long, unsigned long) at test.cpp:36:3
    frame #4: 0x0000000100002f1c test`main at test.cpp:86:3
    frame #5: 0x000000018ed2d058 dyld`start + 2224

让我们检查第 3 帧，这是您第一次调用：quick_forward_order

(lldb) f 3 <======= frame 3
frame #3: 0x00000001000031f0 test`void quick_forward_order<int, 5ul>(container=0x000000016fdfe7c0, lower_bound=0, upper_bound=4) [5ul], unsigned long, unsigned long) at test.cpp:36:3
   33
   34     std::swap(container[lhs_pointer], container[upper_bound]);
   35
-> 36     quick_forward_order(container, lower_bound, lhs_pointer - 1);
   37     quick_forward_order(container, lhs_pointer + 1, upper_bound);
   38   };
   39
(lldb) p lhs_pointer <==== print lhs_pointer
(size_t) $0 = 3

然后是第 2 帧和第 1 帧：

(lldb) f 2 <======== frame 2
frame #2: 0x00000001000031f0 test`void quick_forward_order<int, 5ul>(container=0x000000016fdfe7c0, lower_bound=0, upper_bound=2) [5ul], unsigned long, unsigned long) at test.cpp:36:3
   33
   34     std::swap(container[lhs_pointer], container[upper_bound]);
   35
-> 36     quick_forward_order(container, lower_bound, lhs_pointer - 1);
   37     quick_forward_order(container, lhs_pointer + 1, upper_bound);
   38   };
   39
(lldb) p lhs_pointer <===== print lhs_pointer
(size_t) $1 = 2      <===== start decreasing because we pass lhs_pointer - 1
(lldb) f 1           <===== frame 1
frame #1: 0x00000001000031f0 test`void quick_forward_order<int, 5ul>(container=0x000000016fdfe7c0, lower_bound=0, upper_bound=1) [5ul], unsigned long, unsigned long) at test.cpp:36:3
   33
   34     std::swap(container[lhs_pointer], container[upper_bound]);
   35
-> 36     quick_forward_order(container, lower_bound, lhs_pointer - 1);
   37     quick_forward_order(container, lhs_pointer + 1, upper_bound);
   38   };
   39
(lldb) p lhs_pointer
(size_t) $2 = 0

老年退休金计划。你可以看到现在。一旦你把它作为....现在一切都清楚了。lhs_pointer0lhs_pointer - 1

至于解决方案，这非常简单：在界面中交换。是的，仅此而已：size_tint

template <typename T, std::size_t S>
void quick_forward_order(T (&container)[S], int lower_bound = 0,
                         int upper_bound = S - 1)

函数开始时的保护将开始起作用。

❯ g++ -std=c++11 test.cpp -o test
❯ ./test
Before sorting:

3
1
5
7
6
After sorting:

1
3
5
6
7

如果你真的想要一个实现，这也很简单：在调用函数之前，判断是否是，如果是，停止调用size_tquick_forward_orderlhs_pointer0quick_forward_order

谢谢。在再次调用递归函数之前进行检查，您的解决方案可以完美地工作。我更喜欢使用而不是的唯一原因是因为社区一直在推动我使用，因为它足够大，可以容纳大量元素。否则，我坚持使用类型没有问题。std::size_tintstd::size_tint

1赞 LiuYuan 10/3/2023

@Default 使用的另一个原因：请检查文档的值类型部分，这将对元编程非常有帮助。使用是一个非常好的习惯，坚持下去！std::size_tsize_t

0赞 Default 10/3/2023

会做的！谢谢你的动力！

上一个：快速排序的这个片段有什么问题？[关闭]

下一个：快速排序算法（js）中的 If/else

快速排序的分段错误

Segmentation fault with Quick sort

评论

评论