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

 

Основная идея, на которой базируется метод быстрой сортировки Хоара, состоит в том, чтобы взять одну из записей, скажем 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 ² – 2 n +1, что составляет » n ².

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