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

Основная идея, на которой базируется метод быстрой сортировки Хоара, состоит в том, чтобы взять одну из записей, скажем 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);

}

}