LINUX.ORG.RU

О сортировке пирамидой

 , ,


0

2

В книге Седжвика. «Фундаментальные алгоритмы на С++» предлагается такая сортировка:

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

Почему так происходит?

★★★★★

Ответ на: комментарий от ox55ff

Потому что ошибка в алгоритме, очевидно же.

Спасибо, кэп. Меня интересует где, и как ещё исправить.

Ygor ★★★★★
() автор топика

Читая по диагонали такой вопрос возник - мб проблема на чётном/нечётном количестве элементов?

Bfgeshka ★★★★★
()
Ответ на: комментарий от Ygor

однобуквенные имена вида k, r, N, pq, a, отсутствие скобок вокруг тела цикла for, сырые указатели

Это какая-то лаба сишника-олимпиадника. Мне это физически больно смотреть.

ox55ff ★★★★★
()
Ответ на: комментарий от ox55ff

В 1975 году получил степень Ph.D. от Стэнфордского университета, защитив диссертацию про алгоритм быстрой сортировки под руководством Дональда Кнута.[3]

он учился у непревзойденного маэстро, который

Преподавал там же математику

Дело раскрыто: Седжевика научил так математик Кнут


Но это странно почему они все (математики) такую дрисню пишут. Я думал, что это советская школа такая

rtxtxtrx
()
Ответ на: комментарий от AlexVR

Первое, что бросается в глаза:

   int k, N=r-1+1;
   Item *pq = a+1-1;

Да там весь код такой - кончелыжный:

void heapsort(Item *a, int l, int r)

int l - вообще никак не используется.

Ygor ★★★★★
() автор топика
Ответ на: комментарий от rtxtxtrx

Кнут не писал на C++. В его книге «Искусство программировпния» примеры были на псевдокоде. Я их адаптирован на разные языки (не на C++) и успешно использовал. Сейчас для разных языков функции сортировки скорее всего вполне эффективны. Так что программировать её можно для изучения алгоритмов. В данном примере ошибка не в алгоритме, а в программе. Лень искать.

Partisan ★★★★
()
Ответ на: комментарий от Bfgeshka

Читая по диагонали такой вопрос возник - мб проблема на чётном/нечётном количестве элементов?

Нет. Чет, нечет ведёт себя одинаково.

Ygor ★★★★★
() автор топика
Ответ на: комментарий от Reset

У тебя вместо l где-то используется 1

Спасибо, вы оказались правы, это:

    int k, N=r-l+1;
    Item *pq = a+l-1;

помогло.

Ygor ★★★★★
() автор топика
Ответ на: комментарий от Reset

везде, где 1+/-1, первая 1 - это латинская строчная L

anonymous
()
Ответ на: комментарий от Ygor

Компилятор должен был выдать предупреждение про неиспользуемый аргумент функции.

annulen ★★★★★
()
Ответ на: комментарий от Partisan

Он учил Седживика писать дрисню с переменными типа l, которые ОП не смог от 1 отличить из-за используемого шрифта в книге. Явно, что нормальный погроммист вменяемые имена был дал, но не математик.

rtxtxtrx
()
Последнее исправление: rtxtxtrx (всего исправлений: 1)
Ответ на: комментарий от ox55ff

Потому что это худший вариант копипаст программирования, когда копирование - это игра в клавогонки.

anonymous
()
Ответ на: комментарий от rtxtxtrx

Есть такое наблюдение: умные люди обычно склонны считать окружающих более умными, чем те есть на самом деле.

Ну то есть человек предполагает, что программист, встретив конструкцию var+1-1 и неиспользуемый параметр по имени l немножечко задумается.

Он не предполагает увидеть в профессии обезьяну и не пишет для обезьян.

thesis ★★★★★
()
Ответ на: комментарий от Reset

LeftItemIndexInSortingArray

RightItemIndexInSortingArray

anonymous
()
Ответ на: комментарий от rtxtxtrx

напыщенные идиоты

