В книге Седжвика. «Фундаментальные алгоритмы на С++» предлагается такая сортировка:
template <class Item>
void fixDown(Item *a, int k, int N)
{
while (2 * k <= N)
{
int j = 2 * k;
if ((j < N) && (a[j] < a[j + 1]))
j++;
if (a[k] > a[j])
break;
std::swap(a[k], a[j]);
k = j;
}
}
template <class Item>
void heapsort(Item *a, int l, int r){
int k, N=r-1+1;
Item *pq = a+1-1;
for(k=N/2;k>=1;k--)
fixDown(pq, k, N);
while (N>1)
{
std::swap(pq[1], pq[N]);
fixDown(pq, 1, --N);
}
}
И всё бы хорошо, сортирует полюбому быстро за O(N lgN), памяти дополнительной не требует, но есть неприятный нюанс: Если сгенерить такой массив, такой функцией.
int len=2300000;
auto array=generantion_array(0, 23000000,len);
int *generantion_array(int min, int max, int len)
{
std::default_random_engine generator;
std::uniform_int_distribution<int> distribution(min, max);
int *array = new int[len];
for (int i = 0; i < len; i++)
{
array[i] = distribution(generator);
}
return array;
}
То получается пара элементов не отсортирована:
180 10
Почему так происходит?
