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

Продолжить читать "Быстрая сортировка Хоара"

Аналогичен методу пузырька, но просмотры с обменами производятся попеременно то в сторону возрастания то в сторону убывания. Соответственно потребуется две переменные – левая и правая границы. При просмотре в большую сторону меняется правая граница, в меньшую сторону – левая.

Продолжить читать "Сортировка. Метод “шейкера”"

Есть массив B не упорядоченный длиной N, требуется его отсортировать не заводя дополнительных массивов.

i – счетчик

M – расматриваемая часть массива ,  M:=N-1

Несколько раз подряд просматриваем массив В от 0 до M-1 . Для каждого i сравниваем B[i] и B[i+1]. Если они стоят не в нужном порядке, то меняем их местами и к:=i (k – место последнего обмена).  к+1 занял свое место, M:=k; перед каждым просмотром к:=0. Просмотры повторяются до тех пор пока M>0/

Достоинство метода: не требуется дополнительных массивов.

Недостаток: время алгоритма пропорционально квадрату количества элементов.

Продолжить читать "Сортировка. Метод пузырька"

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

Продолжить читать "Сортировка. Вставка в список"

Этот метод аналогичен сортировке простыми вставками, но совмещает два процесса: поиск места вставки и раздвижение элементов.

Алгоритм: Добавляем элемент в конец отсортированного массива и начинаем добавленый элемент менять местами с предыдущим до тех пор пока предыдущий не окажется меньшим или равным ему.

Продолжить читать "Сортировка. Метод погружения"

Требуется два массива: исходный(А), хранящий не отсортированные элементы; выходной(В), уже отсортированный массив.

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

k – количество заполненных элементов в выходном массиве

i  – очередной элемент исходного массива

Сравниваем A[i] с B[j]  ( j=1..k ), пока не найдется A[i]<B[j] или j=k+1. Если больших элементов не было, то добавляем элемент место k+1 и k увеличиваем.

Смещение от k до j

for (l=k; l>=j; l–)

B[l+1]=B[l];

На B[j] место помещаем A[i]

Продолжить читать "Сортировка простыми вставками"

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

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

Продолжить читать "Сортировка вставками"

Идея метода: найти для каждого элемента массива R его номер, который он будет занимать в отсортированом массиве.

Нумеровать будем с нуля, номером элемента может являться количество элементов меньших его. Для того  чтобы найти все номера заводим массив, элементами которого будут номера массива R. Обнуляем этот массив и начинаем сравнивать все элементы со всеми. Если i элемент больше j, то элемент массива Number увеличиваем на 1. После того как все элементы массива R сравним, то в массиве Number будут их номера. Остается упорядочить массив в соответствии с номерами.

Продолжить читать "Сортировка. Метод подсчета"