Мне со школы нравилась блестящая формулировка, особо любимая двоечниками: «ничего не понимаю, дебильный учебник какой-то».

thesis ★★★★★
()

Оффтоп.

    std::uniform_int_distribution<int> distribution(min, max);
    int *array = new int[len];

Мультипарадигменное программирование во всей красе

anonymous
()
Ответ на: комментарий от ox55ff

Единственная стилистическая проблема которая там это направильные отступы и открывающая фигурная скобка на отдельной строке. Имена переменных - норм, указатели - норм, скобки вокруг тела не нужны если оно из одной строчки, но надо эту строчку прицеплять к строчке с for тогда а не на отдельной писать.

firkax ★★★★★
()
Ответ на: комментарий от goingUp

Вангую косяк с переводом/версткой

Вангую, что ТС валенок. Как можно было скопипастить +1-1 даже если и вправду так в книжке написано? Это надо вообще не отдуплять что ты делаешь и копировать по принципу «там такая же закорючка».

no-such-file ★★★★★
()
Последнее исправление: no-such-file (всего исправлений: 1)
Ответ на: комментарий от rtxtxtrx

Идиот-клоунатор rtxtxtrx опять обидется и наспамил мне клоунов в сообщения из поиска по последним.

firkax ★★★★★
()
Ответ на: комментарий от Bfgeshka

Я для этого шрифт iosevka собираю, чтобы 1(единица) и l(латинская), 3(три) и З(русская) и тп имели разные глифы.

anonymous
()
Ответ на: комментарий от thesis

дебильный учебник какой-то

В случае с книгой Седжвика – это чистая правда. Зачем её брать при существовании альтернатив – для меня загадка.

anonymous
()
Ответ на: комментарий от thesis

Кстати, если в школе учился позднее 60х, то «двоечники» тоже были недалеки от истины. Послереформенные учебники – параша та ещё.

anonymous
()
Ответ на: комментарий от anonymous

дебильный учебник какой-то

В случае с книгой Седжвика – это чистая правда. Зачем её брать при существовании альтернатив – для меня загадка.

Альтернативы в студию. На С++.

Ygor ★★★★★
() автор топика
Ответ на: комментарий от anonymous

З(русская)

Так вот она какая, русская тройка.

anonymous
()
Ответ на: комментарий от Ygor

Все нормальные с псевдокодом, потому что дрючево с бойлерплейтом отвлекает от сути. Если в названии – конкретный ЯП (а книга не про этот ЯП), значит это порожняк.

anonymous
()
Ответ на: комментарий от firkax

Имена переменных - норм

Чувак, ты лучший. Перед тобой пример ошибки, возникшей только благодаря всратым именам переменных, а ты на голубом глазу утверждаешь, что норм. Это вообще как?

Не уже говоря, что такие переменные это неуважение коллег, которые буду читать твой код. Поэтому такое запрещено в code style любой уважающей себе конторы и не пройдёт дальше ревью.

Фигурные скобки в ту же степь. Так запрещено писать и нещадно фиксится каким-нибудь clang-format в git hook.

У меня всё больше уверенности, что ты не работал профессионально, а только лабал программки в стол. Иначе невозможно не усвоить базовые принципы стиля кодирования.

ox55ff ★★★★★
()
Ответ на: комментарий от ox55ff

Нормальные имена. Левую и правую границу обозначать l и r это общепринято и сразу понятно о чем речь. Всякие LeftItemIndexInSortingArray как раз вынесут мозг и придется вникать.

Reset ★★★★★
()
Ответ на: комментарий от Ygor

Даже если не на C++. Суть книги Седжвика не в C++, а в алгоритмах и реализации их на реальном существующем языке программирования, а не на дебильном псевдокоде.

Reset ★★★★★
()
Ответ на: комментарий от Reset

Всякие LeftItemIndexInSortingArray как раз вынесут мозг и придется вникать.

