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

Публикация № 128251

Разработка - Практика программирования

Реализовано средствами 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
58
.epf 8,72Kb 58 Скачать

Специальные предложения

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

См. также

Вам нравятся запросы в 1С? Промо

Практика программирования Разработка v8 v8::Запросы 1cv8.cf Абонемент ($m)

Речь не только о том, что простейший запрос с "легальным" оформлением растянется на пол-экрана, речь еще обо всем, что нужно написать "в нагрузку" к тексту запроса. Все эти "Новый Запрос", "УстановитьПараметр" и последующие пляски с обработкой результата... Пора с этим заканчивать!

1 стартмани

03.07.2019    21119    5    m-rv    88    

Интерактивная справка по объектам 1С (автономное расширение)

Практика программирования Работа с интерфейсом v8 ERP2 Абонемент ($m)

База знаний, подключаемая к объектам основной базы. Ведётся интерактивно, формируется в виде статей прямо в 1С (текст, картинки, таблицы, ссылки). Есть возможность прикрепления файлов, привязки к объектам 1С, возможности рейтинга и комментирования пользователями.

3 стартмани

29.09.2020    6535    30    sapervodichka    33    

Конвейер проверки качества кода

Инструментарий разработчика Практика программирования Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

Jenkinsfile для выполнения проверки качества кода. Собирает информацию с АПК, EDT и BSL-LS. Сопоставляет ошибки с гит-репозиторием, выгруженным ГитКонвертором. Отправляет в Сонар.

3 стартмани

04.09.2019    25474    22    Stepa86    46    

Алгоритмы поиска пути в графе

Практика программирования Разработка v8 1cv8.cf Абонемент ($m)

Реализуем алгоритмы поиска пути в графе на платформе 1С 8.3, такие как алгоритм А*, поиск в ширину, жадный поиск, алгоритм Дейкстры и вконце волновой.

1 стартмани

09.07.2019    17909    11    RonX01    10    

ВСТАВИТЬ В Справочник.Номенклатура (Код, Наименование) ЗНАЧЕНИЯ ("001", "Новый товар") Промо

Практика программирования v8 v8::Запросы 1cv8.cf Абонемент ($m)

Вас не обманывают ваши глаза, это запрос на изменение данных! И это работает без прямого доступа к БД, регистрации и смс.

1 стартмани

01.06.2018    30842    86    m-rv    57    

Работа с публикациями "Инфостарт"

Практика программирования О сообществе WEB v8 УУ Абонемент ($m)

Работа с рублевыми публикациями на сайте "Инфостарт": ведение клиентов, заказов, обновление файлов публикации, рассылка обновлений.

1 стартмани

13.09.2018    22080    13    RocKeR_13    16    

HTTP Сервисы: Путь к своему сервису. Часть 3

Инструментарий разработчика Практика программирования v8 1cv8.cf Абонемент ($m)

Продолжение статьи «HTTP Сервисы: Путь к своему сервису. Часть 2». В предыдущих частях мы использовали только Get, в этой части поговорим о других методах и длительных операциях.

1 стартмани

27.08.2018    38602    56    dsdred    17    

Позиционирование в помещении с помощью нейросети по сигналу Wi-Fi. Интерактивная карта склада в 1С с показом позиции

Инструментарий разработчика Практика программирования v8 Абонемент ($m)

Данная публикация содержит в себе редактор и интерактивную карту склада или иного помещения, на которой в реальном времени отображается позиция устройства, координаты которого вычисляются по уровням сигнала нескольких роутеров Wi-Fi. В статье и приложенным к ней разработкам предлагаются инструменты и методика для реализации вычисления точной геопозиции внутри помещений с помощью нейронной сети. Конфигурация написана на релизе 1С:Предприятие 8.3.12.1412, клиентское приложение имеет минимальный уровень совместимости SDK -16.

5 стартмани

09.08.2018    28584    26    informa1555    26    

Заполняем по шаблону (по умолчанию) Промо

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

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

1 стартмани

08.02.2018    28667    19    mvxyz    17    

Работа с данными выбора

Практика программирования Работа с интерфейсом v8 Россия Абонемент ($m)

