Recursive quick-sort causing segmentation fault (not overflow)

Question

Please help me (this would be very handy for a school project due tommorow)

I haven been trying to implement a recursive quick-sort algorithm in C++, however, when i run it i get a runtime segmentation fault(windows):

#include <iostream>
#include <sstream>
#include <stdlib.h>

using namespace std;

void getRandomList(int, int*);
void outputList(int, int*);
void quicksort(int, int*);

int main()
{
    cout<<"Quick Sort example, By Jack Wilkie\n";
    while (true)
    {
        cout<<"Please enter list length\n";
        string pnput;
        cin>>pnput;
        cin.ignore(1);
        stringstream temp;
        temp << pnput;
        int length;
        temp >> length;
        if (length < 1 || length > 100000)
        {
            cout<<"INVALID INPUT! (0 < input < 100,000)\n";
        }
        else
        {
            cout<<"Creating random list of "<<length<<" items\n";
            int *list = new int[length];
            getRandomList(length, list);
            outputList(length, list);
            double start = clock();
            quicksort(length, list);
            double stop = clock();
            double time = stop-start;
            cout<<time<<"ms";
            cin.get();
            delete[] list;
            break;
        }
    }
}

void quicksort(int len, int* list)
{
    if (len < 1)
    {
        return;
    }
    else
    {
        int low[10];
        int mid[10];
        lmid[0] = list[0];
        int high[10];
        int lens[3] = {0,1,0};
        for(int i = 1; i < len; i++)
        {
            if(list[i] < list[0])
            {
                low[lens[0]] = list[i];
                lens[0]++;
            }
            else if (list[i] > list[0])
            {

                high[lens[2]] = list[i];
                lens[2]++;
            }
            else
            {
                mid[lens[1]] = list[i];  
                lens[1]++;
            }
        }
        quicksort(lens[0], low);
        quicksort(lens[2], high);
        for(int i = 0; i < len; i++)
        {
                if (i < lens[0])
                {
                      list[i] = low[i];
                }
                else if (i < lens[0]+lens[1])
                {
                       list[i] = mid[i-lens[0]];
                }
                else
                {
                    list[i] = high[i-lens[0]-lens[1]];
                }
        }
    }
    return;

}

My debug program (dev c++, almost out of internet and cant get anything big) say that the error is on line

    lmid[0] = list[0];

however i cannot find any issues with it, it has the error as soon as it calls the quicksort function, i beleive the issue has something to do with passing an array, and i am fairly sure that the function isn't recursing and bloating the stack

in case you need it for debuging, here are the other functions i used

void getRandomList(int length, int* output)
{
    for(int i = 0; i < length; i++)
    {
        output[i] = rand() % 100;
    }
    return;
}

void outputList(int length, int* input)
{
    for(int i = 0; i < length; i++)
    {
        cout<<input[i]<<" ";
    }
    cout<<"\n";
    return;
}

Answer 1

Your exit base case is incorrect.

This:

if (len < 1)

Should be this:

if (len <= 1)

That is very important for stopping the infinite recursion of your program. Your fault happens because you blow through your automatic variable storage space (aka. the stack), consuming more and more of it with each iteration until finally ker-boom.

---

General In-Place Quicksort

As an algorithm implementation note, you're making this much, much harder than it needs to be. Quicksort is about partitioning, and done correctly, you should need no temporary storage outside of the temp-variable used for swapping elements. Use the library to your advantage. A swap mechanism is provided for you, namely std::swap. This significantly cleans up the code.

void quicksort(int arr[], size_t len)
{
    if (len <= 1)
        return;

    size_t pvt = 0, i;
    for (i=0; i<len; ++i)
    {
        if (arr[i] < arr[len-1])
            std::swap(arr[i], arr[pvt++]);
    }
    std::swap(arr[pvt], arr[len-1]);

    // important: do NOT include the pivot slot
    quicksort(arr, pvt++);
    quicksort(arr+pvt, len-pvt);
}

