gifts2017

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

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