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

Стандартный обмен (сортировка обменом, метод "пузырька")

Рассмотрим еще один метод сортировки, который основан на следующих принципах.

Пусть необходимо отсортировать массив по убыванию.

1. Сравниваем первые два элемента. Если первый меньше второго, то меняем их местами.

2. Сравниваем второй и третий, третий и четвертый, ..., предпоследний и последний, при необходимости меняя их местами. В конечном итоге наименьший окажется на последнем месте.

3. Снова просматриваем массив с его начала, уменьшив на единицу количество просматриваемых элементов (т.е. как раньше упорядоченную часть массива больше не рассматриваем).

4. Массив будет отсортирован после просмотра, в котором приняли участие только первый и второй элементы.

Начало цикла 1 (выполнять для i от 0 до N-1)

Начало цикла 2 (выполнять для j от 0 до N-1)

если a[j] > a[j+1]

тогда

x= a[j];

a[j]= a[j+1];

a[j+1]=x;

все

конец цикла 2

конец цикла 1

Оптимизируем алгоритм - можем запомнить, были или не были перестановки в процессе некоторого прохода, и если перестановок не было, то работу можно заканчивать. Ля этого воспользуемся «булевским принципом»: веем логическую переменную flag. для контроля: был обмен или нет и переменную i1 для запоминания индекса последнего обмена. Еще нужна одна переменная R – это будет граница, на которой заканчиваем просмотр:

flag = «истина»;

i1=N-1;

Начало цикла 1: выполнять пока flag = =«истина»;

flag = «ложь»;

R=i1;

Начало цикла 2(выполнять для j от 1 до R)

если a[j] > a[j+1]

тогда

x= a[j];

a[j]= a[j+1];

a[j+1]=x;

flag = «истина»;

i1=j;

все

конец цикла 2

конец цикла 1

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

Метод Хоара

Метод Хоара (Charles Antony Richard Hoare, разраотал агоритм в 1962 г.), называемый также методом быстрой сортировки (Quicksort) основывается на следующем: находится такой элемент, который разбивает множество на два подмножества так, что в одном все элементы больше, а в другом - меньше делящего. Каждое из подмножеств также разделяется на два, по такому же признаку. Конечным итогом такого разделения станет рассортированное множество.

Рассмотрим один из вариантов реализации сортировки Хоора.

Сначала выберем средний элемент. Потом, используя переменные i (цикл: i=0, i++) и j (цикл: j=n-1, j--), пройдем по массиву, отыскивая в левой части элементы больше среднего, а в правой - меньше среднего. Два найденных элемента переставим местами. Будем действовать так, пока i не станет больше (или равным) j. Тогда мы получим два подмножества, ограниченные с краев индексами l и r, а в середине - j и i. Если эти подмножества существуют (т.е. i<r и j>l), то теперь выполняем их сортировку по такому же алгоритму.

Словесный рекурсивный алгоритм Хоара

Просмотр и деление совокупности данных на два подмножества оформим рекурсивной функцией, в которую через список параметров будем передавать текущий массив, и его левую (left) и правую (right) границы.

Сортируем совокупность a[n], поэтому первое обращение к функции:

qs(a, 0, n-1);

Заголовок функции: void qs(int a[], int left, int right)

1. Инициализируем рабочие переменные границами массива:

i=left; j=right;

2. выбираем средний элемент:

t=a[(left+right)/2];