Сортировка бинарными вставками c

Сортировка бинарными вставками c

Начиная со 2-го элемента, каждый текущий элемент с номером i запоминается в промежуточной переменной.

Затем просматриваются предыдущие i–1 элемент и ищется место вставки i-го элемента таким образом, чтобы не нарушить упорядоченности, при этом все элементы, превышающие iй, сдвигаются вправо.

На освободившееся место вставляется i-й элемент.

Таблица 2. Пример сортировки прямыми включениями.

5

4

3

Программа сортировки вставками:

void sort_insert (int *m, int n)

for (int i=1;i =0 && m[j]>r) // Ищем новое место вставки,

< m[j+1]=m[j]; j—;>// сдвигая на 1 элемент вправо

m[j+1]=r; // На освободившееся место вставляется элемент

6. Сортировка бинарными вставками

Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1]. a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

Реализация алгоритма бинарными вставками:

void sort_bin_insert (int *a, int n) // Сортировка бинарными вставками

for (int i=1; i a[i])

x=a[i]; // x – включаемый элемент

left=0; // левая граница отсортированной части массива

right=i-1; // правая граница отсортированной части массива

sred = (left+right)/2; // sred – новая "середина" последовательности

if (a[sred] =left;j—) a[j+1]= a[j];

7. Сортировка методом простого выбора

Обычно применяется для массивов, не содержащих повторяющихся элементов.

1) выбрать максимальный элемент массива;

2) поменять его местами с последним элементом (после этого самый большой элемент будет стоять на своём месте);

3) повторить пункты 1-2 с оставшимися n–1 элементами.

Пример. Дан массив из пяти элементов: 5, 2, 7, 4, 6. Отсортировать по возрастанию методом простого выбора.

Читайте также:  Как сделать жесткую перезагрузку на айфон 8

Порядок сортировки показан в таблице Таблица 2. Сортировка массива по возрастанию методом простого выбора.

Таблица 2. Сортировка массива по возрастанию методом простого выбора.

1. для i от 2 до n если a[i-1]>a[i] то x:= a[i];

left:= 1; right:= i-1;

пока left если a[sred] то left:= sred+1 иначе right:= sred-1;

для j:= i-1 до left шаг -1 a[j+1]:= a[j];

Характеристики

Со сторожевым элементом (I)

C = 1/8 (n 2 + n — 2)

Со сторожевым элементом (II)

Сортировка Шелла

Сортирует элементы массива, отстоящие друг от друга на заданный интервал .

После того, как все элементы массива, отстоящие друг от друга на будут отсортированы, интервал изменяется по правилу H i +1 =( H i — 1)/2 для массивов, содержащих более 500 элементов и H i +1 =( H i -1)/3 для массивов, содержащих менее 500 элементов. За H 0 принимается число элементов массива. Метод заканчивает работу, когда становится меньше 1. Модификация сортировки вставками

Сортировка Шелла

Например, для массива из 7 элементов: 23 12 43 54 83 11 2 23 12 43 54 83 11 2 23 12 43 54 83 11 2 23 12 43 54 83 11 2 23 12 43 54 83 11 2 23 12 43 54 83 11 2 23 12 43 54 83 11 2 23 12 43 11 83 54 2 23 12 43 54 83 11 2 23 12 43 11 2 54 83

Так как обмены при первом проходе были, то шаг остается прежним:

23 12 43 11 2 54 83 23 12 43 11 2 54 83 23 12 43 11 2 54 83 23 11 43 12 2 54 83 23 11 43 12 2 54 83 23 11 2 12 43 54 83 23 11 2 12 43 54 83 23 11 2 12 43 54 83 23 11 2 12 43 54 83 23 11 2 12 43 54 83

Читайте также:  Terminal services configuration как открыть

Сортировка комбинированная

Комбинация пузырька и сортировки Шелла. На каждом шаге сравниваются значения отстоящие друг от друга на заданное значение шага H i +1 =8 H i /11 , но

такое сравнение происходит всего один раз. Как только значение смещения становится равным 1, выполняется сортировка до конца методом пузырька. За принимается число элементов массива.

Сортировка комбинированная

23 12 43 54 83 11 H i 0 =7 H 1 = (7*8)/11=5 23 12 43 54 83 11 2 11 12 43 54 83 23 2 11 12 43 54 83 23 2 11 2 43 54 83 23 12 H 2 = (5*8)/11=3

11 2 43 54 83 23 12 11 2 43 54 83 23 12 11 2 43 54 83 23 12 11 2 43 54 83 23 12 11 2 43 54 83 23 12 11 2 23 54 83 43 12 11 2 23 54 83 43 12 11 2 23 12 83 43 54 H 3 = (3*8)/11=2

11 2 23 12 83 43 54 11 2 23 12 83 43 54 11 2 23 12 83 43 54 11 2 23 12 83 43 54 11 2 23 12 83 43 54 11 2 23 12 83 43 54 11 2 23 12 83 43 54 11 2 23 12 83 43 54 11 2 23 12 83 43 54 11 2 23 12 54 43 83

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

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

  1. первая и вторая карта меньше третьей;
  2. первая и вторая карта больше третьей;
  3. первая карта уступает значением третьей, а вторая превосходит ее;
  4. первая карта превосходит значением третью карту, а вторая уступает ей.
Читайте также:  Установка связи с интернет

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

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

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

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

Ссылка на основную публикацию
Смарт часы что они умеют
В этой статье мы поговорим о том, для чего нужны умные часы, а также какими функциями они располагают чаще всего....
Сервер не поддерживает символы не ascii
Многие из нас пользуются замечательным FTP сервером FileZilla Server. Думаю, не я один столкнулся с проблемой некорректного отображения русских букв...
Сервера для обновления nod32 бесплатно
Отличие полной версии от триальной Полные (не триальные) антивирусные базы и программные компоненты Eset Antivirus и Eset Smart Security! Отличия...
Смарт часы самсунг с сим картой
Хотите быть современным и модным человеком? Перестать зависеть от своего громоздкого смартфона? Только представьте, вы можете не брать телефон на...
Adblock detector