В управляемом интерфейсе заложена мощная возможность описывать связи реквизитов формы через параметры. Установка параметров связей позволяет ограничить выбор данных так, чтобы целостность данных была обеспечена на этапе ввода. Однако без дополнительного программирования задать можно только самые простые связи. Такие условия связи, как зависимость от реквизита через точку или зависимость через дополнительное отношение, заданное в регистре сведений - уже задать без программирования не получится.

1 стартмани

17.07.2018    48880    17    kalyaka    16    

Полезные примеры составления схемы компоновки данных #2

Практика программирования v8 v8::СКД 1cv8.cf Абонемент ($m)

Еще один набор примеров как решить частные задачи в СКД

1 стартмани

22.05.2018    31620    11    SITR-utyos    13    

Печатная форма, сделанная как расширение конфигурации для БП 3.0. Новые возможности БСП

Практика программирования Универсальные печатные формы v8 БП3.0 Абонемент ($m)

Печатные формы на внешних обработках скоро канут в лету. На смену им приходят ПФ, реализованные в виде расширений конфигурации. Не нашел на сайте примеров таких расширений. Привожу пример подобного расширения для БП 3.0.

1 стартмани

06.12.2017    27381    54    kwazi    6    

Нечеткий поиск одним запросом Промо

Практика программирования v8 1cv8.cf Абонемент ($m)

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

1 стартмани

28.12.2015    28180    71    vasvl123    9    

Паузы при исполнении кода (Sleep для 1С)

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

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

1 стартмани

28.11.2017    46901    12    swimdog    42    

Макет в СКД - пример всех возможных типовых вариантов

Практика программирования Инструментарий разработчика v8 v8::СКД 1cv8.cf Абонемент ($m)

Макет СКД: наглядное представление того, что, как и куда выводится при типовых настройках.

1 стартмани

09.11.2017    22235    76    freelancer    4    

Telegram-боты

Практика программирования v8 Абонемент ($m)

Описание теории, разбор архитектуры и пример реализации telegram-ботов. Сразу скажу, со структурированием изложения мало что могу поделать. :) редакция от 18.07.2018 Правки последней редакции выделены жирным.

1 стартмани

01.09.2017    33171    132    PLAstic    59    

1С: Предприятие + корпоративный чат, как наладить оперативные уведомления за 10 минут Промо

Практика программирования v8 Абонемент ($m)

Как сделать автоматические уведомления о разных событиях из 1С в корпоративный чат MyChat для сотрудников компании

1 стартмани

14.08.2016    48538    36    Demanoidos    60    

Умный дом на 1С + ардуино

Практика программирования v8 Абонемент ($m)

Конфигурация для автоматизации быта программиста 1C и не только. В данной статье будет рассказано, как можно использовать 1С для задач, не входящих в стандартные рамки этой платформы. Например, управление домом. В качестве периферии для подключения будет использован микроконтроллер (МК) Ардуино, но на нём не будет никакой логической нагрузки, весь процесс будет проходить на сервере 1С. Работа с пинами ввода/вывода происходит напрямую из 1С.

1 стартмани

07.08.2017    23135    21    sasha777666    63    

Расширения конфигураций 1С: учимся перехватывать методы

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

В этой статье я на примерах разберу некоторые механизмы расширений конфигураций 1С. А именно «перехваты» методов модуля объекта и «перехваты» событий формы и элементов формы. Данная статья написана с учебными целями, чтобы показать, как при помощи расширений конфигурации можно делать такие доработки, ради которых раньше приходилось снимать конфигурацию с поддержки.

1 стартмани

30.05.2017    132251    13    signum2009    48    

Регулярные выражения – это просто. Построитель и отладчик регулярных выражений

Инструментарий разработчика Практика программирования v8 1cv8.cf Абонемент ($m)

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

1 стартмани

13.03.2017    31868    113    romasna    49    

Быстрое определение интервалов в запросе Промо

Практика программирования v8 Абонемент ($m)

В статье описывается новый метод определения интервалов между данными различных записей в запросе. В отличие от общеизвестного метода, время работы предлагаемого метода зависит от объема данных ЛИНЕЙНО. Это обеспечивает ему значительный выигрыш по быстродействию на больших объемах данных. В качестве иллюстрации возможностей метода приведен отчет, показывающий гистограмму распределения времени между продажами.

1 стартмани

01.10.2015    52105    35    ildarovich    41    

Распознавание текста с помощью нейросетей Google Cloud Vision и 1С

Практика программирования v8 1cv8.cf Абонемент ($m)

Возможности Google Cloud Vision в распознавании текста.

1 стартмани

08.02.2017    29994    127    kiv1c    18    

Графическая схема. Управление при помощи XDTO.

Практика программирования v8 Абонемент ($m)

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

2 стартмани

16.01.2017    22731    105    Alxby    23    

Простой редактор плана помещения JavaScript

Практика программирования Работа с интерфейсом v8 1cv8.cf Абонемент ($m)

На ресурсе сейчас очень много решений, которые позволяют редактировать карты, используя географические схемы. Так же много решений, которые позволяют редактировать объекты онлайн веб-карт. Мне же нужно было простое решение, для того чтобы расставить квадратные объекты на плане, показать их пользователю. Ну и распечатать, опять же. Я решил написать простенький редактор на JavaScript с использованием библиотеки Raphael.

1 стартмани

23.11.2016    21416    96    igel9780    22    

Хранение файлов в томах на диске (для УПП 1.3) Промо

Практика программирования v8 УПП1 Абонемент ($m)

Доработка типовой УПП 1.3 в плане хранения присоединенных файлов вне базы данных

2 стартмани

05.06.2016    58140    10    wowik    32    

Работа с двоичными данными на примере чтения файлов изображений. Новые возможности 8.3.9

Практика программирования WEB v8 1cv8.cf Россия Абонемент ($m)

В статье приводятся новые функции по работе с двоичными данными, появившимися в версии платформы 8.3.9 , на примере анализа формата и размера изображений. А также пример отправки изображения через API ВКонтакте с помощью новых объектов (без использования ОбъединитьФайлы())

1 стартмани

14.11.2016    26531    16    Anton64    22    

Загрузка файлов на сервер с прогрессом и докачкой

Практика программирования v8 1cv8.cf Россия Абонемент ($m)

Пример использования новых возможностей платформы 8.3.9 по низкоуровневой работе с двоичными данными для инкрементальной передачи файлов на сервер.

1 стартмани

04.10.2016    13564    53    mrstomak    21    

Несколько шаблонов для доработки типовых конфигураций

Практика программирования Инструментарий разработчика v8 v8::УФ Абонемент ($m)

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

1 стартмани

03.10.2016    37018    95    json    25    

HTTP-сервис: отчеты [Расширение]

Практика программирования Работа с интерфейсом v8 1cv8.cf Абонемент ($m)

Это HTTP-сервис, который возвращает почти любой отчет в HTML, XLSX или в JSON. Сохраните вариант отчета, получите на него ссылку и можно получить данные без захода в 1С. Работает в конфигурациях на основе БСП 2.3.3+, для отчетов на СКД и в 1С 8.3.8+

2 стартмани

30.08.2016    27212    137    Stepa86    15    

Недокументированное использование стандартных форм Upd.

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

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

1 стартмани

26.07.2016    28642    77    ZhokhovM    60    

БСП 2.3 и БСП 3.0: Просто про выполнение внешней обработки в фоне (c индикацией прогресса выполнения)

Инструментарий разработчика Практика программирования БСП (Библиотека стандартных подсистем) v8 1cv8.cf Абонемент ($m)

Простое пояснение о том, как сделать внешнюю обработку с фоновым выполнением и индикацией процесса для любой конфигурации на основе БСП 2.3.2. UPDATE 20/09/19: добавлен вариант обработки с индикацией процента выполнения и статусом выполнения для БСП 3.0.

1 стартмани

18.05.2016    62514    184    rozer    65    

Остатки на каждый день в запросе

Практика программирования Учет ТМЦ Учет ТМЦ v8 1cv8.cf УУ Абонемент ($m)

