А есть нормальная и адекватная литература по структурам данных и алгоритмам

Классика: Дональд Кнут, «Искусство программирования для ЭВМ» в 3 томах (может более поздние издания с 4-м томом, точно не помню).

Кормен

А точно ли это авторы что-то не то пишут, а не ТС путает сортировку деревом с топологической сортировкой?

Седжвик первое издание алгоритмов на C самая вменяемая и компактная книженция. Если хочется больше теории — очевидный Кормен.

Дональд Кнут, «Искусство программирования для ЭВМ»

Эта та книжка, где примеры на ассемблере? Хороший способ бесцельно потратить время.

Точно. По крайней мере википедия упорота на обоих языках (и на русском и на английском), как и большая часть сайтов, а разные авторы трактуют разные вещи одними и теми же терминами или скатываются исключительно к BST, который для сортировки не годен, если не все ключи уникальны.

Дональд Кнут, «Искусство программирования для ЭВМ»

Эта та книжка, где примеры на ассемблере?

для машины MIX. Она самая.

Хороший способ бесцельно потратить время.

А какая разница, на чём? Ну да, на си или на паскале было бы удобнее. Но скажи ещё спасибо, что не на алголе, потому что систему команд MIX выучить гораздо легче. А ещё там блок-схемы есть кроме кода. Да и какая разница, на чём? Освоил язык (а Кнут намеренно сделал его максимально простым и компактным) и вперёд! Алгоритмы же. А в качестве упражнения и закрепления материала можешь сам реализовывать на си или на чём тебе там больше нравится. А потом в глобальную сеть выложить. Будет и тебе польза, и остальным.

скатываются исключительно к BST, который для сортировки не годен, если не все ключи уникальны.

Почему? Там просто дубликаты будут идти в одно из поддеревьев, но работать то оно будет.

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

Так а у Вас откуда это предстваление том, что как правильно называть? Есть какой-то источник? Меня просто удивляет эта нестандартная трактовка.

может более поздние издания с 4-м томом

Есть только первая часть четвёртого тома (из трёх).

http://e-maxx.ru/algo неплох. https://neerc.ifmo.ru/wiki/ хорош, но там достаточно сложно описано.

А книжки в 2к18 уже не модно читать и писать.

для машины MIX

В новом издании весь код уже переписан на MMIX, если что.

А какая разница, на чём?

Ассемблер вроде нужен был, чтобы можно было сравнивать алгоритмы и их разные версии точно подсчитывая сложность выполнения инструкций этого виртуального компьютера. С языками так не получится.

https://www.ozon.ru/context/detail/id/18319699/

По этой книге есть (или был) великолепный двухсерийный курс на курсере в исполнении того же Роберта Седжвика.

И кажись есть этого же автора аналогичная книга только применительно к C++

Конечно же Chris Okasaki «Purely Functional Data Structures» (версия PhD тезиса свободно доступна)

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

В чем проблема с алголом? Всегда считал алгол, аду и паскаль родственными языками. Си тоже заимствовал из алгола операции типа +=.

Почему? Там просто дубликаты будут идти в одно из поддеревьев, но работать то оно будет.

Не совсем хорошо будет работать - смотри например тут, про описание реализации вставки. И да, там формулировка дерева другая несколько.

Так а у Вас откуда это предстваление том, что как правильно называть?

Что непонятно? Тыц про деревья.

Не, с тем как сделать вопросов нет, но убивает, какие разные формулировки в разных источниках. Т.е. говорим про разные вещи, а обзываем одинаково.

Из всего перечисленного мне понравился Кормен, хотя ИМХО можно было и больше написать.

У нас дубль создаст новый узел с точно таким же значением ключа и поместит его в правое поддерево узла с оригинальным ключом. В результате новый узел никогда не будет обнаружен в процессе поиска.

Так это же проблема их реализации (если можно иметь дубликаты, то надо их искать при поиске), а для сортировки вообще не проблема.

Что непонятно?

Не понятно с чего бы вдруг какие-то минорные разногласия в терминологии были проблемой.

https://en.wikipedia.org/wiki/Rosetta_Code полезен

Есть только первая часть четвёртого тома (из трёх).

Всё-таки неподъёмную задачу он на себя взвалил с этим «Искусством программирования» и так и не осилил до конца. Но то, что осилил, выполнил блестяще.

для машины MIX

В новом издании весь код уже переписан на MMIX, если что.

А в чём между ними разница, если в 2 словах?

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

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

С языками так не получится.

Хотя, конечно, с языками высокого уровня попроще. Но тут ещё надо было угадать тренды, какие языки вымрут, а какие останутся.

В чем проблема с алголом?

Да ни в чём. Против него я ничего не имею. Да и не могу иметь, т. к. не знаю этот язык. Просто он давно умер. И учить его сейчас только для того, чтоб понять книжку, имхо, намного сложнее, чем выучить ассемблер MIX с минимальным набором команд, т. к. Алгол был полноценным высокоуровневым языком.

оберон же

Не понятно с чего бы вдруг какие-то минорные разногласия в терминологии были проблемой.

Подумаешь в арифметике заменили бы деление с остатком делением нацело...