This is different than your algorithm in some fundamental ways, and not just because it works:

• It takes the array as the first parameter, the length second.
• It uses arr[len-1] to keep the pivot value, not arr[0]
• It requires no temporary arrays whatsoever.

Apart from the choice pivot values (it should be random-based, not always in a specific slot location), this is the traditional sweep-parition method used for in-place quicksort.

---

Iterator-Based Template

Though overkill for your needs, the above algorithm can be extended to a general iterator-based template that is easily implemented using the C++ standard library.

#include <type_traits>
#include <iterator>
#include <cstdlib>

// assumes T::operator <(const T&) exists for the iterated type.
template<
   typename Iterator,
   typename Compare=std::less<typename std::iterator_traits<Iterator>::value_type>
>
void quicksort(Iterator first, Iterator last, Compare&& cmp = Compare())
{
    // early exit on trivial list (zero or one element)
    typename std::iterator_traits<Iterator>::difference_type len = std::distance(first, last);
    if (len <= 1)
        return;

    // establish pivot, move it to end of sequence
    Iterator tail = std::prev(last,1);
    Iterator pvt = std::next(first, (std::rand() % len));
    std::iter_swap(pvt, tail);

    // run through scan
    pvt = first;
    for (Iterator head = first; head != tail; ++head)
    {
        if (cmp(*head,*tail))
            std::iter_swap(head, pvt++);
    }
    std::iter_swap(pvt, tail);

    // run through sublists. note: pvt is NOT included.
    quicksort(first, pvt, cmp);
    quicksort(++pvt, last, cmp);
}

This allows you to invoke this on any sequence container supporting bi-directional iterators. For example:

std::vector<int> data;

// populate data with values.

quicksort(data.begin(), data.end());

Likewise, it can be used on fixed arrays:

int arr[N];

// populate arr with values

quicksort(std::begin(arr), std::end(arr));

// or
quicksort(arr, arr + sizeof(arr)/sizeof(*arr));

Finally, the fixed array example can be made even more straight-forward using a simple fixed-array-template wrapper around our quicksort implementation:

template<typename T, std::size_t N>
void quicksort(T (&arr)[N])
{
    quicksort(std::begin(arr), std::end(arr));
}

which then allows us to simply do this:

int arr[N];

// populate arr with values

quicksort(arr);

Answer 2

Not an answer to your question.

A few weeks ago I was practicing with C++ containers and algorithms, and decided to implement quicksort. I am attaching my code not because it is particularly good or efficient, but I like the feel it gave me to using C++ algorithms to solve specific problems.

Maybe it can help you both understand the algorithm and its "functional" implementation using C++.

#include<iostream>
#include<iterator>
#include<functional>
#include<algorithm>
#include<vector>
#include<array>
#include<list>
#include<string>

namespace detail {
template<typename T, typename Iterator>
void show(Iterator first, Iterator last, Iterator pidx, int depth) {
  if(std::distance(first, last) <= 0) {
    return;
  }
  std::cout<<"tail depth: "<<depth<<std::string(depth, '\t')<<"[ ";
  std::copy(first, pidx, std::ostream_iterator<T>(std::cout, " "));
  std::cout<<"]  + "<<(*pidx) <<" + [ ";
  std::copy(std::next(pidx), last, std::ostream_iterator<T>(std::cout, " "));
  std::cout<<"]"<<std::endl;
}

template<typename T, typename Iterator>
void quicksort(Iterator first, Iterator last, int depth=0) {
  if(std::distance(first, last) > 0) {
    auto pred = std::bind(std::less<T>(), std::placeholders::_1, *first);    

    std::iter_swap(first, std::prev(last));
    auto pidx = std::partition(first, last, pred);    
    std::iter_swap(pidx, std::prev(last));

    depth++;    
    show<T>(first, last, pidx, depth);

    detail::quicksort<T>(first, pidx, depth);
    detail::quicksort<T>(std::next(pidx), last, depth);
  }
}
}

