0

I'm implementing Quicksort algorithm, and I'm getting a "core dumped" error.

However, when I change the arguments for the quickSort() function to int instead of size_t, it works fine. What is the problem?

The code is as follows:

size_t partition(std::vector<int>& numbers, size_t start, size_t end)
{
    size_t pivot {end};

    size_t actual {start};

    for(size_t i{start}; i < end; i++){
        if(numbers.at(i) < numbers.at(pivot)){
            std::swap(numbers.at(i), numbers.at(actual));
            ++actual;
        }
    }
    std::swap(numbers.at(actual), numbers.at(pivot));
    return actual;

}

Here is the issue:

void quicksort(std::vector<int>& numbers, size_t start, size_t end)
{ 
    if(end > start){
        size_t pivot = partition(numbers, start, end);
        quicksort(numbers, start, pivot - 1);
        quicksort(numbers, pivot + 1, end );
    }
}

I know it should be size_t since I'm working with vector indices, but size_t doesn't work for this case. Why not?

user207421
  • 305,947
  • 44
  • 307
  • 483
Mohamed Soliman
  • 1
  • 1
  • Does this answer your question? [Difference between size\_t and unsigned int?](https://stackoverflow.com/questions/19732319/difference-between-size-t-and-unsigned-int) – hessam hedieh May 11 '21 at 09:46
  • 4
    what is `pivot-1` when `pivot` is unsigned `0` ? What input does it make fail? – 463035818_is_not_an_ai May 11 '21 at 09:46
  • In particular `i < pivot - 1` – Jarod42 May 11 '21 at 09:48
  • 2
    @hessam & @Abanoub not it does not answer the question. With `usigned int` the code would be as wrong as with `size_t` – 463035818_is_not_an_ai May 11 '21 at 09:48
  • signed vs unsigned issue. – Jarod42 May 11 '21 at 09:49
  • Coredump is usually caused by out of bound of an array, instead of int or size_t. Check your `start` and `end`, make sure they are legal. – Yves May 11 '21 at 09:49
  • 2
    I *strongly* urge you to reinvent your wheelhouse here and use *iterators* rather than a vector by reference and start-end indexes. It will actually make the algorithm *less* complicated, and much more akin to standard C++ practices. – WhozCraig May 11 '21 at 09:52
  • @Yves The code works properly with the same values if I change the arguments to int. – Mohamed Soliman May 11 '21 at 09:52
  • What is the size of the `numbers`? – Yves May 11 '21 at 09:53
  • std::vector numbers {6,3,0,7,89,9,45,4,67,99,9,8,5,87,996} it was 14 – Mohamed Soliman May 11 '21 at 09:55
  • @Jarod42 I thought if this, but the if condition will not execute if end ever reaches zero. The end "must" be larger than the start to call the function. – Mohamed Soliman May 11 '21 at 09:58
  • In the function `partition`, add this: `cout << start << ' ' << end << endl;` before the `for` loop. Run again, check if `start` and `end` are all legal. – Yves May 11 '21 at 09:58
  • In your case `{6,3,0,7,89,9,45,4,67,99,9,8,5,87,996}`, there are 15 integers, right? So `start` and `end` should be >=0 and <15. – Yves May 11 '21 at 09:59
  • 1
    @MohamedOsman: As already stated, if `pivot == 0`, `quicksort(numbers, start, pivot - 1);` would be `quicksort(numbers, 0, -1);`, but ... `std::size_t(0) < std::size_t(-1)`... – Jarod42 May 11 '21 at 10:06
  • @MohamedOsman yes, but the `if(end > start)` does not prevent pivot from being zero. Lets say you call `partition` with `{6,3}, 0, 1` as parameters, then `actual` will be set to 0. Because `numbers.at(i) < numbers.at(pivot)` (`6 < 3`) is false, `actual` will still be 0 when the function returns. – MathiasJ May 11 '21 at 10:44

0 Answers0