Сортировка массива в 1С

Рассмотрим на примерах основные алгоритмы сортировки массивов на 1С.

1. Основные определения

Сортировка — это последовательное расположение или разбиение на группы чего-либо в зависимости от выбранного критерия.

2. Сортировка пузырьком (Bubble sort)

Подробно пузырьку, больший элемент массива поднимается «вверх».

Описание алгоритма

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

Реализация

 Вывод

Метод пузырька оказывается крайне неэффективным на любом входном наборе данных. Единственный плюс алгоритма — простота его исполнения.

3. Сортировка вставками (Insertion sort)

Выбираем и вставляем элемент в нужную позицию.

Описание алгоритма

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

Реализация

 Вывод

Метод оказывается эффективным только на маленьких массивах (не более 10), на массивах больших размеров, в силу асимптотической сложности n^2, алгоритм оказывается крайне не эффективным.

4. Сортировка выбором (Selection sort)

Упорядочиваем постепенно массив, заполняя первую позицию неупорядоченной части минимальным элементом из неупорядоченной части.

Описание алгоритма

Шаги алгоритма: находим номер минимального значения в текущем списке, производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции), теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы. Для реализации устойчивости алгоритма необходимо в пункте 2 минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов.

Реализация

 Вывод

Метод оказывается эффективным только на маленьких массивах (не более 10), на массивах больших размеров, в силу асимптотической сложности n^2, алгоритм оказывается крайне не эффективным.

5. Сортировка Шелла (Shell sort)

Алгоритм назван так в честь американского ученого Дональда Шелла.

Описание алгоритма

По своей сути этот алгоритм является усовершенствованным алгоритмом «Сортировка вставками». Смысл алгоритма заключается в том, чтобы сравнивать не только элементы, стоящие рядом друг с другом, но и на некотором удалении. Сначало выбирается Шаг — некий промежуток, через который будут сравниваться элементы массива на каждой итерации. Обычно его определяют так:
Для первой итерации Шаг = Цел(Массив.Количество()/2), для последующих Шаг = Цел(Шаг/2). Т.е. постепенно шаг сокращается и когда Шаг будет равен 1 произойдет последние сравнение и массив будет отсортирован.

Реализация

Вывод

Метод оказывается эффективным только на маленьких массивах, на массивах больших размеров алгоритм оказывается крайне не эффективным.

6. Сортировка слиянием (Merge sort)

Упорядочиваем списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.

Описание алгоритма

Для решения задачи сортировки эти три этапа выглядят так: 1) Сортируемый массив разбивается на две части примерно одинакового размера; 2) Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом; 3) Два упорядоченных массива половинного размера соединяются в один. 1.1. — 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным). 3.1. Соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива. Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда: 3.2. Слияние двух подмассивов в третий результирующий массив. На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.3. «Прицепление» остатка. Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.

Реализация

 Вывод

Метод оказывается крайне эффективным, однако требуется выделение дополнительной памяти.

 7. Гномья сортировка

Основана на технике, используемой обычным голландским садовым гномом.

Описание алгоритма

Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

Реализация

Вывод

Алгоритм не содержит вложенных циклов, а сортирует весь массив за один проход.

8. Быстрая сортировка (Quicksort)

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.

Описание алгоритма

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

  1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
  2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
    1. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
    2. Вычисляется индекс опорного элемента m.
    3. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
    4. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
    5. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
    6. Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.
  3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
  4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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

Реализация

 Вывод

Метод показывает высокую эффективноть, при этом он не требует расходов на дополнительную память. Однако, в худшем случае алгоритм оказывается крайне медленным (O(n2)).

9. Сортировка списком значений

Описание алгоритма

Передаем массив в список значений. Сортируем стандартным методом «Сортировать».

Реализация

Вывод

Алгоритм показал высокие результаты сортировки, как на небольших так и на больших объемах данных.

10. Какую сортировку использовать?

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *