сравнений, где N - число элементов, а С - число необходимых сравнений.
Мы рассмотрим простые методы сортировки, которые требуют число сравнений порядка
Методы сортировки "на месте" можно разбить на три основных класса:
сортировка выбором
сортировка вставками
сортировка обменом
В сортировке выбором выбирается элемент с наибольшим значением ключа и меняется местами с последним. Затем то же самое повторяется для s-1 элемента. Найденный элемент с наибольшим значением ключа меняется
Рисунок 1. Сортировка простым выбором
В сортировке включениями элементы разделяются на уже упорядоченную и неупорядоченную последовательности. В начале упорядоченная часть содержит только один элемент. Очередной элемент из начала неупорядоченной части вставляется на подходящее место в упорядоченную часть. При этом упорядоченная часть удлиняется на один элемент, а неупорядоченная - укорачивается. Сортировка заканчивается при исчезновении неупорядоченной части (рисунок 2).
Рисунок 2. Сортировка простыми включениями
Основная характеристика сортировки обменом - перестановка местами двух соседних элементов, если они расположены не так, как требует отсортированный массив.
Рисунок 3. Сортировка простым обменом
В рассмотренной классификации существуют разные алгоритмы. Они отличаются сложностью, быстротой выполнения, последовательностью операций.
Например:
сортировка вставками;
пузырьковая сортировка;
корневая сортировка;
пирамидальная сортировка;
сортировка слиянием;
быстрая сортировка;
сортировка Шелла и др.
Рассмотрим подробнее основные типы и виды сортировок (сначала простые сортировки затем более сложные).
Сортировка массива простым выбором
Метод основан на следующем правиле:
Выбирается элемент с наибольшим значением ключа
Он меняется местами с последним элементом arr [s-1]. Затем эти операции повторяются с оставшимися первыми s-1 элементами, затем - с s-2 первыми элементами и т.д. до тех пор, пока не останется только первый элемент - наименьший. Пример сортировки методом простого выбора показан на рисунке 4:
Рисунок 4. Сортировка массива простым выбором
Эффективность сортировки простым выбором. Число сравнений ключей не зависит от начального порядка ключей. Операция сравнения выполняется в теле цикла с управляющей переменной k и средним числом повторений size/2. Этот цикл, в свою очередь, находится в теле цикла с управляющей переменной L и числом повторений size −1. Таким образом, число сравнений
С= (size −1) * size −1/2
Число пересылок, напротив, зависит от начального порядка ключей. Если принять, что операция сравнения в теле цикла по k дает результат "истина" в половине случаев, то среднее число пересылок в этом цикле равно size/4. Цикл по L, как указывалось выше, выполняется size −1 раз и в теле цикла выполняется три пересылки и цикл по k. С учетом этого число пересылок:
М= (3+ size/4) * (size −1)
Получаем, что при сортировке простым выбором и число сравнений, и число пересылок пропорционально
.Метод простых вставок предполагает разделение всего массива элементов на упорядоченную часть, которая вначале содержит лишь один элемент, и неупорядоченную. Очередной элемент из неупорядоченной части вставляется в определенное место упорядоченной части, проходя сравнение с ее элементами. При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы "просеивать" выбранный элемент, сравнивая его с очередным элементом a [j] и либо вставляя, либо пересылая a [i] направо и продвигаясь налево. Заметим, что "просеивание" может закончиться при двух различных условиях: найден элемент a [j] с ключом меньшим, чем ключ x или достигнут левый конец готовой последовательности.
При этом упорядоченная часть удлиняется на один элемент. Сортировка заканчивается при окончании неупорядоченной части.
При данной сортировке общее число сравнений приблизительно равно
,При этом требуется количество проходов по данным P
Рисунок 5. Пример сортировки массива простыми включениями
Число Ci сравнений ключей при i-м просеивании составляет самое большее i-1, самое меньшее 1 и, если предположить, что все перестановки n ключей равновероятны, в среднем равно i/2. Число Мi пересылок (присваиваний) равно Ci+2 (учитывая барьер). Поэтому общее число сравнений и пересылок есть
Cmin = n-1 Mmin = 2 (n-1)
Cср. = (n2+n-2) /4 Mср. = (n2+9n-10) /4
Cmax = ( (n2+n) - 1) /2 Mmax = (n2+3n-4) /2.
Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a [1],…, a [i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения.
Данный алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы массива. Пример сортировки методом "пузырька" приведен на рисунке 6.
Очевидно, что в наихудшем случае, когда минимальное значение ключа элемента имеется у самого правого элемента, число просмотров равно size −1.
12 44 18 55
12 42 44 18 06 55 67 94
18 44
06 44
12 42 18 06 44 55 67 94
18 42
06 42
12 18 06 42 44 55 67 94
06 18
12 06 18 42 44 55 67 94
06 12
06 12 18 42 44 55 67 94
Рисунок 6. Пример сортировки массива простым обменом
Эффективность сортировки. За один проход среднее число сравнений равно С=size/2. При этом среднее число возможных пересылок М=1.5*С (в предположении, что проверяемое условие выполняется в половине случаев). Минимальное количество проходов равно1, максимальное − size -1, а среднее − size/2.
Следовательно,
Метод сортировки основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Понятно, что поиск наименьшего ключа из n элементов требует n-1 сравнений, а поиск его среди n-1 элементов n-2 сравнений. Улучшить сортировку выбором можно в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью n/2 сравнений можно определить наименьший ключ из каждой пары, при помощи следующих n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т.д. Наконец при помощи всего n-1 сравнений мы можем построить дерево, как показано на рис.1, выбора и определит корень, как наименьший ключ. На втором шаге мы спускаемся по пути, указанном наименьшим ключом, и исключаем его, последовательно заменяя либо на "дыру" (или ключ бесконечность), либо на элемент, находящийся на противоположной ветви промежуточного узла Элемент оказывается в корне дерева, вновь имеет наименьший ключ среди оставшихся и может быть исключен. После n таких шагов дерево становится пустым (т.е. состоит из "дыр"), и процесс сортировки закончен.
При сортировке с помощью дерева задача хранения информации стала сложнее и поэтому увеличилась сложность отдельных шагов; в конечном счете, для хранения возросшего объема информации нужно строить некую древовидную структуру. Также желательно избавиться от необходимости в дырах, которые в конце заполняют дерево и приводят к большому числу ненужных сравнений. Механизм сортировки методом бинарного дерева отображен на рисунке 7.
Рисунок 7. Сортировка бинарным деревом
Пирамида определяется как последовательность ключей
hl, hl+1,..., hr, такая, что hi <= h2i, hi <= h2i+1
для всякого i =l,...,r/2. Если двоичное дерево представлено в виде массива, как показано на рис.1, то, следовательно, деревья сортировки на рис.2 и 3 являются пирамидами, и, в частности, элемент h1 пирамиды является ее наименьшим элементом h1 = min (h1... hn).