I need to implement a quick sort for my university assignment. The following is the implementation for quick sort that I wrote in 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);
};
This is the code that I tried and tested this with:
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);
}
I keep getting a segmentation fault around this line for each of the methods:
while(container[lhs_pointer] <= pivot_element && lhs_pointer < rhs_pointer)
I can't figure out what the problem is though. Does it have to do with the fact that I am using an std::size_t and it goes into the negatvie? If so, then how can I fix this please?
Here is the full debug log:
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.
You can see access violation because upper_bound is too big, and your guess is correct. Once a type of size_t of value 0 decrease by 1, its value will be set to the largest integer value that can be represented in that large space.
And if we continue debug:
(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
Let's check frame 3, which is the first time you call 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
And then frame 2 and 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
Ops. You can see lhs_pointer is 0 now. Once you pass it as lhs_pointer - 1.... Now everything is clear.
And as for solution, that's really simple: swap size_t with int in your interface. Yes, that's all:
template <typename T, std::size_t S>
void quick_forward_order(T (&container)[S], int lower_bound = 0,
int upper_bound = S - 1)
And the protection at the beginning of your function will start to work.
❯ g++ -std=c++11 test.cpp -o test
❯ ./test
Before sorting:
3
1
5
7
6
After sorting:
1
3
5
6
7
If you really want a size_t implementation, that's easy ,too: Before you call quick_forward_order function, judge if lhs_pointer is 0, if it is, stop calling quick_forward_order