Multi tool use

Clash Royale CLAN TAG

Std Sort make std::vector invalid

I found a bug in std::sort and in some implementations of QuickSort in particular, I do not know whether the problem is in the algorithm in general.

Essence:

When the elements are less than 16 all the norms, because std::sort uses an insertion sort.

When there are 17 or more elements, then quick sort is used with a restriction on the depth of recursion from the logarithm of the number of elements, but vector has time to deteriorate at the first __introsort_loop iteration.

There is a vector spoilage when many identical elements. Corruption happened by replacement of valid iterators with invalid iterators.

Other containers may break too, I did not check.

An example for simplicity with a vector of type "int", for more complex objects - crash at the time of sorting, because the invalid object is passed to the comparison function:

#include <iostream>
#include <vector>
#include <algorithm>

void quickSort(int arr, int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];

/* partition */

while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};

/* recursion */

if (left < j)
quickSort(arr, left, j);

if (i < right)
quickSort(arr, i, right);
}

int main()
{
for( int i = 0 ; i < 1 ; i++ )
{
//std::vector<int> v({5, 6, 1, 6, 2, 6, 3, 6, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 6});//reproducible with this
std::vector<int> v(19, 6);//reproducible with this also
std::sort(std::begin(v), std::end(v), [&v]( const int & left, const int & right )
{
// std::cout << " left=" << left << ", right=" << right << std::endl;
bool b = left <= right;
return b;
}
);
// quickSort(v.data(), 0, v.size());
for( const auto & result : v )
{
std::cout << "results: " << result << std::endl;
}
}

std::cout << "Hello World!n";
}


Can someone encounter this behavior quick sort?

2 Answers
2

I tried out your code, and it seems that the problem is with vectors created with the constructor vector(n,val) (The fill constructor). Vectors when manually inserted with 16,17,18 and 19 random elements show no problems.

you must save the pivot at beginning class like

void quickSort(int arr, int left, int right) {
int i = left, j = right; int pivot=x[left];
after that will work

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.