Сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька (стр. 2 из 5)
сравнений, где N - число элементов, а С - число необходимых сравнений.
Мы рассмотрим простые методы сортировки, которые требуют число сравнений порядка
Методы сортировки "на месте" можно разбить на три основных класса:
сортировка выбором
сортировка вставками
сортировка обменом
В сортировке выбором выбирается элемент с наибольшим значением ключа и меняется местами с последним. Затем то же самое повторяется для s-1 элемента. Найденный элемент с наибольшим значением ключа меняется
 |
местами предпоследним элементом и т.д. (рисунок 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)
Получаем, что при сортировке простым выбором и число сравнений, и число пересылок пропорционально
. 2.1 Сортировка массива простыми включениями
Метод простых вставок предполагает разделение всего массива элементов на упорядоченную часть, которая вначале содержит лишь один элемент, и неупорядоченную. Очередной элемент из неупорядоченной части вставляется в определенное место упорядоченной части, проходя сравнение с ее элементами. При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы "просеивать" выбранный элемент, сравнивая его с очередным элементом a [j] и либо вставляя, либо пересылая a [i] направо и продвигаясь налево. Заметим, что "просеивание" может закончиться при двух различных условиях: найден элемент a [j] с ключом меньшим, чем ключ x или достигнут левый конец готовой последовательности.
При этом упорядоченная часть удлиняется на один элемент. Сортировка заканчивается при окончании неупорядоченной части.
При данной сортировке общее число сравнений приблизительно равно
, 
При этом требуется количество проходов по данным P
 |
Рассмотрим пошагово сортировку методом простых вставок на рис.5
Рисунок 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], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения.
2.2 Сортировка массива простым обменом ("метод пузырька")
Данный алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы массива. Пример сортировки методом "пузырька" приведен на рисунке 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.
Следовательно,
2.3 Сортировка массива сложным выбором (с помощью двоичного дерева)
Метод сортировки основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Понятно, что поиск наименьшего ключа из n элементов требует n-1 сравнений, а поиск его среди n-1 элементов n-2 сравнений. Улучшить сортировку выбором можно в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью n/2 сравнений можно определить наименьший ключ из каждой пары, при помощи следующих n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т.д. Наконец при помощи всего n-1 сравнений мы можем построить дерево, как показано на рис.1, выбора и определит корень, как наименьший ключ. На втором шаге мы спускаемся по пути, указанном наименьшим ключом, и исключаем его, последовательно заменяя либо на "дыру" (или ключ бесконечность), либо на элемент, находящийся на противоположной ветви промежуточного узла Элемент оказывается в корне дерева, вновь имеет наименьший ключ среди оставшихся и может быть исключен. После n таких шагов дерево становится пустым (т.е. состоит из "дыр"), и процесс сортировки закончен.
При сортировке с помощью дерева задача хранения информации стала сложнее и поэтому увеличилась сложность отдельных шагов; в конечном счете, для хранения возросшего объема информации нужно строить некую древовидную структуру. Также желательно избавиться от необходимости в дырах, которые в конце заполняют дерево и приводят к большому числу ненужных сравнений. Механизм сортировки методом бинарного дерева отображен на рисунке 7.
Рисунок 7. Сортировка бинарным деревом
2.4 Пирамидальная сортировка
Пирамида определяется как последовательность ключей
hl, hl+1,..., hr, такая, что hi <= h2i, hi <= h2i+1
для всякого i =l,...,r/2. Если двоичное дерево представлено в виде массива, как показано на рис.1, то, следовательно, деревья сортировки на рис.2 и 3 являются пирамидами, и, в частности, элемент h1 пирамиды является ее наименьшим элементом h1 = min (h1... hn).