4. Простая сортировка вставками

На этапе j имя x_j вставляется на свое правильное место среди x₁, x₂, …, x_n. При вставке x_j временно размещается в ячейке X и просматриваются имена x_j-1, x_j-2, …, x₁. Они сравниваются с Х и сдвигаются вправо, если обнаруживается, что они больше Х. Имеется фиктивное имя x₀, значение которого – служит для остановки просмотра слева.

	x0  –  for j = 2 to n do			i  j – 1 X  xj while X < xi do xi+1  X		xi+1  xi i  i – 1
x0		x1	x2		x3		x4	x5
– 		8	7		2		4	6	j=2
– 		7	8		2		4	6	j=3
– 		2	7		8		4	6	j=4
– 		2	4		7		8	6	j=5
– 		2	4		6		7	8

Рис. 3.4. Простая сортировка вставками для пяти имен.

Пунктирные вертикальные линии разделяют уже отсортированную часть таблицы от еще не отсортированной.

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

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <conio.h>

int main ()

{

int A[20],i,n;

cout<<"Enter size A[] , n= ";

cin>>n;

cout<<"\n Enter elements: \n";

for(i=0;i<n;i++) cin>>A[i];

int zm; // для выноса элемента

int ip; // индекс предыдущего элемента

for (i = 1; i < n; i++)

// цикл по числам и каждому числу ищется свое место, т.е.это прогоны

{

zm = A[i];

ip = i-1; // предыдущее место

while(ip >= 0 && A[ip] > zm)

// пока индекс не равен 0 и предыдущий элемент массива больше текущего

{

A[ip + 1] = A[ip]; // перестановка элементов массива

A[ip] = zm;

ip--;

}

cout<<"\n Work array: \n"; // отладочная печать

for(int v=0; v<n; v++) cout<<A[v]<<" ";

}

cout<<"\n Resultat: \n";

for(i=0;i<n;i++) cout<<A[i]<<" ";

_getch();

return 0;

}

5. Быстрая сортировка Хоара. Сортировка методом пузырька

Основная идея, на которой базируется метод быстрой сортировки Хоара, состоит в том, чтобы взять одну из записей, скажем R₁, и передвинуть ее на то место, которое она должна занять после сортировки, скажем в позицию S.

В поиске этой окончательной позиции придется несколько перекомпоновать и остальные записи таким образом, чтобы слева от позиции S не оказалось ни одной записи с большим ключом, а с права — с меньшим. В результате последовательность окажется разбитой таким образом, что исходная задача сортировки всего массива записей будет сведена к задачам независимой сортировки пары массивов R₁… R_s-1 и R_s+1… R_N меньшей длины.

Предположим, что нам даны n элементов. Их нужно рассортировать по возрастанию. Выберем средний элемент. Обозначим его через Х. Разобьем массив на 2 части. Зафиксируем средний элемент. Сначала поменяем местами самый левый и самый правый элементы, для которых характерно, что левый элемент больше правого элемента. Так постепенно продвигаемся с двух концов к середине.

44 55 12 42 94 06 18 67 — 1 проход

a_i<X X a_j >X

18 55 12 42 94 06 44 67 — 2 проход

a_i<X Х a_j>X

18 06 12 42 94 55 44 67

<X Х >X

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

Приведем программную реализацию алгоритма Хоара на языке С++.

#include "stdafx.h"

#include <math.h>

#include <iostream>

using namespace std;

#include <conio.h>

#define SIZE 40

int n; // глобальная переменная

void xoor(int*,int,int,int);

int main()

{

// Инициализация

int A[SIZE],i;

cout<<"Input n= \n";

cin>>n;

cout<<" Enter items of array A:\n";

for(i=0;i<n;i++) cin>>A[i];

xoor(A,0,n-1,n); // функция сортировки методом Хоора

cout<<" Selected array A: \n";

for(i=0;i<n;i++)cout<<" "<<A[i];

getch();

return 0;

}

// РЕКУРСИЯ

void xoor(int* A,int m,int l,int n)

{

int i,j=l,k=0,p,X=A[(m+l)/2];

for(i=m;i<=(l+m)/2;i++)

{

if(((A[i]>X) && (A[j]<=X))||(A[i]> A[j]))

{

p=A[j];

A[j]=A[i];

A[i]=p;

xoor(A,m,l,n);

}

else i--;

j--;

if(j==(l+m)/2)

{

i++;

j=l;

}

}

for(i=0;i<=n-1;i++)

{

if(A[i]<A[i+1])k=k+1;

}

if(k==n) return;

if (m<(l-1)) // сортировка правой части от m до l

{

m=(l+m)/2;

xoor(A,m,l,n);

}

else // сортировка левой части от l/2 элемента до m

{

l=m;

m=l/2;

if(l!=0)xoor(A,m,l,n);

}

}

Сортировка «методом пузырька»

Идея, лежащая в основе сортировки «методом пузырька» заключается в следующем. Файл просматривается несколько раз последовательно. Каждый просмотр состоит из сравнения каждого элемента x_i файла со следующим за ним элементом x_i+1 и «обмена» (транспозиции) этих элементов, если они располагаются не в нужном порядке [3].

Например, задан файл 25, 57, 48, 37, 12, 92, 86, 33. Требуется отсортировать записи, расположив их по возрастанию значений элементов файла. Действия сортировки оформим в виде таблицы.

Итерация	Файл
0	25, 57, 48, 37, 12, 92, 86, 33
1	25, 48, 37, 12, 57, 86, 33, 92
2	25, 37, 12, 48, 57, 33, 86, 92
3	25, 12, 37, 48, 33, 57 ,86, 92
4	12, 25, 37, 33, 48, 57, 86, 92
5	12, 25, 33, 37, 48, 57, 86, 92

Эффективность «метода пузырька» считается следующим образом. Имеется в худшем случае n–1 просмотров файла и n–1 сравнений в каждом просмотре. Таким, образом, общее число сравнений равно (n–1) (n–1) = n² – 2n +1, что составляет n².

Единственным плюсом «метода пузырька» является то, что для такой сортировки требуется мало дополнительного пространства (одна дополнительная запись для временного хранения той записи, для которой выполняется транспозиция, и несколько простых целых переменных).