Методы сортировки. Быстрая сортировка - один из лучших методов сортировки массивов

Для упрощения кода и улучшения читаемости мы введем метод Swap , который будет менять местами значения в массиве по индексу.

Void Swap(T items, int left, int right) { if (left != right) { T temp = items; items = items; items = temp; } }

Пузырьковая сортировка

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

Например, у нас есть массив целых чисел:

При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так:

Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так:

Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6.

И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз.

При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу.

Public void Sort(T items) { bool swapped; do { swapped = false; for (int i = 1; i < items.Length; i++) { if (items.CompareTo(items[i]) > 0) { Swap(items, i - 1, i); swapped = true; } } } while (swapped != false); }

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

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

Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса - уже отсортировано. На этом рисунке показано, как увеличивается отсортированная часть массива с каждым проходом:

Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.

Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:

Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным.

На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно.

Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex . Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки.

Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:

Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки.

Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена.

Public void Sort(T items) { int sortedRangeEndIndex = 1; while (sortedRangeEndIndex < items.Length) { if (items.CompareTo(items) < 0) { int insertIndex = FindInsertionIndex(items, items); Insert(items, insertIndex, sortedRangeEndIndex); } sortedRangeEndIndex++; } } private int FindInsertionIndex(T items, T valueToInsert) { for (int index = 0; index < items.Length; index++) { if (items.CompareTo(valueToInsert) > 0) { return index; } } throw new InvalidOperationException("The insertion index was not found"); } private void Insert(T itemArray, int indexInsertingAt, int indexInsertingFrom) { // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // // Действия: // 1: Сохранить текущий индекс в temp // 2: Заменить indexInsertingAt на indexInsertingFrom // 3: Заменить indexInsertingAt на indexInsertingFrom в позиции +1 // Сдвинуть элементы влево на один. // 4: Записать temp на позицию в массиве + 1. // Шаг 1. T temp = itemArray; // Шаг 2. itemArray = itemArray; // Шаг 3. for (int current = indexInsertingFrom; current > indexInsertingAt; current--) { itemArray = itemArray; } // Шаг 4. itemArray = temp; }

Сортировка выбором

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

Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве.

При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало.

Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение - 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход - на этот раз по индексам от 1 до n — 1.

На втором проходе мы определяем, что наименьшее значение - 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию.

Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован.

После еще двух проходов алгоритм завершает свою работу:

Public void Sort(T items) { int sortedRangeEnd = 0; while (sortedRangeEnd < items.Length) { int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd); Swap(items, sortedRangeEnd, nextIndex); sortedRangeEnd++; } } private int FindIndexOfSmallestFromIndex(T items, int sortedRangeEnd) { T currentSmallest = items; int currentSmallestIndex = sortedRangeEnd; for (int i = sortedRangeEnd + 1; i < items.Length; i++) { if (currentSmallest.CompareTo(items[i]) > 0) { currentSmallest = items[i]; currentSmallestIndex = i; } } return currentSmallestIndex; }

Сортировка слиянием

Разделяй и властвуй

До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer) .

Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге - один из примеров такого алгоритма.

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

Насколько эффективны эти алгоритмы?

Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.

Сортировка слиянием

При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.

Давайте посмотрим на такой массив:

Разделим его пополам:

И будем делить каждую часть пополам, пока не останутся части с одним элементом:

Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке.

Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.

Для работы алгоритма мы должны реализовать следующие операции:

Операцию для рекурсивного разделения массива на группы (метод Sort).
Слияние в правильном порядке (метод Merge).

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

Public void Sort(T items) { if (items.Length <= 1) { return; } int leftSize = items.Length / 2; int rightSize = items.Length - leftSize; T left = new T; T right = new T; Array.Copy(items, 0, left, 0, leftSize); Array.Copy(items, leftSize, right, 0, rightSize); Sort(left); Sort(right); Merge(items, left, right); } private void Merge(T items, T left, T right) { int leftIndex = 0; int rightIndex = 0; int targetIndex = 0; int remaining = left.Length + right.Length; while(remaining > 0) { if (leftIndex >= left.Length) { items = right; } else if (rightIndex >= right.Length) { items = left; } else if (left.CompareTo(right) < 0) { items = left; } else { items = right; } targetIndex++; remaining--; } }

Быстрая сортировка

Быстрая сортировка - это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:

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

Давайте посмотрим на работу алгоритма на следующем массиве:

Сначала мы случайным образом выбираем ключевой элемент:

Int pivotIndex = _pivotRng.Next(left, right);

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

Перемещение значений осуществляется методом partition .

На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива.

У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу.

Random _pivotRng = new Random(); public void Sort(T items) { quicksort(items, 0, items.Length - 1); } private void quicksort(T items, int left, int right) { if (left < right) { int pivotIndex = _pivotRng.Next(left, right); int newPivot = partition(items, left, right, pivotIndex); quicksort(items, left, newPivot - 1); quicksort(items, newPivot + 1, right); } } private int partition(T items, int left, int right, int pivotIndex) { T pivotValue = items; Swap(items, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { if (items[i].CompareTo(pivotValue) < 0) { Swap(items, i, storeIndex); storeIndex += 1; } } Swap(items, storeIndex, right); return storeIndex; }

Заключение

На этом мы заканчиваем наш цикл статей по алгоритмам и структурам данных для начинающих. За это время мы рассмотрели связные списки, динамические массивы, двоичное дерево поиска и множества с примерами кода на C#.

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

Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения).

В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36.

Для проведения исследования были выбраны следующие алгоритмы сортировки:

Selection sort (сортировка выбором) – суть алгоритма заключается в проходе по массиву от начала до конца в поиске минимального элемента массива и перемещении его в начало. Сложность такого алгоритма O(n2).

Bubble sort (сортировка пузырьком) – данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2).

Insertion sort (сортировка вставками) – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2).

Quick sort (быстрая сортировка) – суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получим отсортированный массив. Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n×2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n×log2n).

Comb sort (сортировка расческой) – идея работы алгоритма крайне похожа на сортировку обменом, но главным отличием является то, что сравниваются не два соседних элемента, а элементы на промежутке, к примеру, в пять элементов. Это обеспечивает от избавления мелких значений в конце, что способствует ускорению сортировки в крупных массивах. Первая итерация совершается с шагом, рассчитанным по формуле (размер массива)/(фактор уменьшения), где фактор уменьшения равен приблизительно 1,247330950103979, или округлено до 1,3. Вторая и последующие итерации будут проходить с шагом (текущий шаг)/(фактор уменьшения) и будут происходить до тех пор, пока шаг не будет равен единице. Практически в любом случае сложность алгоритма равняется O(n×log2n).

Для проведения тестирования будет произведено по 5 запусков каждого алгоритма и выбрано наилучшее время. Наилучшее время и используемая при этом память будут занесены в таблицу. Также будет проведено тестирование скорости сортировки массива размером в 10, 50, 200 и 1000 элементов чтобы определить для каких задач предназначен конкретный алгоритм.

Полностью неотсортированный массив:

Частично отсортированный массив (половина элементов упорядочена):

Результаты, предоставленые в графиках:

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

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

В основе методов внешней сортировки лежит процедура слияния, заключающаяся в объединении двух или более отсортированных последовательностей. Рассмотрим эту процедуру на примере слияния двух последовательностей A и B в последовательность C. Пусть элементы A и B отсортированы по возрастанию, то есть a 1 £ a 2 £ …£ a m и b 1 £ b 2 £ …£ b n . Требуется, чтобы последовательность C также располагалась по возрастанию, то есть выполнялось c 1 £ c 2 £ …£ c m + n .

Сначала в качестве текущих выбираются первые элементы последовательностей. Меньший из них записывается в C, и вместо него текущим становится следующий элемент этой же последовательности. Эта операция повторяется до исчерпания одной из последовательностей, после чего в C дописывается остаток другой последовательности.

Можно заметить, что доступ к элементам A, B и C выполнялся строго последовательно. В методах внешней сортировки в качестве последовательностей A, B и C фигурируют отсортированные участки файлов.

Базовым методом внешней сортировки является метод простого слияния. Рассмотрим его на следующем примере. Пусть имеется файл A, включающий элементы 27, 16, 13, 11, 18, 25, 7. Этот файл разделяется на два файла B и C путем поочередной записи элементов в эти файлы. Покажем это схемой

B: 27, 13, 18, 7

A: 27, 16, 13, 11, 18, 25, 7

Затем файлы B и C снова соединяются путем поочередного включения в C элементов из A и B. При этом первым располагается меньший элемент каждой пары. Получится следующий результат

B: 27, 13, 18, 7

Пары отделяются друг от друга апострофами. На следующем этапе снова происходит разделение файла A на B и C, но в каждый файл пишутся поочередно уже не отдельные элементы, а выделенные пары. Получаем

B: 16, 27,’ 18, 25

A: 16, 27,’ 11, 13,’ 18, 25, ‘ 7

B: 16, 27,’ 18, 25

A: 11, 13, 16, 27,’ 7, 18, 25

Затем файл A распределяется по четверкам элементов и при новом соединении будет состоять из упорядоченных восьмерок элементов. В нашем примере сортировка закончится на этом этапе. В общем случае длина отсортированных серий будет увеличиваться по степеням 2, пока величина серии не превзойдет количество элементов в файле.

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

Есть очевидное усовершенствование метода. Результат слияния сразу распределяется на две ленты, то есть в процессе участвуют уже 4 ленты. За счет дополнительной памяти число операций перезаписи уменьшается вдвое. Это однофазный четырехленточный метод, называемый также сбалансированным слиянием.

Как видно из приведенных выше данных, метод может конкурировать по скорости с самыми быстрыми методами внутренней сортировки, но не применяется в таком качестве, так как требует значительных затрат памяти. Число проходов оценивается величиной log 2 n, а общее число пересылок M пропорцинально n log 2 n.

Метод простого слияния не дает какого-либо выигрыша в тех случаях, когда файл A полностью либо частично отсортирован. Этот недостаток отсутствует в методе естественного слияния.

Назовем серией последовательность элементов a i , a i +1 , …, a j , удовлетворяющих соотношениям a i -1 > a i £ a i +1 £ …£ a j > a j +1 . В частных случаях серия может находиться в начале или конце последовательности.

Исходный файл A разбивается на серии. Распределение на B и C ведется по сериям. При соединении сливаются пары серий. Снова возможен как трехленточный, так и четырехленточный вариант метода. Ниже показан пример сортировки методом естественного слияния c 4 лентами.

B: 17, 25, 41, ‘6

A: 17, 25, 41, ‘ 9, 11, ‘ 6, ‘ 3, 5, 8, 44

C: 9, 11, ‘ 3, 5, 8, 44

A: 9, 11, 17, 25, 41 B: 3, 5, 6, 8, 9, 11, 17, 25, 41, 44

D: 3, 5, 6, 8, 44 C:

При последнем разделении лента C оказывается пустой, и отсортированный файл остается на ленте B.

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

Program SortSlian;

{ 3-ленточная, 2-фазная сортировка естественным слиянием }

{ ключи целые и положительные }

Type elem=record

{ другие поля }

tape=file of elem;

Name: string; { имя исходного файла }

Procedure Vvod(var F: tape);

While K <> -1 do

Write("Введите очередной ключ (конец -1): ");

if K<>-1 then Write(F, S)

Procedure Pech(var F: tape);

While not eof(F) do

Write(S. Key," ")

Procedure CopyElem(var X, Y: tape;

var Buf: elem; var E: boolean);

{ копирование элемента и считывание следующего

{ в Buf с проверкой конца серии (E=True) }

if not Eof(X) then Read(X, Buf)

else Buf.Key:=-1; { барьер: достигнут конец файла }

E:=(Buf.Key

Procedure CopySer(var X, Y: tape; var Buf: elem);

{ копирование серии из X в Y }

{в начале Buf-первый элемент текущей серии на X }

{в конце Buf-первый элемент следующей или –1 (конец X) }

if Buf.Key>0 then { файл X не считан }

CopyElem(X, Y, Buf, E)

Until E { E=True в конце серии }

Procedure Raspred;

{ распределение A ---> B и C }

Read(A, S); { первый элемент из A }

Rewrite(B); Rewrite(C);

CopySer(A, B, S); {S-первый элемент следующей серии }

if S.Key>0 then { файл A скопирован не весь }

CopySer(A, C, S)

Until S.Key<0

Procedure Slian;

{ слияние B и C--->A }

E1, E2: boolean;

Procedure SlianSer;

{ слияние серий из B и C ---> A }

{ S и T - первые элементы серий }

{ S.Key<0-весь файл B считан, T.Key<0-файл C считан }

E1:=False; E2:=False;

if (S.Key>0) and ((S.Key

{ файл B не считан и текущий элемент B меньше, чем в C либо файл C полностью считан }

CopyElem(B, A, S, E1);

if E1 then { достигнут конец серии на B }

CopySer(C, A, T)

CopyElem(C, A, T, E2);

if E2 then { достигнут конец серии на C }

CopySer(B, A, S)

Begin { начало Slian }

if not (Eof(B) or Eof(C)) then

begin { оба файла не пусты }

L:=0; { счетчик числа серий }

While (S.Key>0) or (T.Key>0) do

Begin { начало основной программы }

Write("Введите имя файла для записи элементов: ");

Assign(A, Name);

Assign(B, "Rab1");

Assign(C, "Rab2");

L:=0; { L - число серий после слияния - параметр }

WriteLn("Файл A: "); Pech(A);

Raspred; { фаза распределения }

WriteLn("Файл B: "); Pech(B);

WriteLn("Файл C: "); Pech(C);

ReadLn; { пауза }

Slian { фаза слияния }

Until L<=1; { L=0, если исходный файл отсортирован }

WriteLn("Файл A в конце: ");

Close(B); Erase(B); { удаление рабочих файлов }

Close(C); Erase(C);

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

Эффективность сортировки можно повысить, используя многопутевое слияние, в котором распределение выполняется на k лент. Поскольку число серий на каждом проходе уменьшается в k раз, количество пересылок M пропорционально величине n log k n. Если общее число лент четное, то можно использовать однофазный метод слияния, распределяя серии с одной половины лент на другую. Платой за повышение эффективности многопутевого слияния являются, как всегда, увеличение сложности реализации и дополнительные затраты внешней памяти.

На сколько может отличаться количество серий после разделения? На первый взгляд кажется, что не более, чем на одну, но это не так. Например, при распределении серий 17, 25, 41, ’ 9, 60, ‘ 50, 52, ‘ 7 первая и третья серии сливаются в общую серию, что не происходит со второй и четвертой сериями. В результате при последующем слиянии серии на одной из лент могут закончиться раньше, и придется впустую переписывать остаток другой ленты, теряя эффективность. Подобные ситуации учитываются в методе многофазной сортировки. Рассмотрим его на примере трех лент.

Пусть при соединении лент B и C на ленту A серии на B заканчиваются раньше. Тогда лента B объявляется выходной, а лента A становится входной. Процесс продолжается до нового повторения ситуации, когда серии на одной из входных лент заканчиваются. Многофазная сортировка возможна и при многопутевом слиянии. Например, при использовании в сортировке k лент можно постоянно иметь одну выходную ленту. При исчерпании серий на одной из k-1 входных лент эта лента становится выходной вместо предыдущей выходной ленты.

Методы внутренней и внешней сортировок могут использоваться совместно. Пусть сортируется большой по объему файл. В оперативной памяти выделяется буфер максимально возможного размера. Файл делится на блоки, соответствующие величине буфера. Блоки читаются в буфер, сортируются одним из методов внутренней сортировки и переписываются в другой файл. Сейчас каждый блок нового файла является серией достаточно большой длины, определяемой размером буфера. Остается применить один из методов внешней сортировки, использующий данные серии.

Введение .

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

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

1. Задачи сортировки.

1.1.Общие положения.

Основная задача – продемонстрировать различные методы сортировки и выделить наиболее эффективные из них. Сортировка – достаточно хороший пример задачи, которую можно решать с помощью многих различных алгоритмов. Каждый из них имеет и свои достоинства, и свои недостатки, и выбирать алгоритм нужно, исходя из конкретной постановки задачи.

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

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

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

Прежде чем идти дальше, введем некоторые понятия и обозначения. Если у нас есть элементы а , a, …… , а то сортировка есть перестановка этих элементов в массив а k, ak, …… , ak где ak ak ak .

Считаем, что тип элемента определен как INTEGER .

Constn=???; //здесь указывается нужная длина массива

Var A: array of integer;

Выбор INTEGER до некоторой степени произволен. Можно было взять и

другой тип, на котором определяется общее отношение порядка.

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

1.2. Постановка задачи сортировки массивов.

Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте т. е. методы, в которых элементы из массива а передаются в результирующий массив b, представляют существенно меньший интерес. Мы будем сначала классифицировать методы по их экономичности, т. е. по времени их работы. Хорошей мерой эффективности может быть C – число необходимых сравнений ключей и M – число пересылок (перестановок) элементов. Эти числа суть функции от n – числа сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n* logn сравнений, мы сначала разберем несколько простых и очевидных методов, их называют прямыми, где требуется порядка n2 сравнений ключей. Начинать разбор с прямых методов, не трогая быстрых алгоритмов, нас заставляют такие причины:

Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.

Программы этих методов легко понимать, и они коротки.

Усложненные методы требуют большого числа операций, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.

Методы сортировки “ на том же месте “ можно разбить в соответствии с определяющими их принципами на три основные категории:

Сортировки с помощью включения ( byinsertion).

Сортировки с помощью выделения ( byselection).

Сортировка с помощью обменов ( byexchange).

Теперь мы исследуем эти принципы и сравним их. Все программы оперируют массивом а.

Constn=

a: array ofinteger;

2. Методы сортировки массивов.

2.1. Простые методы сортировки массивов.

2.1.1. Сортировка с помощью прямого включения.

Такой метод широко используется при игре в карты. Элементы мысленно делятся на уже “готовую” последовательность а , … , а и исходную последовательность. При каждом шаге, начиная с I = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i- й элементы и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

ПРОГРАММА 2.1. ССОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВКЛЮЧЕНИЯ.

I,J,N,X:INTEGER;

A:ARRAY OF INTEGER;

WRITELN(‘Введите длину массива’);

READ(N);

WRITELN(‘Введите массив ’);

FOR I:=1 TO N DO READ(A[I]);

FOR I:=2 TO N DO

WRITELN("Результат:");

END.

Такой типичный случай повторяющегося процесса с двумя условиями

окончания позволяет нам воспользоваться хорошо известным приемом

“барьера” (sentinel).

Анализ метода прямого включения. Число сравнений ключей ( Ci) при i- м просеивании самое большее равно i-1, самое меньшее – 1; если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнений – I/2. Число же пересылок Mi равно Ci + 2 (включая барьер). Поэтому общее число сравнений и число пересылок таковы:

Cmin = n-1 (2.1.) Mmin = 3*(n-1) (2.4.)

Cave = (n2+n-2)/4 (2.2.) Mave = (n2+9*n-10)/4 (2.5.)

Cmax = (n2+n-4)/4 (2.3.) Mmax = (n2+3* n-4)/2 (2.6.)

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

ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ.

I,J,M,L,R,X,N:INTEGER;

A:ARRAY OF INTEGER;

WRITELN("Введи массив");

FOR I:=1 TO N DO READ(A[I]);

FOR I:=2 TO N DO

X:=A[I];L:=1;R:=I;

FOR J:=I DOWNTO R+1 DO A[J]:=A;

WRITELN("Результат:");

FOR I:=1 TO N DO WRITE(A[I]," ")

END.

Анализ двоичного включения. Место включения обнаружено, если L= R. Таким образом, в конце поиска интервал должен быть единичной длины; значит, деление его пополам происходит I* logI раз. Таким образом:

C = Si: 1i n : [ logI ] (2.7.)

Аппроксимируем эту сумму интегралом

Integral (1:n) log x dx = n*(log n – C) + C (2.8.)

Где C = loge = 1/ ln 2 = 1.4426… . (2.9.)

2.1.2.Сортирвка с помощью прямого выбора.

Этот прием основан на следующих принципах:

Выбирается элемент с наименьшим ключом

Он меняется местами с первым элементом а1.

Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.

ПРОГРАММА 2.3. СОРТИРВКА С ПОМОЩЬЮ ПРЯМОГО ВЫБОРА.

I,J,R,X,N:INTEGER;

A:ARRAY OF INTEGER;

WRITELN("Введи длину массива");

WRITELN("Введи массив");

FOR I:=1 TO N DO READ(A[I]);

FOR I:=1 TO N-1 DO

FOR J:=I+1 TO N DO IF A[J]

WRITELN("Результат:");

FOR I:=1 TO N DO WRITE(A[I]," ")

END.

Анализ прямого выбора. Число сравнений ключей (С), очевидно не зависит от начального порядка ключей. Для С мы имеем C = (n2 – n)/2 (2.10.).

Число перестановок минимально: Mmin = 3*(n-1) (2.11.).

В случае изначально упорядоченных ключей и максимально Mmax = n2/4 + 3*(n-1) (2.12.)

Определим М avg . Для достаточно больших n мы можем игнорировать дробные составляющие и поэтому аппроксимировать среднее число присваиваний на i-м просмотре выражением Fi = lni + g + 1 (2.13.), где g = 0.577216… - константа Эйлера.

Среднее число пересылок Mavg в сортировке с выбором есть сумма Fi с i от 1 до n

Mavg = n*(g + 1) + (Si: 1

Вновь аппроксимируя эту сумму дискретных членов интегралом

Integral (1:n) ln x dx = x*(ln x – 1) = n*ln (n) – n + 1 (2.15.)

Получаем приблизительное значение

Mavg = n*(ln (n) + g) . (2.16.)

2.1.3. Сортировка с помощью прямого обмена .

Как и в методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу.

ПРОГРАММА 2.4. ПУЗЫРЬКОВАЯ СОРТИРОВКА.

PROGRAMBS;

I,J,X,N:INTEGER;

A:ARRAY OF INTEGER;

WRITELN("Введи длину массива");

WRITELN("Введи массив");

FOR I:=1 TO N DO READ(A[I]);

FOR I:=2 TO N DO

FOR J:=N DOWNTO I DO

IF A>A[J] THEN

WRITELN("Результат:");

FOR I:=1 TO N DO

END.

Улучшения этого алгоритма напрашиваются сами собой:

Запоминать, были или не были перестановки в процессе

некоторого прохода.

Запоминать не только сам факт, что обмен имел место, но и

положение (индекс) последнего обмена.

Чередовать направление последовательных просмотров.

Получающийся при этом алгоритм мы назовем “шейкерной” сортировкой ( ShakerSoft).

Анализ пузырьковой и шейкерной сортировок. Число сравнений в строго обменном алгоритме C = (n2 – n)/2, (2.17.), а минимальное, среднее и максимальное число перемещений элементов (присваиваний) равно соответственно M = 0, Mavg = 3*(n2 – n)/2, Mmax = 3*(n2 – n)/4 (2.18.)

Анализ же улучшенных методов, особенно шейкерной сортировки довольно сложен. Минимальное число сравнений Cmin = n – 1. Кнут считает, что улучшенной пузырьковой сортировки среднее число проходов пропорционально n – k1 n1/2, а среднее число сравнений пропорционально ½( n2 – n(k2 + lnn)).

ПРОГРАММА 2.5. ШЕЙКЕРНАЯ СОРТИРОВКА.

PROGRAMSS;

J,L,K,R,X,N,I:INTEGER;

A:ARRAY OF INTEGER;

WRITELN("Введи длину массива’);

WRITELN("Введи массив");

FOR I:=1 TO N DO

FOR J:=R DOWNTO L DO

IF A>A[J] THEN

FOR J:=L TO R DO

IF A>A[J] THEN

WRITELN("Результат:");

FOR I:=1 TO N DO

END.

Фактически в пузырьковой сортировке нет ничего ценного, кроме ее привлекательного названия. Шейкерная же сортировка широко используется в тех случаях, когда известно, что элементы почти упорядочены – на практике это бывает весьма редко.

2.2. Улучшенные методы сортировки массивов.

2.2.1.Метод Шелла.

В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сначала отдельно сортируются и группируются элементы, отстоящие друг от друга на расстояние 4. Такой процесс называется четверной сортировкой. В нашем примере восемь элементов и каждая группа состоит из двух элементов. После первого прохода элементы перегруппировываются – теперь каждый элемент группы отстоит от другого на две позиции – и вновь сортируются. Это называется двойной сортировкой. На третьем подходе идет обычная или одинарная сортировка. На каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок.

ПРОГРАММА 2.6. СОРТИРОВКА ШЕЛЛА..

PROGRAMSHELLS;

H: ARRAY OF INTEGER = (15,7,3,1);

I,J,K,S,X,N,M:INTEGER;

A:ARRAY[-16..50] OF INTEGER;

WRITELN("Введи длину массива");

WRITELN("Введи массив");

FOR I:=1 TO N DO

FOR M:=1 TO T DO

FOR I:=K+1 TO N DO

IF S=0 THEN S:=-K;

WRITELN("Результат:");

FOR I:=1 TO N DO

Анализ сортировки Шелла. Нам не известно, какие расстояния дают наилучший результат. Но они не должны быть множителями один другого. Справедлива такая теорема: если k-отсортированную последовательность i-отсортировать, то она остается k-отсортированной. Кнут показывает, что имеет смысл использовать такую последовательность, в которой hk-1 = 3 hk + 1, ht = 1 и t = [ log2 n] – 1. (2.19.)

2.2.2.Сортировка с помощью дерева .

Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди n-1 оставшихся элементов и т. д. Как же усовершенствовать упомянутый метод сортировки? Этого можно добиться, действуя согласно следующим этапам сортировки:

1. Оставлять после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Проделав n-1 сравнений, мы можем построить дерево выбора вроде представленного на рисунке 2.1.

44 12 18 06

44 55 12 42 94 18 06 67

РИСУНОК 2.1. ПОВТОРЯЮЩИЙСЯ ВЫБОР СРЕДИ ДВУХ КЛЮЧЕЙ.

2. Спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путем замены либо на пустой элемент в самом низу, либо на элемент из соседний ветви в промежуточных вершинах (см. рисунки 2.2 и 2.3.).

Д. Уилльямсом был изобретен метод Heapsort, в котором было получено существенное улучшение традиционных сортировок с помощью деревьев. Пирамида определяется как последовательность ключей a[ L], a[ L+1], … , a[ R], такая, что a[ i] a и a[ i] a для i= L… R/2.

Р. Флойдом был предложен некий “лаконичный” способ построения пирамиды на ”том же месте”. Здесь a … a[ n] – некий массив, причем a[ m]… a[ n] (m = [ nDIV 2] + 1) уже образуют пирамиду, поскольку индексов i и j, удовлетворяющих соотношению j = 2 i (или j = 2 i + 1), просто не существует.

44 12 18

44 55 12 42 94 18 67

РИСУНОК 2.2.ВЫБОР НАИМЕНЬШЕГО КЛЮЧА.

12 18

44 12 18 67

44 55 12 42 94 18 67

РИСУНОК 2.3. ЗАПОЛНЕНИЕ ДЫРОК.

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

РИСУНОК 2.4.МАССИВ , ПРЕДСТАВЛЕННЫЙ В ВИДЕ ДВОИЧНОГО ДЕРЕВА .

ПРОГРАММА 2.7. HEARSORT.

I,X,L,N,R:INTEGER;

A:ARRAY OF INTEGER;

PROCEDURE SIFT(L,R: INTEGER);

WRITELN("Введи длину массива");

WRITELN("Введи массив");

FOR I:=1 TO N DO

WRITELN(‘Результат:");

FOR I:=1 TO N DO

END.

Анализ Heapsort. Heapsort очень эффективна для большого числа элементов n; чем больше n, тем лучше она работает.

В худшем случае нужно n/2 сдвигающих шагов, они сдвигают элементы на log(n/2), log(n/2 – 1), … , log(n – 1) позиций (логарифм по [основанию 2] «обрубается» до следующего меньшего целого). Следовательно фаза сортировки будет n – 1 сдвигов с самое большое log(n-1), log(n-2), … , 1 перемещениями. Можно сделать вывод, что даже в самом плохом из возможных случаев Heapsort потребуется n* logn шагов. Великолепная производительность в таких случаях – одно из привлекательных свойств Heapsort.

2.2.3. Сортировка с помощью разделения .

Этот улучшенный метод сортировки основан на обмене. Это самый лучший из всех известных на данный момент методов сортировки массивов. Его производительность столь впечатляюща, что изобретатель Ч. Хоар назвал этот метод быстрой сортировкой ( Quicksort) . В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, что у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно сдвигаться с двух сторон. Это возможно в том случае, когда мы знаем, что порядок действительно обратный. Однако полученный при этом алгоритм может оказаться и не удачным, что, например, происходит в случае n идентичных ключей: для разделения нужно n/2 обменов. Этих необязательных обменов можно избежать, если операторы просмотра заменить на такие:

В этом случае x не работает как барьер для двух просмотров. В результате просмотры массива со всеми идентичными ключами приведут к переходу через границы массива.

Наша цель – не только провести разделение на части исходного массива элементов, но и отсортировать его. Будем применять процесс разделения к получившимся двум частям, до тех пор, пока каждая из частей не будет состоять из одного-единственного элемента. Эти действия описываются в программе 2.8.

ПРОГРАММА 2.8. QUICKSORT.

A:ARRAY OF INTEGER;

PROCEDURE SORT(L,R: INTEGER);

I,J,X,W: INTEGER;

X:=A[(L+R) DIV 2];

WRITELN("Введи длину массива");

WRITELN("Введи массив");

FOR I:=1 TO N DO READ(A[I]);

WRITELN("Результат:");

FOR I:=1 TO N DO

END.

Анализ Quicksort. Процесс разделения идет следующим образом: выбрав некоторое граничное значение x, мы затем проходим целиком по всему массиву. При этом выполняется точно n сравнений. Ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x.

N*(n-1)/2n-(2n2-3n+1)/6n = (n-1/n)/6 (2.20.)

В том случае, если бы нам всегда удавалось выбирать в качестве границы медиану, то каждый процесс разделения расщеплял бы массив на две половинки, и для сортировки требовалось бы всего n* logn подходов. В результате общее число сравнений было бы равно n* logn, а общее число обменов – n* log(n) /6. Но вероятность этого составляет только 1/ n.

Главный из недостатков Quicksort – недостаточно высокая производительность при небольших n, впрочем этим грешат все усовершенствованные методы, одним из достоинств является то, что для обработки небольших частей в него можно легко включить какой-либо из прямых методов сортировки.

Тесты .

Идея сортировки массива прямым включением заключается в том, что

в сортируемой последовательности masi длиной n (i = 0..n - 1) последовательно выбираются элементы начиная со второго (i
в сортируемой последовательности masi длиной n (i=0..n-1) последовательно выбираются элементы начиная со первого (i
в сортируемой последовательности masi длиной n (i=0..n-1) последовательно выбираются элементы начиная со второго (i
в сортируемой последовательности masi длиной n-1 (i=0..n-1) последовательно выбираются элементы начиная со второго (i

При сортировке массива прямым включением поиск места включения очередного элемента х в левой части последовательности mas может закончиться двумя ситуациями:

найден элемент последовательности mas, для которого masi>x; достигнут левый конец отсортированной слева последовательности.

найден элемент последовательности mas, для которого masi
найден элемент последовательности mas, для которого masi

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

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

Сортировка массива прямым включением требует в среднем

N^2/2 перемещений.
N^2/4 перемещений.
N^2 перемещений.
N/4 перемещений.

Выберите правильный вариант для вставки вместо знака «вопрос» во фрагмент кода сортировки массива прямым включением:

For i:=2 to С ount do

Begin

Tmp:=Arr [i];

j:=i -1;

Begin

Arr :=Arr[j];

j:=j -1;

End ;

Arr :=Tmp;

End ;

While (j0) and (Arr[j] ) do

While (j>0) and (Arr[j]>Tmp) do

While (j> 0 ) and (Arr [ j ] ) do

While (j=0) and (Arr[j]=Tmp) do

Алгоритм сортировки массива бинарными включениями

вставляет i - й элемент в готовую последовательность, которая пока не отсортирована, для нахождения места для i - го
вставляет i - й i - го элемента используется метод бинарного поиска элемента.
вставляет i - й элемент в готовую последовательность, которая уже отсортирована, для нахождения места для i - го
вставляет i - й элемент в пока готовую последовательность, которая пока не отсортирована, для нахождения места для i - го элемента используется метод Шелла поиска элемента.

При сортировке массива бинарными включениями всего будет произведено

N log 2 N сравнений.
 log 2 N сравнений.
log 2 (N/ 2 ) сравнений.
N /2*log 2 N сравнений.

Изменится ли количество пересылок в сортировке массива бинарными включениями по отношению к количеству сравнений

станет больше
станет меньше
не изменится.

При сортировке массива методом бинарного включения внутренний цикл поиска с одновременным сдвигом следует разделить:

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

В чем состоит идея сортировки массива методом Шелла?

сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии большем h.
сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии меньшем h.
сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии h.
сортировке подвергаются не все подряд элементы последовательности, а только h элементов.

При сортировке массива методом Шелла на каждом шаге значение h изменяется, пока не станет (обязательно) равно

Если h=1, то алгоритм сортировки массива методом Шелла вырождается в
1. пирамидальную сортировку.
  сортировку прямыми включениями.
  сортировку слиянием.
  сортировку бинарного включения.

При сортировке массива методом Шелла расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что

последний шаг должен равняться единице.
последний шаг должен равняться нулю.
первый элемент равен последнему элементу.
первый элемент равен предпоследнему элементу.

Эффективность сортировки массива методом Шелла объясняется тем, что

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

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

Идея алгоритма сортировки массива прямым выбором заключается в том, что

на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной максимальный элемент. Если он найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он не найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он найден, то производится его перемещение на место крайнего правого элемента несортированной левой части массива.
на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.

Если сортировку выбором применить для массива "bdac", то будут получены следующие проходы

первый проход: c d b a; второй проход: a b b c; третий проход: a b c d.
d c; третий проход: a b c d.
первый проход: a d b c; второй проход: a cdb; третий проход: a b c d.
первый проход: a d b c; второй проход: a b d c; третий проход: d b c a.

Как и в сортировке массива пузырьковым методом в сортировке массива прямым выбором внешний цикл

выполняется n раз, а внутренний цикл выполняется n/2 раз.
выполняется n-1 раз, а внутренний цикл выполняется n раз.
выполняется n-1 раз, а внутренний цикл выполняется n/2 раз.
выполняется n раз, а внутренний цикл выполняется n раз.

Вставить во фрагмент кода сортировки массива прямым выбором, вместо знака «вопроса», верное неравенство:

for i:= 1 to n - 1 do

begin

min:= i;

for j:= i + 1 to n do

if ? then

min:= j;

t:= a[i];

a[i] := a;

a := t

end;

a > a[j].

a[ min] a[ j].

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

Вставьте вместо знака «вопрос» верный вариант.

n-элементов.

(n-1)-элементов.

n/2-элементов.

2*n-элементов.

Алгоритм сортировки массива методом пирамидального выбора предназначен для сортировки последовательности чисел, которые

являются отображением в памяти дерева специальной структуры - пирамиды.
являются отображением в памяти дерева специальной структуры - дерева.
являются отображением в памяти пирамиды специальной структуры - пирамиды.
являются отображением в памяти куста специальной структуры - дерева.

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

Т4.

Пирамида, показанная на рисунке (одна из четырех), в памяти будет представлена следующим массивом:

3, 2, 7, 11, 5, 8, 14, 9, 27.

2, 3, 5, 7, 8, 9, 11, 14, 27.

27, 14, 11, 9, 8, 7, 5, 3, 2.

27, 9, 14, 8, 5, 11, 7, 2, 3.

На каждом из n шагов, требуемых для сортировки массива методом пирамидального выбора, нужно

n*log n (двоичных) сравнений.
(log n )/2 (двоичных) сравнений.
log n (двоичных) сравнений.
2 * log n (двоичных) сравнений.

Идея алгоритма сортировки массива прямым обменом заключается в том, что

если номер позиции большего из элементов больше номера позиции меньшего элемента, то меняем их местами.
если номер позиции меньшего из элементов больше номера позиции большего элемента, то не меняем их местами.
если номер позиции меньшего из элементов больше номера позиции большего элемента, то оставляем их на месте.
если номер позиции меньшего из элементов больше номера позиции большего элемента, то меняем их местами.

При использовании метода пузырьковой сортировки массива требуется самое большее

n проходов.
(n-1) проходов.
n /2 проходов.
2*n проходов.

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

таблица не отсортирована и требует дальнейших проходов.
таблица уже отсортирована и требует дальнейших проходов.
таблица уже отсортирована и дальнейших проходов не требуется.
таблица не отсортирована и дальнейших проходов не требуется.

Сортировка массива пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент

достигает своего места за один проход.
достигает своего места за два прохода.
достигает своего места за три прохода.
достигает своего места за N проходов.

Сортировка массива пузырьковым методом обладает одной особенностью: элемент, расположенный в начале массива

очень быстро достигает своего места.
очень медленно достигает своего места.
не достигает своего места.
достигает середины массива.

В основе метода внутренней сортировки массива лежит процедура слияния

двух упорядоченных таблиц.
одной упорядоченной таблицы.
трех упорядоченных таблиц.
двух неупорядоченных таблиц.

Сущность сортировки массива слиянием состоит в том, что упорядочиваемая таблица разделяется на равные группы элементов. Группы упорядочиваются, а затем

попарно сливаются, образуя три новые группы, содержащие втрое больше элементов.
попарно сливаются, образуя две новые группы, содержащие вдвое больше элементов.
попарно сливаются, образуя новые группы, содержащие втрое больше элементов.
попарно сливаются, образуя новые группы, содержащие вдвое больше элементов.

В предложенных тестах правильные ответы выделены курсивом.

Заключение .

В данной курсовой работе рассматриваются задачи сортировки, постановка задачи сортировки массивов. А также основная часть отведена рассмотрению методов: а именно, простые методы сортировки (сортировка с помощью прямого включения, сортировка с помощью прямого выбора, сортировка с помощью прямого обмена) и улученные методы сортировки массивов (метод Шелла, сортировка с помощью дерева, сортировка с помощью разделения). Предложен анализ к каждому из методов сортировки массивов. Разработаны тестовые задания по сортировкам массивов (30 заданий). http://ru.wikipedia.org

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

1.Алгоритм "Сортировка выбором".

Является одним из самых простых алгоритмов сортировки массива. Смысл в том, чтобы идти по массиву и каждый раз искать минимальный элемент массива, обменивая его с начальным элементом неотсортированной части массива. На небольших массивах может оказаться даже эффективнее, чем более сложные алгоритмы сортировки, но в любом случае проигрывает на больших массивах. Число обменов элементов по сравнению с "пузырьковым" алгоритмом N/2, где N - число элементов массива.

Алгоритм:
1. Находим минимальный элемент в массиве.
2. Меняем местами минимальный и первый элемент местами.
3. Опять ищем минимальный элемент в неотсортированной части массива
4. Меняем местами уже второй элемент массива и минимальный найденный, потому как первый элемент массива является отсортированной частью.
5. Ищем минимальные значения и меняем местами элементы,пока массив не будет отсортирован до конца.

//Сортировка выбором {--- Функция СортировкаВыбором(Знач Массив) Мин = 0; Для i = 0 По Массив.ВГраница() Цикл Мин = i; Для j = i + 1 ПО Массив.ВГраница() Цикл //Ищем минимальный элемент в массиве Если Массив[j] < Массив[Мин] Тогда Мин = j; КонецЕсли; КонецЦикла; Если Массив [Мин] = Массив [i] Тогда //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем. Продолжить; КонецЕсли; Смена = Массив[i]; //Производим замену элементов массива. Массив[i] = Массив[Мин]; Массив[Мин] = Смена; КонецЦикла; Возврат Массив; КонецФункции

2.Алгоритм "Сортировка пузырьком".

Пожалуй самый известный алгоритм, применяемый в учебных целях, для практического же применения является слишком медленным. Алгоритм лежит в основе более сложных алгоритмов: "Шейкерная сортировка", "Пирамидальная сортировка", "Быстрая сортировка". Примечательно то, что один из самых быстрых алгоритмов "Быстрый алгоритм" был разработан путем модернизации одного из самых худших алгоритмов "Сортировки пузырьком"."Быстрая" и "Шейкерная" сортировки будут рассмотрены далее. Смысл алгоритма заключается в том, что самые "легкие" элементы массива как бы "всплывают" , а самые "тяжелые" "тонут". Отсюда и название "Сортировка пузырьком"

Алгоритм:
1. Каждый элемент массива сравнивается с последующим и если элемент[i] > элемент происходит замена. Таким образом самые "легкие" элементы "всплывают" - перемещаются к началу списка,а самые тяжелые "тонут" - перемещаются к концу.
2. Повторяем Шаг 1 n-1 раз, где n - Массив.Количество ().

//Сортировка пузырьком {--- Функция СортировкаПузырьком(Знач Массив) Для i = 0 По Массив.ВГраница() Цикл Для j = 0 ПО Массив.Вграница() - i - 1 Цикл Если Массив[j] > Массив Тогда Замена = Массив[j]; Массив[j] = Массив; Массив = Замена; КонецЕсли; КонецЦикла; КонецЦикла; Возврат Массив; КонецФункции //---}

3.Алгоритм "Шейкерная сортировка"(Сортировка перемешиванием,Двунаправленная пузырьковая сортировка).

Алгоритм представляет собой одну из версий предыдущей сортировки - "сортировки пузырьком". Главное отличие в том, что в классической сортировке пузырьком происходит однонаправленное движение элементов снизу - вверх, то в шейкерной сортировке сначало происходит движение снизу-вверху, а затем сверху-вниз.

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

В приведенном ниже примере, есть усовершенствование в шейкерной сортировке. В отличие от классической, используется в 2 раза меньше итераций.

//Сортировка перемешивание (Шейкер-Сортировка) {--- Функция СортировкаПеремешиванием(Знач Массив) Для i = 0 ПО Массив.ВГраница()/2 Цикл нИтер = 0; конИтер = Массив.ВГраница(); Пока нИтер Массив[нИтер+1] Тогда Замена = Массив[нИтер]; Массив[нИтер] = Массив[нИтер + 1]; Массив[нИтер + 1] = Замена; КонецЕсли; нИтер = нИтер + 1;//Двигаем позицию на шаг вперед //Проходим с конца Если Массив[конИтер - 1] > Массив[конИтер] Тогда Замена = Массив[конИтер - 1]; Массив[конИтер-1] = Массив[конИтер]; Массив[конИтер] = Замена; КонецЕсли; конИтер = конИтер - 1;//Двигаем позицию на шаг назад КонецЦикла; КонецЦикла; Возврат Массив; КонецФункции //---}

4. Алгоритм "Гномья сортировка".

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

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

Вот собственно и все описание алгоритма "Гномья сортировка". Что интересно, алгоритм не содержит вложенных циклов, а сортирует весь массив за один проход.

//Гномья сортировка {--- Функция ГномьяСортировка(Знач Массив) i = 1; j = 2; Пока i < Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, > - по убыванию Если Массив i = j; j = j + 1; Иначе Замена = Массив[i]; Массив[i] = Массив; Массив = Замена; i = i - 1; Если i = 0 Тогда i = j; j = j + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат Массив; КонецФункции //---}

5. Алгоритм "Сортировка вставками".

Представляет собой простой алгоритм сортировки. Смысл заключается в том, что на каждом шаге мы берем элемент, ищем для него позицию и вставляем в нужное место.
Элементарный пример: При игре в дурака, вы тянете из колоды карту и вставляете ее в соответствующее место по возрастанию в имеющихся у вас картах. Или
в магазине вам дали сдачу 550 рублей- одна купюра 500, другая 50. Заглядываете в кошелек, а там купюры достоинством 10,100,1000. Вы вставляете купюру
достоинсвом 50р. между купюрами достоинством 10р и 100р, а купюру в 500 рублей между купюрами 100р и 1000р. Получается 10,50,100,500,1000 - Вот вам
и алгоритм "Сортировка вставками".
Таким образом с каждым шагом алгоритма, вам необходимо отсортировать подмассив данных и вставить значение в нужное место.

//Сортировка вставками {--- Функция СортировкаВставками(Знач Массив) Для i = 0 По Массив.ВГраница()-1 Цикл Ключ = i + 1; Замена = Массив[Ключ]; j = i + 1; Пока j > 0 И Замена < Массив Цикл Массив[j] = Массив; Замена = j - 1; Ключ = j - 1; j = j - 1; КонецЦикла; Массив[Ключ] = Замена; КонецЦикла; Возврат Массив; КонецФункции //---}

6. Алгортим "Сортировка слиянием".

Интересный в плане реализации и идеи алгоритм. Смысл его в том, чтобы разбивать массив на подмассивы, пока длина каждого подмассива не будет равна 1. Тогда мы утверждаем, что такой подмассив отсортирован. Затем сливаем получившиеся подмассивы воедино, одновременно сравнивая и сортируя поэлементно значения подмассивов.

p/s не смог вставить сюда рисунок с более наглядной схемой, постоянно размазывается. Зато хорошо видна в блоке скриншотов внизу. Можно посмотреть как работает алгоритм.

//Сортировка слиянием {---

Функция СортировкаСлиянием(Знач Массив) Если Массив.Количество() = 1 Тогда Возврат Массив; КонецЕсли; ТочкаРазрыв = Массив.Количество() / 2; лМассив = Новый Массив; прМассив = Новый Массив; Для Сч = 0 ПО Массив.ВГраница() Цикл Если Сч < ТочкаРазрыв Тогда лМассив.Добавить(Массив[Сч]); Иначе прМассив.Добавить(Массив[Сч]); КонецЕсли; КонецЦикла; Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив)); КонецФункции Функция Слияние(массив1,массив2) a = 0; b = 0; слМассив = Новый Массив; Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл слМассив.Добавить(); КонецЦикла; Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл Если b < массив2.Количество() И a < массив1.Количество() Тогда Если (массив1[a] > массив2[b]) И (b < массив2.Количество()) Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; Иначе Если b < массив2.количество() Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат слМассив; КонецФункции //---}

7. Алгортим "Сортировка Шелла".

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

Пример:
Дан массив (10,5,3,1,14,2,7,12).
1. Шаг = 4.
Сортируем простыми вставками каждые 4 группы по 2 элемента (10,14)(5,2)(3,7)(1,12)

10 ,2 ,3 ,1,14 ,5 ,7 ,12

2. Шаг = 2
Сортируем простыми вставками каждые 2 группы по 4 элемента (10,3,14,7)(2,1,5,12)

3 ,1 ,7 ,2 ,10 ,5 ,14 ,12

3. Шаг = 1
Сортируем простыми вставками каждую 1 группу по 8 элементов.

1,2,3,5,7,10,12,14

//Сортировка Шелла {--- Функция СортировкаШелла(Знач Массив) Шаг = Цел(Массив.Количество()/2); Пока Шаг > 0 Цикл i = 0; Пока i < (Массив.Количество() - Шаг) Цикл j = i; Пока j >= 0 И Массив[j] > Массив Цикл Замена = Массив[j]; Массив[j] = Массив; Массив = Замена; j = j - 1; Если ПрименитьОтображениеСортировки Тогда ОтобразитьДиаграммуСортировки(Массив); КонецЕсли; КонецЦикла; i = i + 1; КонецЦикла; Шаг = Цел(Шаг/2); ОбработкаПрерыванияПользователя(); КонецЦикла; Возврат Массив; КонецФункции //---}

8. Алгортим "Быстрая сортировка".

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

//Алгоритм "Быстрая сортировка" { Процедура б_Сортировка(Массив,НижнийПредел,ВерхнийПредел) i = НижнийПредел; j = ВерхнийПредел; m = Массив[Цел((i+j)/2)]; Пока Истина Цикл Пока Массив[i] < m Цикл i = i + 1; КонецЦикла; Пока Массив[j] > m Цикл j = j - 1; КонецЦикла; Если i > j Тогда Прервать; КонецЕсли; КонецЦикла; Если НижнийПредел < j Тогда б_Сортировка(Массив,НижнийПредел,j); КонецЕсли; Если i < ВерхнийПредел Тогда б_Сортировка(Массив,i,ВерхнийПредел); КонецЕсли; КонецПроцедуры Функция БыстраяСортировка(Массив) НижняяГраница = 0; ВерхняяГраница = Массив.ВГраница(); б_Сортировка(Массив,НижняяГраница,ВерхняяГраница); Возврат Массив; КонецФункции //---}

9. Классическая сортировка массива в 1с.

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

//Сортировка списком значений {--- Функция СортировкаСпискомЗначений(Знач Массив) мСписокЗнч = Новый СписокЗначений; мСписокЗнч.ЗагрузитьЗначения(Массив); мСписокЗнч.СортироватьПоЗначению(НаправлениеСортировки.Возр); Возврат мСписокЗнч.ВыгрузитьЗначения(); КонецФункции //---}

Все сортировки можно ускорить расположив код в циклах в 1 строку. Но для читабельности, оставил так.

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

-При запуске обработки автоматически происходит формирование массива случайных чисел от 0 до 100 размерностью 100 элементов.
-Для создания другого массива необходимо нажать на кнопку "Создание ГСЧ массива ", также можно выбирать необходимый диапазон.
-Для включения динамической анимации необходимо поставить галочку на "Отобразить сортировку в диаграмме". Советую на неэффективных алгоритмах устанавливать галочку при размерности массива до 100 элементов, иначе состаритесь ждать сортировки:)

Динамическая отрисовка процесса сортировки очень сильно снижает производительность, зато наглядно видно как работает алгоритм.