Okasaki Chris, «Purely Functional Data Structures», https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Этот вроде не обсирается.

При знании паскаля алгол читается очень легко, как псевдокод. Тем более учебные алгоритмы сортировки. Но первый том вышел в 68 году. Тогда ещё не было Паскаля, Микрософта и IBM pc, а программирование на ассемблере было обычным занятием.

Н. Вирт «Алгоритмы и структуры данных»

Си тоже заимствовал из алгола операции типа +=

В алголе := операция присваивания

первый том вышел в 68 году. Тогда ещё не было Паскаля, Микрософта и IBM pc, а программирование на ассемблере было

и си не было, зато алгол-68 как раз появился.

Нет, высокоуровневое программирование, конечно, уже давно практиковалось. Кроме алгола ещё и фортран был распространён. Наверно, было и ещё что-то, но даже этих 2 языков достаточно.

Скорее всего, он действительно хотел, чтоб читатель мог оценить скорость алгоритма чуть ли ни в машинных тактах. Возможно, дополнительной задачей было показать, что и на ассемблере можно писать ясный код.

Скорее всего, он действительно хотел

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

разве он при введении своей абстрактной машины не объясняет причины такого выбора?

Он объяснил, что реальные ассемблеры приходят и уходят и их очень много, поэтому каждый из них по отдельности мало кому нужен. С другой стороны, он оговорился, что ассемблер для несуществующей машины вообще никому не нужен. Но MIX очень похожа на все существующие (на тот момент) машины и в этом плане идеальна.

А вот что он написал про языки высокого уровня Алгол и Фортран (этого я не помнил, специально сейчас открыл предисловие к 1-му тому, ниже краткий пересказ, — перепечатывать полностью лениво):

1. они больше подходят для численных задач;
2. они сильно влияют на программиста, навязывая ему не самые оптимальные конструкции с точки зрения машины;
3. большинство примеров в книге очень короткие, и ассемблера для них достаточно;
4. все обязаны знать ассемблер, потому что без него никуда (напомню, что сей с крестами в то время не было);
5. для нескольких программ из нескольких глав необходим ассемблер.

Лучшая книжка из мне известных: Grokking Algorithms (бесплатно скачать).

Следует сделать её стандартом ISO и все книги только так писать.

В новом издании весь код уже переписан на MMIX, если что.

А в чём между ними разница, если в 2 словах?

У MMIX 64-бита, RISC-архитектура, 256 регистров общего назначения и никакого двоично-десятичного кодирования.

И кажись есть этого же автора аналогичная книга только применительно к C++

Начиналось все с Алгоритмов на Си (1990 год). Эта книга Седжвика самая кошерная. Дальше он занялся коммерцией: накачивание водой и дублирование под разные язычки. И примеры стали неряшливые.

Подумаешь в арифметике заменили бы деление с остатком делением нацело...

Нету такой разницы в терминах, хоть путаница иногда бывает. Просто никаких «единственно правильных» терминов не существует. Какие-то авторы добавляют определения для частных случаев, а какие-то нет. Какие-то термины популярны, какие-то нет, какие-то дублируют понятия. Я поэтому и удивился, услышав, что какой-то источник является более правильным чем другие.

P.S. Aho+Ullman «The Design and Analysis of Computer Algorithms», кажется, никто не вспомнил.

У MMIX 64-бита, RISC-архитектура, 256 регистров общего назначения и никакого двоично-десятичного кодирования.

Спасибо за информацию. Это, пожалуй, стоит купить.

Вот эта короткая и простая: https://www.ozon.ru/context/detail/id/4788523/

но хз есть ли там, что ты ищешь

Классика: Дональд Кнут

Это для лохматых ботанов из 70-х. Вот прям хочется каждого советующего Кнута запереть в кладовке и не выпускать пока он хотя бы первый том не прочитает вслух. Совершенно бесполезный талмуд.

Совершенно бесполезный талмуд.

Почему? Там много элементарных алгоритмов и основных структур с хорошим математическим обоснованием.

Скажи, что не осилил.

А ты все три тома уже прочитал? И упражнения сделал?

Еще нет. Но я уже передумал становиться программистом.

подсовываешь эту книжку чтоб чел тоже передумал?

А почему нет? Если не может осилить книжку рассчитанную на начинающего, то дальше будет очень сложно.

Скажи, что не осилил.

Открою страшную тайну: его никто не осиливает в полном объеме. А те кто таки осилил, как Седжвик тот же (учившийся у Кнута), тут же бегут писать книги по алгоритмам для людей.

Ахо Альфред В. Структуры данных и алгоритмы

книжку рассчитанную на начинающего

Эта книжка расчитана на начинающего ученого, балда. Просто возьми старые книги для кодеров (Вирт, Ахо) и сравни с этим талмудом. Можешь чисто внешне, даже не открывая.

Вот прям хочется каждого советующего Кнута запереть в кладовке и не выпускать пока он хотя бы первый том не прочитает вслух.

Первый том - самый полезный.

Вот прям хочется каждого советующего Кнута запереть в кладовке и не выпускать пока он хотя бы первый том не прочитает вслух.

если бы ещё еду заносили )

+1 :)