QuickSort, pass by reference, recursion

Question

i am trying to solve a kind of weird QuickSort. I partition the array and I create 2 other arrays: the left array and the right array (without the pivot) and I partition them and so on. My code is this:

#include <bits/stdc++.h>

using namespace std;

int partition(vector<int>& ar) {
     int pivot=ar[0];
     int store=0;
     for(int i=0;i<ar.size();i++)
     {
         if(ar[i]<pivot)
         {
             store++;
             int temp=ar[store];
             ar[store]=ar[i];
             ar[i]=temp;
         }
     }
     for(int i=0;i<store;i++){
         int temp=ar[i];
         ar[i]=ar[i+1];
         ar[i+1]=temp;
     }
     for(int i=ar.size()-2;i>store;i--){
         int temp=ar[i+1];
         ar[i+1]=ar[i];
         ar[i]=temp;
     } 
     return store; }

 void quickSort(vector <int>& arr) {
     if(arr.size()<=1)
     {
         return;
     }
     int a=partition(arr);
     vector <int> vec1(a);
     int b=arr.size()-a-1;
     vector <int> vec2(b);
     for(int i=0;i<a;i++)
     {
         vec1[i]=arr[i];
     }
     for(int i=a+1;i<arr.size();i++)
     {
         vec2[i]=arr[i];
     }
     if(vec1.size()<2 && vec2.size()<2)
     {
         for(int i=0;i<arr.size();i++)
         {
             cout<<arr[i]<<" ";
         }
         cout<<endl;
         return;
     }
     else{
         quickSort(vec1);
         quickSort(vec2);

     }
 }

 int main() {
     int n;
     cin >> n;

     vector <int> arr(n);
     for(int i = 0; i < (int)n; ++i) {
         cin >> arr[i];
     }
     quickSort(arr);
     for(int i =0; i <arr.size(); i++) 
     {
       cout<<arr[i]<<" ";
     }

     return 0; 
 }

The code is not finished at all, however, here, It should run whereas it does not. I have this error:

Abort Called

Error (stderr):

solution: malloc.c:2372: sysmalloc: Assertion (old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.`

I think it is because I am calling recursively the function quickSort which takes the reference of vector vec1 and vector vec2 and then I create in the function again vector vec1 and vec2...But i am not sure at all!!

Sorry again for such a long question but it is not easy to write it...

Thanks in advance for your answers!!!!

The right tool to solve such problems is your debugger. You should step through your code line-by-line *before* asking on Stack Overflow. For more help, please read [How to debug small programs (by Eric Lippert)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). At a minimum, you should \[edit] your question to include a [Minimal, Complete, and Verifiable](http://stackoverflow.com/help/mcve) example that reproduces your problem, along with the observations you made in the debugger. — πάντα ῥεῖ, Oct 15 '16 at 22:01
[`#include `](http://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) Who taught you that? — πάντα ῥεῖ, Oct 15 '16 at 22:06
Can you compile any code at all? If this is indeed a compiler message it seems the compiler can't allocate enough memory. — Dietmar Kühl, Oct 15 '16 at 22:13
@πάνταῥεῖ: How can the debugger help with a compiler error? — Benjamin Lindley, Oct 15 '16 at 22:18
Is it possible that is due because i am creating a vector inside the function (function passed by reference)and then i call the function recursively on this vector? — Bazouk55555, Oct 15 '16 at 22:18
because actually i can say that the error comes when i call the function recursively the first time on the line "vector vec2(b);" — Bazouk55555, Oct 15 '16 at 22:19
Then why does your question say *"It should compile whereas it does not."*? — Benjamin Lindley, Oct 15 '16 at 22:30

Barmak Shemirani · Accepted Answer · 2016-10-16T04:48:23.110

if (arr.size() <= 1)
    return;

int a = partition(arr);
vector<int> vec1(a);
for (int i = 0; i<a; i++)
    vec1[i] = arr[i];

int b = arr.size() - a - 1;
vector<int> vec2(b);
for (int i = a + 1; i<(int)arr.size(); i++)
    vec2[i] = arr[i];

Clearly vec2.size() is less than arr.size(). vec2 can easily go out of bound, and possibly vec1

For example if arr.size() is 10, and b is 2, then at one point you try to set vec2[3] = arr[3] but vec2 only has size 2.

To fix this, you want to set size of vec1 and vec2 to be the same as arr

vector<int> vec1(arr.size(), 0);
vector<int> vec2(arr.size(), 0);

This creates array of same size, and initializes the values to zero. Also make sure a and b are greater than zero. I don't see how the algorithm relates to qsort. See the example below for working code.

For convenience, you can declare some random array in main, example:

vector<int> arr{ 7,3,6,1,4,8,9,2 };

This way you don't have to spend 2 minutes entering data each time you want to test the algorithm. Also you can write a swap function to avoid repeating the same code, example

void myswap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

Or simply use std::swap. qsort example:

#include <iostream>
#include <vector>

using std::cout;

int qsort_partition(std::vector<int> &arr, const int left, const int right)
{
    const int mid = left + (right - left) / 2;
    const int pivot = arr[mid];

    std::swap(arr[mid], arr[left]);
    int i = left + 1;
    int j = right;
    while (i <= j) 
    {
        while (i <= j && arr[i] <= pivot) 
            i++;

        while (i <= j && arr[j] > pivot) 
            j--;

        if (i < j) 
            std::swap(arr[i], arr[j]);
    }
    std::swap(arr[i - 1], arr[left]);
    return i - 1;
}

void qsort(std::vector<int> &arr, const int left, const int right)
{
    if (left >= right) return;
    int partition = qsort_partition(arr, left, right);
    qsort(arr, left, partition - 1);
    qsort(arr, partition + 1, right);
}

void my_qsort(std::vector<int> &arr)
{
    qsort(arr, 0, arr.size() - 1);
}

int main() 
{
    std::vector<int> arr{ 7,3,6,1,4,8,9,2 };
    my_qsort(arr);
    return 0;
}

QuickSort, pass by reference, recursion

1 Answers1