template<typename T>
void show(T& data) {
  std::cout<<"[ ";
  std::copy(data.begin(), data.end(), std::ostream_iterator<typename T::value_type>(std::cout, " "));
  std::cout<<"]"<<std::endl;
}

template<typename Container>
void quicksort(Container& data) {
  using T = typename Container::value_type;
  std::cout<<"Before sort: "; show(data);
  detail::quicksort<T>(std::begin(data), std::end(data));
  std::cout<<"After sort: "; show(data);
}

int main(int argc, char* argv[]) {

  std::cout<<"working with vector<int>"<<std::endl;
  std::vector<int> vdata = {5, 10, 0, 2, 8, 3, 7, 4, 6};
  quicksort(vdata);

  std::cout<<"working with array<double>"<<std::endl;  
  std::array<double, 9> adata = {5, 10, 0, 2, 8, 3, 7, 4, 6};
  quicksort(adata);

  std::cout<<"working with list<float>"<<std::endl;  
  std::list<float> cdata =  {5, 10, 0, 2, 8, 3, 7, 4, 6};
  quicksort(cdata);
  std::cout<<"worst case performance: sort a sorted container"<<std::endl;  
  quicksort(cdata);

  size_t N = argc == 2 ? std::stoi(argv[1]) : 100;
  std::cout<<"test on vector<int> with elements in [0, ..., "<<N-1<<"] shuffled randomly"<<std::endl;
  std::vector<int> ldata(N);
  std::iota(ldata.begin(), ldata.end(), 0);
  std::random_shuffle(ldata.begin(), ldata.end());
  quicksort(ldata);
  return 0;
}

I compiled on OS X 10.7.4 using GCC 4.8.1. Sample run:

