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

17.05.12

Разработка - Математика и алгоритмы

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

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

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

Попалась на глаза интересная ссылка 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

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4415    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

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

1 стартмани

09.06.2023    7458    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7854    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8834    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

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

31.08.2021    7801    dusha0020    8    

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