Вводная часть
Существует большое количество различных сортировок, которые применяются повсеместно в программах. Алгоритмы сортировок помогают сэкономить такие ресурсы, как время работы какой-либо части кода и, соответственно, время человека и память, используемую для выполнения вашей программы. Например:
При редактировании файла нет необходимости держать весь файл в оперативной памяти. Каждой строке присваивается порядковый номер, и после внесения изменений достаточно обновленные строки отсортировать и вставить в сам файл.
Группировка элементов по признакам, которые характеризуются определенным числом или текстовой величиной (символы также поддаются упорядочиванию, например, по расположению их в алфавите или по номеру в таблице символов Юникода)
При сравнении двух и более таблиц или файлов для экономии времени достаточно отсортировать их. Таким образом, не надо "бегать" от одной строки к другой, а анализ будет более удобным и структурированным.
Алгоритмы сортировок применяются в различных областях, причина их использования состоит и в упорядочивании тех или иных структур для простоты понимания человеком, и в оптимизации работы программы по отношению к ресурсам компьютера.
Каждый алгоритм сортировки обладает такой характеристикой, как сложность (худший, средний и лучший случаи) и устойчивость.
Устойчивая сортировка — сортировка, не меняющая относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
В статье публикуются программные коды сортировок на языке C++, в которых присутствует функция, меняющая местами элементы в массиве:
template <typename T>
void swap(std::vector<T>& arr, unsigned int A, unsigned int B) {
T temp = arr[A];
arr[A] = arr[B];
arr[B] = temp;
}Простые виды сортировок
В этой части мы познакомимся с некоторыми алгоритмами, которые не применяются в общем случае из-за не особо большой скорости их работы, однако, позволяют вникнуть в некоторые принципы сортировки, используемые в более сложных алгоритмах.
Сортировка обменом (Exchange Sort)
Сначала сравнивается первый элемент со всеми последующими и меняется местами со сравниваемым, если требуется (зависит от условия: сортировка выполняется по возрастанию или по убыванию). Затем аналогичная процедура выполняется для второго, третьего и т.д.
Код на C++:
template <typename T>
void exchangeSort(std::vector<T>& arr) {
for (unsigned int i = 0; i < arr.size() - 1; i++) {
for (unsigned int j = i + 1; j < arr.size(); j++) {
if (arr[i] > arr[j])
swap(arr, i, j);
}
}
}Сложность: O(n^2) (во всех случаях)
Не является устойчивой
Преимущества и недостатки:
+ Простота реализации
- Медленная
Сортировка выбором (Selection Sort)
Находится минимальный (или максимальный, если сортировка происходит по убыванию) элемент на всем отрезке массива и переставляется в начало этого отрезка. После длина отрезка уменьшается на единицу слева и процедура повторяется.
Код на C++:
template <typename T>
void selectionSort(std::vector<T>& arr) {
for (unsigned int i = 0; i < arr.size(); i++) {
unsigned int j_min = i;
unsigned int j = i + 1;
for (; j < arr.size(); j++) {
if (arr[j] < arr[j_min])
j_min = j;
}
if (j_min != j)
swap(arr, i, j_min);
}
}Сложность: O(n^2) (во всех случаях)
Не является устойчивой
Преимущества и недостатки:
+ Простота реализации
- Медленная
Сортировка пузырьком (Bubble Sort)
Происходит проход по массиву с обменом местами соседних элементов, если требуется (зависит от условия: сортировка выполняется по возрастанию или по убыванию), до тех пор, пока массив не будет полностью отсортирован.
Код на С++:
template <typename T>
void bubbleSort(std::vector<T>& arr) {
bool swapped;
do {
swapped = false;
for (unsigned int i = 0; i < arr.size() - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
swapped = true;
}
}
} while (swapped);
}Сложность: O(n) - лучший случай
O(n^2) - средний и худший случаи
Является устойчивой
Преимущества и недостатки:
+ Простота реализации
- Медленная
Сортировка вставками (Insertion Sort)
Первый элемент считается отсортированной частью массива. Последующие элементы переносятся в отсортированную часть на нужную позицию. Таким образом, при каждом переносе отсортированная часть увеличивается на один элемент.
Код на C++:
template <typename T>
void insertionSort(std::vector<T>& arr) {
for (unsigned int i = 1; i < arr.size(); i++) {
if (arr[i] < arr[i - 1]) {
unsigned int j = i;
while ((j > 0) && (arr[j] < arr[j - 1])) {
swap(arr, j, j - 1);
j--;
}
}
}
}Сложность: O(n) - лучший случай
O(n^2) - средний и худший случаи
Является устойчивой
Преимущества и недостатки:
+ Простота реализации
+ Быстрая на частично упорядоченных последовательностях
- Медленная в общем случае
Мини-заключение
Рассмотренные алгоритмы имеют достаточно небольшие скорости сортировки, поэтому в проектах следует использовать, например, сортировку Шелла (Shell Sort) или быструю сортировку (Quick Sort). Эти виды сортировок будут разобраны в следующей части.
Ссылка на код с сортировками
Комментарии (42)
Zara6502
28.05.2023 18:00Какие все умные и злые )
Кнут это замечательно, но непонятно, как и многие академические материалы они прекрасны, но не всегда. Да-да, я знаю, если я не понимаю что написано в Кнуте, то программирование это не моё, но мне нравится программировать, я с этого не зарабатываю, но многие алгоритмы написаны так сложно и порой совершенно непонятно, что всегда ищешь что-то простое, например чтобы разобраться с LZW и Huffman мне потребовалось почти 20 лет, 15 из которых я искал нужную книжку, но так и не нашел. В Ютубе есть канал, там рассказывают о сложном простыми словами и я смотрю его, например о формате PNG было очень познавательно.
Вот например до сих пор не могу найти нормальное описание CCITT Group 4.
IkaR49
28.05.2023 18:00PNG сложный? Когда мне надо было ручками в HEX-редакторе поправить png-картинку, я открыл официальную спецификацию и через пол часа сделал то, что мне было нужно. Да, я не разобрался до конца, и не смогу написать сходу (ен|де)кодер png, но я понимаю его структуру и заложенную в формат идею.
Тот же gzip мне показался сложнее.
Zara6502
28.05.2023 18:00PNG сложный? Когда мне надо было ручками в HEX-редакторе поправить png-картинку, я открыл официальную спецификацию и через пол часа сделал то, что мне было нужно
Вот эта спецификация для меня слишком сложна для освоения. И вы же понимаете что сравнивать вас и меня нет смысла, мы разные, с разными умениями и возможностями. Например я помню что-то не больше 2-3 дней если просто прочитал, если пользуюсь постоянно, то могу быстро вспомнить, но совсем не обязательно что вспомню. Например когда программирую то открытыми держу 4-5 старый своих проектов и подглядываю как и что я делал раньше, потому что я помню только основные наборы языка if, for, while, всё остальное не помню и читаю в гугле как оформляется та или иная команду, смотрю примеры.
Я лучше понимаю материал который идет от сложного к простому, спеки они же сухие и формализованные, я такую информацию понимаю плохо.
но я понимаю его структуру и заложенную в формат идею
В том то и дело что я по спекам этого не вижу. А переработанный материал и поданный иначе - понимаю. Поэтому я Хаффмана очень долго не могу понять пока не попал на какой-то текстовик, еще из FIDO, где псевдографикой было показано и рассказано, буквально на страничку. И теперь я бог хаффмана )
Тот же gzip мне показался сложнее
Читал спеки, такое не осилю. LZW тоже долго гайдов хороших не находил, были абстрактные примеры по которым картина не складывалась.
sshikov
28.05.2023 18:00многие алгоритмы написаны так сложно
И поэтому вы прочитали эту статью, и теперь знаете, как сортировать пузырьком? Ну я рад за вас, правда. Только знаете что? Вам это все равно не пригодится, потому что пузырьковая сортировка на практике бесполезна. При чем автор честно написал, что ни один из рассмотренных алгоритмов на практике не применяется. Потому что все они плохие. Ну и в итоге, ему допустим было интересно описать свое понимание, а нам-то с чего быть добрыми, читая в сотый раз одно и тоже, да еще и неправильно описанное? Ну кстати, за этот пост автору поставили аж 12 плюсов, как по мне, это еще и много, но 12 добрых нашлось.
Zara6502
28.05.2023 18:00оценки мало кто может поставить, я вот не мог никогда и не могу и сейчас, поэтому просто читаю. В закладки 54 человека добавили, я например не стал. И я не сказал что статья хорошая, я о том что многие считают что 40-60 лет назад всё придумано и больше ничего писать не нужно. Об этом речь. Мне вон аж в карму минус влепили, за что? За личную неприязнь? У меня просто своё мнение на этот счёт.
Человек написал первую часть, учтёт критику, вторую напишет лучше, во всяком случае постарается.
Ну и Хабр не обязан быть только таким, каким вы себе его представляете, тут уже давно дети читают, которым до понимания Кнута как до Луны пешком.
И не всё должно просто пригождаться, я много вещей читаю для себя, а потом никак не применяю. Кто-то читает романы о любви, кто-то детективы, а я люблю про алгоритмы и программирование.
sshikov
28.05.2023 18:00А зачем Кнута? Я кстати Кнута не советовал, и вам (как вы себя описываете) точно не посоветую. Есть много более простых книжек, с тех пор понаписали. Писать тексты для начинающих гораздо сложнее, чем для опытных. И я вот не верю, что у кого-то получится первую или даже вторую статью про давно изжеванную тему написать лучше, чем сто раз написано в одной из хороших книжек. Только мусора в поиске больше будет.
Zara6502
28.05.2023 18:00Чтобы найти простую книжку нужно знать ее название и что она простая, то есть по рекомендации, но рекомендация будет не факт что о простой для вас книжки, она будет простая для советующего. По факту её потом купить нужно (понятно что многое можно скачать за так). Мне периодически советуют книги или сам нахожу что-то, но пока ни разу ничего интересного для меня не встретил.
Вопрос не в том является конкретная статья хорошей, а в отношении других хабровчан к самой идее простых научпоповских статей. Почитайте внимательно комментарии.
(Так как я интересуюсь темой программирования для Atari XL/XE то имею около двух сотен книжек, читаю потихоньку, в 90% это просто хлам, а времени отнимает)
sshikov
28.05.2023 18:00Ну да, все правда. И что это меняет, с учетом того факта, что данный текст бесполезен?
Zara6502
28.05.2023 18:00Собственно вот мой комментарий: "Какие все умные и злые ) Кнут это замечательно, но непонятно, как и многие академические материалы они прекрасны, но не всегда"
И он в первую очередь написан в противовес тем кто пишет, что всё написано 40-50-60 лет назад, то есть они априори не приемлют новые статьи. Я не обсуждаю качество этой, хотя и уже написал что она слаба. Читайте внимательнее впредь.
BugM
28.05.2023 18:00Чуть ниже упомянутый простой и понятый Кормен это 1989 год. 34 года книжке. Все на самом деле уже написано.
Zara6502
28.05.2023 18:00Я его читал немного, не считаю эту книгой удобной, можно иногда подглянуть, оценил бы на 3+ (оценка не качества материала, а доступность и понятность изложенного), простой пример (цитата из книги):
1) "сортировка карт" - возможно ошибка перевода, но я представил ГИС систему и какие-то алгоритмы их сортировок. Потом по тексту понял что речь про игральные карты.
2) "в левой руке карты уже упорядочены, правой картой берем из упорядоченных карт карту и вставляем её в "нужное" место" - Кто определяет нужность места? Если карты уже отсортированы, то зачем еще их сортировать. (я не дебил, я понимаю что речь про взятие карты из колоды, надеюсь это так, ведь по тексту написано не так, и вставка в левую руку в соответствии с мастью и значением, но я уже прожженный дед, я уже привык читать такую ахинею, а школьники - нет).
3) "запишем этот алгоритм в виде процедуры" - ладно, допустим слово "алгоритм" многие знают и его описание дано по тексту выше, но слово "процедура" я впервые узнал на втором курсе на занятиях по "Теории и технологии программирования". То есть задолго то прочтения этой книжки я должен уже чему-то сильно научиться, в этом и проблема таких книг.
4) "Массив A[1..n]" - это вообще кто должен понять? Человек должен знать что такое массивы, множества, иметь бэкграунд какой-то по языкам программирования (две точки вы думаете будет понятно что означают?). При этом сортировка и описание алгоритма вставками прекрасно описываются без таких вещей. Я ни разу не видел первокурсника, который понимал бы такое. Когда я учился мы с этим только начинали знакомиться на 2 курсе на высшей математике.
5) "сортируется без дополнительной памяти" - это весьма излишняя информация, тут вопросы сразу и по аппаратной части и по ограничениям памяти и по тому, как сравниваются разные виды сортировок и т.п.
И это я только открыл книгу, это первый алгоритм. Судя по введению всё же авторы рекомендуют его для преподавателей, студентов и программистов и уверен студентов не первого курса, ну или со второго семестра. То есть книжка Кормена не подходит (про псевдокод промолчу вообще, я вырос на книжках 60-70-х и там было страшнее, но всё же он морально устарел).
BugM
28.05.2023 18:00Претензии к непонимаю базовых cs терминов необоснованны. Сортировки всегда преподаются после них. Не надо пытаться учить дифуры, до обычной алгебры.
Перед словом карт стоит добавить слово игральных и все станет понятно сразу. Ну такое. В переиздание наверно стоит добавить и не более того. А пример отличный. Как обычный человек сам изобретает и использует алгоритм про который идет речь.
Ресурсы это важно. Без упоминания и рассмотрения что сколько стоит это всё не имеет смысла. Пузырек отлично работает.
thevlad
28.05.2023 18:00В книжках это обычно более системно все описано, и в определенном смысле проще, вводится аппарат построения различных алгоритмов и доказательства корректности . По моему вкусу, как по простоте изложению, так и обхвату тематики, Кормен просто отличный. Сам его читал в начале нулевых, когда только учился.
Zara6502
28.05.2023 18:00системный подход в голове формируется в ВУЗе годам к 20, то есть читать такие книжки например в 12-15 лет почти на 100% будет фиаско. Вы слишком оптимистично смотрите на возможности обучающихся, я работаю в ВУЗе почти 15 лет и у меня нет иллюзий по поводу умственных способностей среднестатистического студента. Несомненно есть ВУЗы где обучаются гении, но какой смысл писать книжки только для гениев? Основная масса людей совсем не гении и таковыми никогда не будут.
Посмотрите на статьи в википедии, она уж точно не для гениев написана, я её читаю регулярно, в большинстве своем мои запросы всегда выглядят так "comb sort wiki", читаю там и почти всегда этого достаточно, иногда изучаю ссылки на источники, углубленно могу потом поискать специализированную статью или сайт, часто в выдаче будет Хабр и часто не одна статья. Многие статьи на Хабре весьма хороши (я это знаю), но понять что-то из них мне невозможно. Ищу что-то другое.
И что я точно никогда не скажу - что если какой-то материал изложен и понятен мне, то он будет понятен всем. Люди разные настолько, что это даже иногда до мурашек пробирает. На одни и те же данные может быть абсолютно противоположная реакция и решения. Если вы не работали с детьми, то вы всегда будет опираться на ошибку выжившего.
thevlad
28.05.2023 18:00Да, я в курсе кто учится в ВУЗах. ) Поэтому и советую, то что считаю наиболее доступным, при этом содержащее достаточно хорошего материала, и правильного, системного подхода к предмету. Кнута я к примеру и сам не осилил. Кормен очень хорош, даже если сравнивать с википедией.
bogolt
28.05.2023 18:00+2При редактировании файла нет необходимости держать весь файл в оперативной памяти. Каждой строке присваивается порядковый номер, и после внесения изменений достаточно обновленные строки отсортировать и вставить в сам файл.
Замечу тут, что нельзя просто "вставить в файл" отредактированные строки зная их номера. В файл мы вставляем данные по смещению а не номеру строки, да и вообще вставка в файл затирает данные которые были в том месте куда мы вставляли данные. Придется перезаписывать весь файл целиком, а значит все равно придется весь файл загрузить в оперативную память ( хотя не обязательно сразу весь целиком, можно конечно читать/писать его частями ).
Zara6502
28.05.2023 18:00еще в эпоху DOS я писал файлы через прерывание, кажется 21h, и всегда занимало как обновление архива RAR на дискетке происходило куда быстрее чем перезапись всего файла, то есть формально 1.4 Мб диска (например файл целиком на весь диск) будут перезаписаны целиком что в варианте с копированием что с обновлением архива, но по факту обновление архива происходило быстрее. Мы тогда сошлись во мнении что RAR работает напрямую с FAT (но это лишь предположение).
gatoazul
Небольшой лайфхак: если вам нужно отсортировать данные, вызовите функцию из стандартной библиотеки. Она там уже лет шестьдесят.
Ksoo
Это если данные помещаются в памяти
BugM
Если не помещаются, то вызовите стандартную функцию сортировки той системы где они у вас лежат. Она там есть с момента создания этой системы.
NeoCode
А если вам нужно что-то посчитать, воспользуйтесь калькулятором:) Зачем учить математику в школе 10 лет?
В общем, с практической точки зрения - конечно да, мы воспользуемся стандартной функцией сортировки, и посчитаем на калькуляторе. Но теория все равно интересна. Понимание того как это работает, понимание концепции вычислительной сложности очень важно даже для использования стандартных алгоритмов. И еще, это вроде простые вещи, но все гениальное просто, и имеет свое очарование.
BugM
Этой теории уже примерно 70 лет. Есть любые учебники и любые лекции в общем доступе. Они гораздо лучше всего что я или вы сможем написать. Больше не надо.
NeoCode
А математике наверное несколько тысяч лет:) Но я бы здесь, именно в формате таких вот легких статей, с удовольствием почитал бы про какой нибудь мат.анализ (как повторение давно пройденного и благополучно забытого). Пределы, производные, интегралы, первообразные и вот это всё. С картинками. Желательно с цветными и анимированными, чего точно нет в учебниках.
Если фактических искажений в подаче материала нет, и статья написана в приятном для чтения стиле, то такие статьи вполне имеют право на существование.
BugM
А чем вас не устраивает любой учебник или любые записанные лекции? Вы можете выбрать по вкусу, их достаточно прямо вообще любых. Они сделаны профессионалами в образовании и гораздо лучше любых любительских поделок.
Myclass
Вы можете со мной не согласиться, но просто повторять то, что уже много десятилетий описано уйму раз и не внести что-нибудь нового - в материале или подачи материала - то тогда зачем вообще писать. Ведь если вам хочется про анализ почитать, вбейте в поиске "матанализ" и весь мир к вашим ногам. И в этой статье нет ни одного момента, который что-нибудь по другому показал в сортировках.
Скажу больше - пояснение очень непонятное. Если я не знал-бы все эти алгоритмы, то из рисунков я ничего-бы не понял.
gatoazul
...вплоть до видео сортировки в виде народных танцев
https://www.youtube.com/watch?v=5JMInXAtnQg&pp=ygUy0LDQu9Cz0L7RgNC40YLQvNGLINGB0L7RgNGC0LjRgNC-0LLQutC4INGC0LDQvdGG0Ys%3D
gatoazul
В стандартной библиотеке еще несколько десятков функций. Почему из них интересна только сортировка?
Ksoo
Большие данные очень часто лежат просто в файлах.И средствами файловой системы данные в них не отсортировать
BugM
Вы хотя бы раз реально видели такое? С ними же невозможно работать в таком виде. И значит они бесполезны в таком виде.
Большие данные лежат в БД. Как бы это удивительно для вас не было. И эти БД умеют их сортировать. Я вам точно говорю.
sshikov
Каждый день вижу.
Нет. Они лежать в виде файлов Parquet. И никакой "стандартной функции сортировки", которая была бы заведомо пригодна для данных размером теребайт 100, например в Hadop, не существует.
Неправда. То что вы знаете про базы (и это в общем верно) — это далеко не все что бывает в жизни. Каждую конкретную партицию или таблицу просто сортируют каждый раз при записи. А при чтении пользуются тем, что она отсортирована. Кстати баз это тоже касается — если вы знаете, что у таблицы уже есть порядок, вы можете этим воспользоваться, чтобы не сортировать. И вы (или оптимизатор) этим реально пользуетесь, а не вызываете тупо некую "функцию" сортировки.
BugM
А что такое secondary sort в Хадупе тогда?
Сортировка просто существует. В любой бд, по чему угодно. Это же базовая фича. Для бигдаты любая операция не использующая первичный ключ занимает много времени. Это тоже базовое свойство бигдаты.
А зачем вы данные храните не в БД я не знаю. Это странно. Данные нужны чтобы к ним запросы делать, а не чтобы просто лежали.
Ksoo
Я много раз это видел, и много раз видел как в хорошие програмисты пассовали перед задачей, потому что ее нельзя было сделать средствами готовой библиотеки.
Ваша притензия актуальна к "Зачем на собеседовании спрашивать написать алгоритм сортировки, если в языке есть встроеная". Но в контестке чисто теории, ваша претензия мне кажется не уместной.
andrewdeath
cat file | sort > sorted_file
может проканать))
white-wild
Вопрос в понимании, что и как делает инструмент, которым ты пользуешься.