$ /usr/local/bin/g++ quicksort-functional.cpp -std=c++11 -Wall -Wextra
$ ./a.out 
working with vector<int>
Before sort: [ 5 10 0 2 8 3 7 4 6 ]
tail depth: 1   [ 4 3 0 2 ]  + 5 + [ 10 7 6 8 ]
tail depth: 2       [ 2 3 0 ]  + 4 + [ ]
tail depth: 3           [ 0 ]  + 2 + [ 3 ]
tail depth: 4               [ ]  + 0 + [ ]
tail depth: 4               [ ]  + 3 + [ ]
tail depth: 2       [ 8 7 6 ]  + 10 + [ ]
tail depth: 3           [ 6 7 ]  + 8 + [ ]
tail depth: 4               [ ]  + 6 + [ 7 ]
tail depth: 5                   [ ]  + 7 + [ ]
After sort: [ 0 2 3 4 5 6 7 8 10 ]
working with array<double>
Before sort: [ 5 10 0 2 8 3 7 4 6 ]
tail depth: 1   [ 4 3 0 2 ]  + 5 + [ 10 7 6 8 ]
tail depth: 2       [ 2 3 0 ]  + 4 + [ ]
tail depth: 3           [ 0 ]  + 2 + [ 3 ]
tail depth: 4               [ ]  + 0 + [ ]
tail depth: 4               [ ]  + 3 + [ ]
tail depth: 2       [ 8 7 6 ]  + 10 + [ ]
tail depth: 3           [ 6 7 ]  + 8 + [ ]
tail depth: 4               [ ]  + 6 + [ 7 ]
tail depth: 5                   [ ]  + 7 + [ ]
After sort: [ 0 2 3 4 5 6 7 8 10 ]
working with list<float>
Before sort: [ 5 10 0 2 8 3 7 4 6 ]
tail depth: 1   [ 4 3 0 2 ]  + 5 + [ 10 7 6 8 ]
tail depth: 2       [ 2 3 0 ]  + 4 + [ ]
tail depth: 3           [ 0 ]  + 2 + [ 3 ]
tail depth: 4               [ ]  + 0 + [ ]
tail depth: 4               [ ]  + 3 + [ ]
tail depth: 2       [ 8 7 6 ]  + 10 + [ ]
tail depth: 3           [ 6 7 ]  + 8 + [ ]
tail depth: 4               [ ]  + 6 + [ 7 ]
tail depth: 5                   [ ]  + 7 + [ ]
After sort: [ 0 2 3 4 5 6 7 8 10 ]
worst case performance: sort a sorted container
Before sort: [ 0 2 3 4 5 6 7 8 10 ]
tail depth: 1   [ ]  + 0 + [ 2 3 4 5 6 7 8 10 ]
tail depth: 2       [ ]  + 2 + [ 3 4 5 6 7 8 10 ]
tail depth: 3           [ ]  + 3 + [ 4 5 6 7 8 10 ]
tail depth: 4               [ ]  + 4 + [ 5 6 7 8 10 ]
tail depth: 5                   [ ]  + 5 + [ 6 7 8 10 ]
tail depth: 6                       [ ]  + 6 + [ 7 8 10 ]
tail depth: 7                           [ ]  + 7 + [ 8 10 ]
tail depth: 8                               [ ]  + 8 + [ 10 ]
tail depth: 9                                   [ ]  + 10 + [ ]
After sort: [ 0 2 3 4 5 6 7 8 10 ]
test on vector<int> with elements in [0, ..., 99] shuffled randomly
Before sort: [ 95 37 56 15 50 77 61 66 8 43 90 7 25 74 1 26 38 87 13 64 57 84 6 16 17 67 35 42 55 9 59 81 2 68 58 29 76 73 99 96 33 11 34 4 86 46 39 52 97 82 10 41 53 28 49 5 80 12 71 14 91 88 24 93 45 79 62 31 19 60 22 69 94 63 51 32 44 75 98 78 30 89 47 23 83 48 54 21 70 36 20 27 0 3 72 40 85 18 65 92 ]
tail depth: 1   [ 92 37 56 15 50 77 61 66 8 43 90 7 25 74 1 26 38 87 13 64 57 84 6 16 17 67 35 42 55 9 59 81 2 68 58 29 76 73 65 18 33 11 34 4 86 46 39 52 85 82 10 41 53 28 49 5 80 12 71 14 91 88 24 93 45 79 62 31 19 60 22 69 94 63 51 32 44 75 40 78 30 89 47 23 83 48 54 21 70 36 20 27 0 3 72 ]  + 95 + [ 97 96 99 98 ]
tail depth: 2       [ 72 37 56 15 50 77 61 66 8 43 90 7 25 74 1 26 38 87 13 64 57 84 6 16 17 67 35 42 55 9 59 81 2 68 58 29 76 73 65 18 33 11 34 4 86 46 39 52 85 82 10 41 53 28 49 5 80 12 71 14 91 88 24 3 45 79 62 31 19 60 22 69 0 63 51 32 44 75 40 78 30 89 47 23 83 48 54 21 70 36 20 27 ]  + 92 + [ 93 94 ]
tail depth: 3           [ 27 37 56 15 50 20 61 66 8 43 36 7 25 70 1 26 38 21 13 64 57 54 6 16 17 67 35 42 55 9 59 48 2 68 58 29 23 47 65 18 33 11 34 4 30 46 39 52 40 44 10 41 53 28 49 5 32 12 71 14 51 63 24 3 45 0 62 31 19 60 22 69 ]  + 72 + [ 88 91 80 82 75 85 78 86 89 73 76 83 81 84 87 74 90 77 79 ]
tail depth: 4               [ 22 19 0 15 3 20 24 14 8 12 5 7 25 10 1 26 4 21 13 11 18 23 6 16 17 2 9 ]  + 27 + [ 55 35 59 48 67 68 58 29 54 47 65 57 33 64 34 38 30 46 39 52 40 44 70 41 53 28 49 36 32 43 71 66 51 63 61 50 45 56 62 31 37 60 69 42 ]
tail depth: 5                   [ 9 19 0 15 3 20 2 14 8 12 5 7 17 10 1 16 4 21 13 11 18 6 ]  + 22 + [ 26 25 24 23 ]
tail depth: 6                       [ 6 4 0 1 3 7 2 5 8 ]  + 9 + [ 14 20 17 10 15 16 19 21 13 11 18 12 ]
tail depth: 7                           [ 5 4 0 1 3 2 ]  + 6 + [ 8 7 ]
tail depth: 8                               [ 2 4 0 1 3 ]  + 5 + [ ]
tail depth: 9                                   [ 1 0 ]  + 2 + [ 3 4 ]
tail depth: 10                                      [ 0 ]  + 1 + [ ]
tail depth: 11                                          [ ]  + 0 + [ ]
tail depth: 10                                      [ ]  + 3 + [ 4 ]
tail depth: 11                                          [ ]  + 4 + [ ]
tail depth: 8                               [ 7 ]  + 8 + [ ]
tail depth: 9                                   [ ]  + 7 + [ ]
tail depth: 7                           [ 12 11 13 10 ]  + 14 + [ 16 19 21 17 20 18 15 ]
tail depth: 8                               [ 10 11 ]  + 12 + [ 13 ]
tail depth: 9                                   [ ]  + 10 + [ 11 ]
tail depth: 10                                      [ ]  + 11 + [ ]
tail depth: 9                                   [ ]  + 13 + [ ]
tail depth: 8                               [ 15 ]  + 16 + [ 21 17 20 18 19 ]
tail depth: 9                                   [ ]  + 15 + [ ]
tail depth: 9                                   [ 19 17 20 18 ]  + 21 + [ ]
tail depth: 10                                      [ 18 17 ]  + 19 + [ 20 ]
tail depth: 11                                          [ 17 ]  + 18 + [ ]
tail depth: 12                                              [ ]  + 17 + [ ]
tail depth: 11                                          [ ]  + 20 + [ ]
tail depth: 6                       [ 23 25 24 ]  + 26 + [ ]
tail depth: 7                           [ ]  + 23 + [ 25 24 ]
tail depth: 8                               [ 24 ]  + 25 + [ ]
tail depth: 9                                   [ ]  + 24 + [ ]
tail depth: 5                   [ 42 35 37 48 31 45 50 29 54 47 51 43 33 32 34 38 30 46 39 52 40 44 36 41 53 28 49 ]  + 55 + [ 64 57 71 66 65 63 61 58 68 56 62 67 59 60 69 70 ]
tail depth: 6                       [ 28 35 37 41 31 36 40 29 39 30 38 34 33 32 ]  + 42 + [ 51 47 46 54 52 50 44 45 48 53 49 43 ]
tail depth: 7                           [ ]  + 28 + [ 35 37 41 31 36 40 29 39 30 38 34 33 32 ]
tail depth: 8                               [ 32 33 34 31 30 29 ]  + 35 + [ 39 36 38 41 37 40 ]
tail depth: 9                                   [ 29 30 31 ]  + 32 + [ 33 34 ]
tail depth: 10                                      [ ]  + 29 + [ 30 31 ]
tail depth: 11                                          [ ]  + 30 + [ 31 ]
tail depth: 12                                              [ ]  + 31 + [ ]
tail depth: 10                                      [ ]  + 33 + [ 34 ]
tail depth: 11                                          [ ]  + 34 + [ ]
tail depth: 9                                   [ 37 36 38 ]  + 39 + [ 40 41 ]
tail depth: 10                                      [ 36 ]  + 37 + [ 38 ]
tail depth: 11                                          [ ]  + 36 + [ ]
tail depth: 11                                          [ ]  + 38 + [ ]
tail depth: 10                                      [ ]  + 40 + [ 41 ]
tail depth: 11                                          [ ]  + 41 + [ ]
tail depth: 7                           [ 43 47 46 49 48 50 44 45 ]  + 51 + [ 53 54 52 ]
tail depth: 8                               [ ]  + 43 + [ 47 46 49 48 50 44 45 ]
tail depth: 9                                   [ 45 46 44 ]  + 47 + [ 50 49 48 ]
tail depth: 10                                      [ 44 ]  + 45 + [ 46 ]
tail depth: 11                                          [ ]  + 44 + [ ]
tail depth: 11                                          [ ]  + 46 + [ ]
tail depth: 10                                      [ 48 49 ]  + 50 + [ ]
tail depth: 11                                          [ ]  + 48 + [ 49 ]
tail depth: 12                                              [ ]  + 49 + [ ]
tail depth: 8                               [ 52 ]  + 53 + [ 54 ]
tail depth: 9                                   [ ]  + 52 + [ ]
tail depth: 9                                   [ ]  + 54 + [ ]
tail depth: 6                       [ 60 57 59 62 56 63 61 58 ]  + 64 + [ 65 66 67 71 70 69 68 ]
tail depth: 7                           [ 58 57 59 56 ]  + 60 + [ 63 61 62 ]
tail depth: 8                               [ 56 57 ]  + 58 + [ 59 ]
tail depth: 9                                   [ ]  + 56 + [ 57 ]
tail depth: 10                                      [ ]  + 57 + [ ]
tail depth: 9                                   [ ]  + 59 + [ ]
tail depth: 8                               [ 62 61 ]  + 63 + [ ]
tail depth: 9                                   [ 61 ]  + 62 + [ ]
tail depth: 10                                      [ ]  + 61 + [ ]
tail depth: 7                           [ ]  + 65 + [ 66 67 71 70 69 68 ]
tail depth: 8                               [ ]  + 66 + [ 67 71 70 69 68 ]
tail depth: 9                                   [ ]  + 67 + [ 71 70 69 68 ]
tail depth: 10                                      [ 68 70 69 ]  + 71 + [ ]
tail depth: 11                                          [ ]  + 68 + [ 70 69 ]
tail depth: 12                                              [ 69 ]  + 70 + [ ]
tail depth: 13                                                  [ ]  + 69 + [ ]
tail depth: 4               [ 79 77 80 82 75 85 78 86 74 73 76 83 81 84 87 ]  + 88 + [ 90 91 89 ]
tail depth: 5                   [ 76 77 73 74 75 78 ]  + 79 + [ 86 82 80 87 83 81 84 85 ]
tail depth: 6                       [ 75 74 73 ]  + 76 + [ 78 77 ]
tail depth: 7                           [ 73 74 ]  + 75 + [ ]
tail depth: 8                               [ ]  + 73 + [ 74 ]
tail depth: 9                                   [ ]  + 74 + [ ]
tail depth: 7                           [ 77 ]  + 78 + [ ]
tail depth: 8                               [ ]  + 77 + [ ]
tail depth: 6                       [ 85 82 80 84 83 81 ]  + 86 + [ 87 ]
tail depth: 7                           [ 81 82 80 84 83 ]  + 85 + [ ]
tail depth: 8                               [ 80 ]  + 81 + [ 83 84 82 ]
tail depth: 9                                   [ ]  + 80 + [ ]
tail depth: 9                                   [ 82 ]  + 83 + [ 84 ]
tail depth: 10                                      [ ]  + 82 + [ ]
tail depth: 10                                      [ ]  + 84 + [ ]
tail depth: 7                           [ ]  + 87 + [ ]
tail depth: 5                   [ 89 ]  + 90 + [ 91 ]
tail depth: 6                       [ ]  + 89 + [ ]
tail depth: 6                       [ ]  + 91 + [ ]
tail depth: 3           [ ]  + 93 + [ 94 ]
tail depth: 4               [ ]  + 94 + [ ]
tail depth: 2       [ 96 ]  + 97 + [ 99 98 ]
tail depth: 3           [ ]  + 96 + [ ]
tail depth: 3           [ 98 ]  + 99 + [ ]
tail depth: 4               [ ]  + 98 + [ ]
After sort: [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ]

Answer 3

I dont see anywhere declaration or initialization of lmid variable. That would be problem probably.