С чего ты взял, что альтернативой l является LeftItemIndexInSortingArray, а не leftIdx, например? Приписал мне абсурдный аргумент, а потом героически его победил. Очень удобно.

ox55ff ★★★★★
()
Ответ на: комментарий от thesis

Он не предполагает увидеть в профессии обезьяну

Да лааадно.

Nervous ★★★★★
()
Ответ на: комментарий от Reset

Левую и правую границу обозначать l и r

Сначала надо понять, что речь идёт о границах, а не lions & rabbits.

Nervous ★★★★★
()

Оффтоп для холивара.

Item *pq = a+l-1;

Здесь происходит конвертирование из массива ‘a’ с сишным индексированием начиная с 0(нуля) в массив ‘pq’ с индексированием с 1(единицы).

anonymous
()
Ответ на: комментарий от ox55ff

Перед тобой пример ошибки, возникшей только благодаря

Ошибка возникла исключительно благодаря тому что кто-то программирует методом копипаста. Как уже выше отметили, нормальный человек не станет бездумно так переписывать.

Не уже говоря, что такие переменные это неуважение коллег, которые буду читать твой код

Неуважение это когда имена переменных длиннее 10 букв без острой на то нужды. Они засоряют полезную площадь экрана и уменьшают размер куска алгоритма который можно видеть одновременно не крутя глазами. Мусорная разбивка тривиальных конструкций на строки - туда же.

Фигурные скобки в ту же степь. Так запрещено писать и нещадно фиксится

Если ты о таком:

for(a;b;c)
  something();
то я согласен это плохо. А вот такое - норм
for(a;b;c) something();
А вот такое
for(a;b;c) {
  something();
}
норм в плане наглядности, но плохо в плане мусора на экране.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от ox55ff

Перед тобой пример ошибки, возникшей только благодаря всратым именам переменных

Вообще нет. ТС мог также ничтоже сумняшеся забубенить 1eft вместо left. Что теперь букву l вообще нельзя писать? Ты не там ищешь проблему.

no-such-file ★★★★★
()
Ответ на: комментарий от rtxtxtrx

Он учил Седживика писать дрисню с переменными типа l,

Ты в этот момент держал свечку и снимал ролик на андроидозатычку? :-) Смешно смотреть на карапузикаФФ которые … «Эх Моська!» (С) :-D

которые ОП не смог от 1 отличить из-за используемого шрифта в книге.

В книге и близко нет С++ вовна! :) Там вообще псевдокод! Книги доступны - скачай посмотри, тебе будет очень полезно если буквы отличить сможешь :)

Явно, что нормальный погроммист вменяемые имена был дал, но не математик.

1975 год.

Твой тапка уже родился или только дедушка с бабушкой встретились?

Так же любопытно было бы взглянуть на твои книги по которым учился весь мир, о Великий с ЧСВ :))

Да хрен с ним - кинь линк на свои проекты на github-е - дай приобщится к нетленке!!! :-)

Но это врядли. Нынешние годятся только кислые посты на форумах тискать, 100% на замену ChatGPT-ой , резать к чёртовой матери!(С)ПВ

anonymous
()
Ответ на: комментарий от thesis

Он не предполагает увидеть в профессии обезьяну и не пишет для обезьян.

SuperStar! «Теперь так не носят»(С). Увы :(

anonymous
()
Ответ на: комментарий от annulen

Ты дал ссылку на правила расстановки фигурных скобок, про то как писать тело цикла в 1 строчку с оператором там ни слова (ни положительного ни отрицательного). Что касается скобок, то я много где видел правило «если тело из 1 следующей строки то скобки не ставим», но он этого более верным его считать не стану.

firkax ★★★★★
()

Нужно было использовать шрифт подходящий (Consolas, Source Code Pro и т.д.) тогда бы не было путаницы с 1 и l. Ну и внимательность само собой. Cheers!

axle_nix ★★
()
Для того чтобы оставить комментарий войдите или зарегистрируйтесь.