«

»

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

Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом «Быстрая сортировка» (также «qsort» от англ. quick sort). Его разработал в 1960 году английский ученый Чарльз Хоар, занимавшийся тогда в МГУ машинным переводом. Алгоритм, по принципу функционирования, входит в класс обменных сортировок (сортировка перемешиванием, пузырьковая сортировка и др.), выделяясь при этом высокой скоростью работы.

Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

  • разбиение массива относительно опорного элемента;
  • рекурсивная сортировка каждой части массива.

Разбиение массива

Еще раз об опорном элементе. Его выбор не влияет на результат, и поэтому может пасть на произвольный элемент. Тем не менее, как было замечено выше, наибольшая эффективность алгоритма достигается при выборе опорного элемента, делящего последовательность на равные или примерно равные части. Но, как правило, из-за нехватки информации не представляется возможности наверняка определить такой элемент, поэтому зачастую приходиться выбирать опорный элемент случайным образом.

В следующих пяти пунктах описана общая схема разбиения массива (сортировка по возрастанию):

  1. вводятся указатели first и last для обозначения начального и конечного элементов последовательности, а также опорный элемент mid;
  2. вычисляется значение опорного элемента (first+last)/2, и заноситься в переменную mid;
  3. указатель first смещается с шагом в 1 элемент к концу массива до тех пор, пока Mas[first]>mid. А указатель last смещается от конца массива к его началу, пока Mas[last]<mid;
  4. каждые два найденных элемента меняются местами;
  5. пункты 3 и 4 выполняются до тех пор, пока first<last.

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

Имеется массив целых чисел Mas, состоящий из 8 элементов (рис. 5.5): Mas[1..8]. Начальным значением first будет 1, а last – 8. Пройденная часть закрашивается голубым цветом.

quicksort первая часть разбиения

В качестве опорного элемента возьмем элемент со значением 5, и индексом 4. Его мы вычислили, используя выражение (first+last)/2, отбросив дробную часть. Теперь mid=5.

quicksort вторая часть разбиения

Первый элемент левой части сравнивается с mid. Mas[1]>mid, следовательно first остается равным 1. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 8 и значением 8. Mas[8]>mid, следовательно last смещается на одну позицию влево. Mas[7]<mid, следовательно last остается равным 7. На данный момент first=1, а last=7. Первый и седьмой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.

quicksort третья часть разбиения

Алгоритм снова переходит к сравнению элементов. Второй элемент сравнивается с опорным: Mas[2]>mid, следовательно first остается равным 2. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 6 и значением 1: Mas[6]<mid, следовательно last не изменяет своей позиции. На данный момент first=2, а last=6. Второй и шестой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.

quicksort четвертая часть разбиения

Алгоритм снова переходит к сравнению элементов. Третий элемент сравнивается с опорным: Mas[3]<mid, следовательно first смещается на одну позицию вправо. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 5 и значением 9: Mas[5]>mid, следовательно last смещается на одну позицию влево. Теперь first=last=4, а значит, условие first<last не выполняется, этап разбиения завершается.

quicksort пятая часть разбиения

На этом этап разбиения закончен. Массив разделен на две части относительно опорного элемента. Осталось произвести рекурсивное упорядочивание его частей.

Рекурсивное доупорядочивание

Если в какой-то из получившихся в результате разбиения массива частей находиться больше одного элемента, то следует произвести рекурсивное упорядочивание этой части, то есть выполнить над ней операцию разбиения, описанную выше. Для проверки условия «количество элементов > 1», нужно действовать примерно по следующей схеме:

Имеется массив Mas[L..R], где L и R – индексы крайних элементов этого массива. По окончанию разбиения, указатели first и last оказались примерно в середине последовательности, тем самым образуя два отрезка: левый от L до last и правый от first до R. Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L<last. Для правой части условие аналогично: first<R.

Реализации алгоритма быстрой сортировки:

Код программы на C++:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;
const int n=7;
int first, last;
//функция сортировки
void quicksort(int *mas, int first, int last)
{
int mid, count;
int f=first, l=last;
mid=mas[(f+l) / 2]; //вычисление опорного элемента
do
{
while (mas[f]<mid) f++;
while (mas[l]>mid) l--;
if (f<=l) //перестановка элементов
{
count=mas[f];
mas[f]=mas[l];
mas[l]=count;
f++;
l--;
}
} while (f<l);
if (first<l) quicksort(mas, first, l);
if (f<last) quicksort(mas, f, last);
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
int *A=new int[n];
srand(time(NULL));
cout<<"Исходный массив: ";
for (int i=0; i<n; i++)
{
A[i]=rand()%10;
cout<<A[i]<<" ";
}
first=0; last=n-1;
quicksort(A, first, last);
cout<<endl<<"Результирующий массив: ";
for (int i=0; i<n; i++) cout<<A[i]<<" ";
delete []A;
system("pause>>void");
}

 

Код программы на Pascal:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
program qsort;
uses crt;
const n=7;
var A: array[1..n] of integer;
first, last, i: integer;
{процедура сортировки}
procedure quicksort(var mas: array[1..n] of integer; first, last: integer);
var f, l, mid, count: integer;
begin
f:=first;
l:=last;
mid:=mas[(f+l) div 2]; {вычисление опорного элемента}
repeat
while mas[f]<mid do inc(f);
while mas[l]>mid do dec(l);
if f<=l then {перестановка элементов}
begin
count:=mas[f];
mas[f]:=mas[l];
mas[l]:=count;
inc(f);
dec(l);
end;
until f>l;
if first<l then quicksort(A, first, l);
if f<last then quicksort(A, f, last);
end;
{основной блок программы}
begin
clrscr;
randomize;
write('Исходный массив: ');
for i:=1 to n do
begin
A[i]:=random(10);
write(A[i]:2);
end;
first:=1; last:=n;
quicksort(A, first, last);
writeln; write('Результирующий массив: ');
for i:=1 to n do
write(A[i]:2);
end.

 

Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *