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!!!!

Answer 1

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;
}