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

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

void qsort ( int l , int u , int * x )

{

if ( l >= u ) return ;

Разбиение массива на две части;

qsort ( l , p -1, x ); // p – середина массива

qsort ( p +1, u , x );

}

Под серединой массива p понимается индекс такого элемента, что для любых i < p < j имеют место неравенства x [ i ] <= x [ p ] <= x [ j ] . Данная подпрограмма будет сортировать элементы x [ l ], x [ l +1],..., x [ u ] . Для сортировки всего массива она вызывается как qsort (0, n -1, x ).

Опишем алгоритм разбиения массива, индексы элементов которого имеют значения l , l +1,..., u . Будем разбивать этот массив на два из следующих соображений. Установим t = x [ l ] . Будем перебирать элементы массива, начиная с x [ l ] . Схема массива представлена на рис.

Схема прохождения массива

Здесь m – индекс последнего элемента, меньшего, чем t , i – номер элемента, начиная с которого массив еще не разбит, т.е. i – индекс рассматриваемого элемента.

Если x [ i ] ? t , то, увеличивая i на 1, мы расширяем область, для элементов которой известно, относятся они к левой или правой области разбиения. Если же x [ i ]< t , то, меняя местами x [ i ] и x [ m +1] и увеличивая m и i на 1, мы вновь расширяем область, разбиение которой известно.

Получаем следующие операции:

t = x [ l ];

m=l;

for(i=l+1; i<=u; i++)

if (x[i]<t)

{

m++; swap (m,i);

}

swap ( l , m );

последняя из которых меняет местами x [ l ] и x [ m ] .

Пример . Применим быструю сортировку Хоара для следующих входных данных:

55, 41, 59, 26, 53, 58, 97, 93

•  При i =1 будет x [1]<55 , m =1 , и x[1] поменяется местами сам с собой.

•  При i =2 будет x [2] ? 55.

•  При i =3 будет x [3]<55 , m =2 , и x[3] поменяется местами c x[2] ; получим массив:

55, 41, 26, 59, 53, 58, 97, 93.

•  При i =4 будет x [4]<55 , m =3, и x [4] поменяются местами с x [3] :

55, 41, 26, 53, 59, 58, 97, 93.

•  При i >4 элементы x [ i ] ? 55 , поэтому массив остается прежним.

После цикла x [ l ] и x [ m ] меняются местами. Получим массив, равный искомому разбиению:

53, 41, 26, 55, 59, 58, 97, 93.

Для дальнейшей сортировки нужно вызвать подпрограммы qsort (0,2, x ) и qsort (4,7, x ).

Для того чтобы данная подпрограмма быстро сортировала уже упорядоченные массивы, в начале её работы делается перестановка элемента x [ l ] с элементом x [ i ] , где i – индекс из диапазона l < i < u . Получаем следующий текст подпрограммы и вызывающей её программы:

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

void swap (int *a, int *b)

{

int temp=*a; *a=*b; *b=temp;

}

void q_sort (int l,int u, int *x)

{ int i, j, m, t;

if (l<u)

{

swap (&x[l], &x[l+random(u-l+1)]);

t=x[l]; m=l;

for (i=l+1; i<=u; i++)

if (x[i]<t)

{

m++; swap (&x[m],&x[i]);

}

swap (&x[l], &x[m]);

q_sort (l, m-1, x);

q_sort (m+1, u, x);

}

}

main()

{ int i; int *a=new int[10]; // массив из 10 чисел

randomize();

for (i=0; i<10; i++) a[i]=rand();

printf ("\ n Быстрая сортировка\ n До сортировки\ n ");

for (i=0; i<10; i++) printf (“ %d “, a[i]);

q_sort (0, 9, a);

printf("\n После сортировки \n");

for (i=0; i<10; i++) printf (“ %d “, a[i]);

}

Результаты работы программы

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

До сортировки

26473 17134 2983 19904 5261 15607 30031 5163 31868 6720

После сортировки

2983 5163 5261 6720 15607 17134 19904 26473 30031 31868