Запрос формирует остатки товаров на каждый день в пределах выбранного периода.

1 стартмани

26.04.2016    59731    19    arakelyan    19    

Еще один способ расчета остатков на каждый день в запросе

Математика и алгоритмы Практика программирования v8 Абонемент ($m)

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

1 стартмани

24.04.2016    34963    49    ildarovich    23    

Вывод печатных форм с запросом данных в форму "Печать документов" из подсистемы БСП "Печать".

Практика программирования БСП (Библиотека стандартных подсистем) v8 1cv8.cf Абонемент ($m)

Все не раз видели, как в типовых конфигурациях, построенных на основе БСП (Библиотека стандартных подсистем), печатные формы, построенные на основе Табличного документа, выводятся в специальную форму "ПечатьДокументов". Эта форма входит в состав подсистемы "Печать" из БСП. При разработке своих печатных форм, иногда необходимо запросить у пользователя дополнительные данные необходимые для печати. Тут встает вопрос, как в этом случае вывести печатную форму в форму "Печать документа". В этой статье я рассмотрю, как реализовать вывод печатной формы в упомянутую форму из подсистемы "Печать", в случае если мы хотим перед выводом печатной формы запросить у пользователя дополнительные данные. Здесь будут рассмотрены два случая: когда реализуется печатная форма с использованием подсистемы "Дополнительные отчеты и обработки" и когда печатная форма добавляется в конфигурацию в режиме конфигуратора, т.е. вносятся изменения в типовую конфигурацию.

1 стартмани

29.03.2016    91391    181    lopatin    14    

Выполнение JavaScript кода из 1С в объекте Поле HTML Документа (HTML 5) и вызов события в 1С ПриНажатии

Практика программирования v8 1cv8.cf Россия Абонемент ($m)

Пример выполнения JS кода из 1С в Поле HTML Документа под управляемыми формами, с удобным получением результата в 1С(С помощью вызова привязанного события ПриНажатии к элементу ПолеHTMLДокумента)

1 стартмани

22.03.2016    82048    160    igo1    54    

Количество дней недели (понедельников/вторников/...) в заданном диапазоне одним запросом

Практика программирования v8 Абонемент ($m)

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

1 стартмани

03.03.2016    18548    1    Alexander.Shvets    5    

Простые радости жизни программиста 1С: выбор типа значения

Работа с интерфейсом Практика программирования v8 1cv8.cf Абонемент ($m)

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

1 стартмани

17.02.2016    50588    53    yuraos    17    

Отображение прогресса выполнения длительных операций в БСП и их отладка в текущем сеансе.

Практика программирования БСП (Библиотека стандартных подсистем) v8 1cv8.cf Абонемент ($m)

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

1 стартмани

17.02.2016    56028    179    balanton    23    

Яндекс.Деньги "Благотворительность"

Инструментарий разработчика Практика программирования v8 1cv8.cf Абонемент ($m)

Яндекс.Деньги теперь в 1С. Форма для приема благотворительных взносов. Форму легко сделать и вставить на любую страницу сайта или блога. Платежи будут приходить на ваш кошелек. На форме есть три способа платежа: из кошелька, с банковской карты, с баланса мобильного.

1 стартмани

16.02.2016    23606    8    Tatitutu    5    

Мастер рассылки e-mail 2.2 для управляемых форм

Практика программирования Email v8 v8::УФ ERP2 БП3.0 УТ11 Абонемент ($m)

Для пользователей: переделанный из старый разработки под 8.2 с использованием библиотеки Мастер рассылки e-mail 2.2 (ERP, УТ, БП) (Только управляемые формы), который теперь может запускаться под любой версией платформы с разрешенными или запрещенными модальными/синхронными вызовами в конфигурации. Также удобный выбор e-mail и их владельцев с помощью отбора динамического списка по любым критериям и галочки исключения.

1 стартмани

29.12.2015    37311    20    milkers    4    

Передача больших пакетов через веб-сервисы

Практика программирования Администрирование данных 1С Внешние источники данных v8 Абонемент ($m)

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

1 стартмани

06.12.2015    57546    48    YPermitin    19