Классические алгоритмы сортировки данных

Опубликовал ediks (ediks) в раздел Программирование - Практика программирования

Реализовано средствами 1С несколько простых классических алгоритмов сортировки данных. Приведено сравнение быстродействия рассмотренных алгоритмов.

Попалась на глаза интересная ссылка http://algolist.manual.ru/sort/index.php, где автор подробно разбирает алгоритмы сортировки. Результатом явилась представленная обработка. Написана на 8.2 на УФ, но переписать на 8.1 (или даже на 8.3 Laughing) не представляет особого труда.

В обработке рассмотрены следующие алгоритмы (как они описаны в Wikipedia):

Сортировка простыми обменамисортироL9;вка пузырькоL9;м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).

Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки.

Сортировка выбором (Selection sort) — алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.

Сортировка вставками — простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка).

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Для сравнения приведен способ сортировки, предложенный в публикации Заметочки про 1С:Предприятие 8 (редакция 23.03.2012). По результатам испытаний - это наиболее быстрый алгоритм. Хотя я думаю, это связано с тем, что в этом способе сортировка выполняется на "аппаратном уровне" и в каком-то виде показывает различие в быстродействии между интерпретатором (конфигурация 1С) и компилятором (платформа 1С).

После него идет алгоритм быстрой сортировки, что, собственно, неудивительно. Все остальные алгоритмы уходят в себя при количестве элементов более 5-10 тыс. При количестве элементов = 100 тыс. дождаться выполнения этих алгоритмов мне представляется нереальным.

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

Скачивайте, комментируйте, критикуйте (конструктивно Laughing).

Использованные материалы:

http://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%F1%EE%F0%F2%E8%F0%EE%E2%EA%E8

http://algolist.manual.ru/sort/index.php

Скачать файлы

Наименование Файл Версия Размер
Сортировка массивов
.epf 8,72Kb
16.05.12
54
.epf 8,72Kb 54 Скачать

См. также

Комментарии
1. Сергей Рудаков (fishca) 1039 17.05.12 11:49 Сейчас в теме
т.е. Быстрая сортировка и сортировка 1С не отличаются по времени выполнения?
2. ediks (ediks) 319 17.05.12 12:02 Сейчас в теме
(1) Конечно, отличаются во много раз при большем количестве элементов. Просто на данной картинке хотелось показать все алгоритмы.
Прикрепленные файлы:
3. Сергей Рудаков (fishca) 1039 17.05.12 12:12 Сейчас в теме
(2) так какой самый быстрый алгоритм сортировки?
4. ediks (ediks) 319 17.05.12 12:27 Сейчас в теме
(3) Самый быстрый из рассмотренных классических - "Быстрая сортировка". Алгоритм "Сортировка 1С" выполняется на уровне платформы, поэтому сравнивать ее и "Быструю сортировку" не совсем корректно. Хотя в работе, конечно, следует использовать "Сортировку 1С" именно по той причине, что она выполняется на уровне платформы и, соответственно, намного быстрее любой программной реализации сортировки.
5. Сергей Рудаков (fishca) 1039 17.05.12 13:28 Сейчас в теме
(4) т.е. с практической точки зрения использовать сортировку отличную от "Сортировка 1С" не имеет смысла, кроме как чисто в академических целях?
6. ediks (ediks) 319 17.05.12 13:37 Сейчас в теме
(5) да, именно так. Ну, а другие алгоритмы можно использовать на собеседованиях :).
7. Василий Антонов (khaoos) 237 21.05.12 06:53 Сейчас в теме
Что такое сортировка 1С? Это когда массив заворачивается в список, сортируется и обратно разворачивается? А так, благодарность за исследование, плюс, однозначно. А вот если эти сортировки реализовать на компилируемом языке во внешней библиотеке? Наверное, потеряем много на передаче данных туда-сюда.
8. ediks (ediks) 319 21.05.12 11:08 Сейчас в теме
(7)
Да, совершенно верно, массив выгружаем в список, сортируем и обратно загружаем в массив. Это мое условное название - "Сортировка 1С". В основе ее, я думаю, лежит быстрая сортировка, т.к. в языке С qsort это вообще встроенная функция. Ну, а реализовывать эти алгоритмы в ВК - только в качестве тренировки создания ВК. Имхается мне, что практического смысла в этой реализации нет. По крайней мере, пока не вижу.
9. Алексей Прилепский (IamAlexy) 491 26.05.12 21:21 Сейчас в теме
нахрена это 1сникам и проектам на 1С?
10. Иван (Sairys) 29.05.12 09:44 Сейчас в теме
весело, интересная статья
11. Александр Романов (alexandr1972_1) 02.12.14 23:53 Сейчас в теме
(9) Иногда нужно представить массив в упорядоченную структуру.