Сортиране по дялове – бързо сортиране
Като се има предвид, че метода на
мехурчето(пряката размяна) е най-неефективният метод за сортиране трябва да се
очаква сравнително голям процент на подобрение. Изненадващо обаче е, че
подобрението на този метод води до най-добрият метод за сортиране на масиви,
познат до сега. Неговата ефективност е толкова голяма, че авторът му C.A.R.Hoare го е нарекъл бързо сортиране.
Бързото сортиране се основава на
факта, че на колкото по-големи разстояния се правят разместванията, толкова
по-ефективно е сортирането.
Нека е даден масив с n елемента, подредени по
низходящ ред. Те могат да се сортират само с n/2 размени, като най-напред се
разменят най-левият и най-десният елемент и постепенно се отива навътре и от
двете страни.
Пример
масив
А[10] 281 163
87 71 58 21 12
8 5 0
подредения масив A[10]
0
5 8 12
21 58 71
87 163 281
Естествено това се получава само
ако масивът е обратно подреден, но можем да опишем нещо подобно и за неподреден
масив:
1)
нека изберем един елемент от масива и го наречем х.
2)
сканираме масива отляво, докато намерим елемент, чиято
стойност е по-голяма от х (ai > x).
3)
сканираме масива отдясно, докато намерим елемент, чиято
стойност е по-малка от х (aj < x).
4)
разменяме стойностите на ai и aj.
5)
продължаваме стъпки 2, 3 и 4 дотогава, докато двете
сканирания се срещнат някъде по средата на масива.
Пример
|
i=0 |
1 |
2 |
3 |
4 |
|
6 |
7 |
8 |
j=9 |
|
86 |
35 |
72 |
42 |
94 |
56 |
18 |
67 |
22 |
5 |
|
|
|
i=2 |
|
|
|
|
|
j=8 |
|
|
5 |
35 |
72 |
42 |
94 |
56 |
18 |
67 |
22 |
86 |
|
|
|
|
|
i=4 |
|
j=6 |
|
|
|
|
|
5 |
35 |
22 |
42 |
94 |
56 |
18 |
67 |
72 |
86 |
|
Така получаваме два подмасива:
1) със стойности a[k] <= x и индекси k=0……(i-1);
2) със стойности a[k] >= x и индекси k=(j+1)……(n-1).
Всеки от двата подмасива се подрежда по същия
начин. Получават се четири подмасива, които от своя страна също се подреждат по
показания вече начин. Процедурата се изпълнява, докато си достигне до
подмасиви, състоящи се от по един елемент.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
5 |
35 |
22 |
42 |
18 |
56 |
94 |
67 |
72 |
86 |
|
|
|
х |
|
|
|
|
х |
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
5 |
18 |
22 |
42 |
35 |
56 |
67 |
94 |
72 |
86 |
|
х |
|
|
х |
|
х |
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
5 |
18 |
22 |
35 |
42 |
56 |
67 |
72 |
94 |
86 |
|
|
|
|
х |
|
|
|
|
х |
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
5 |
18 |
22 |
35 |
42 |
56 |
67 |
72 |
86 |
94 |
Понякога двата подмасива могат да
включват общи елементи (когато в масива има няколко елемента със стойност х).
Тази област е a[k] = x с индекси k=(j+1)……(i-1).
Пример:
|
i=0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
j=8 |
|
9 |
2 |
5 |
8 |
2 |
6 |
2 |
1 |
0 |
|
0 |
i=1 |
2 |
3 |
4 |
5 |
6 |
j=7 |
8 |
|
0 |
2 |
5 |
8 |
2 |
6 |
2 |
1 |
9 |
|
0 |
1 |
i=2 |
3 |
4 |
5 |
j=6 |
7 |
8 |
|
0 |
1 |
5 |
8 |
2 |
6 |
2 |
2 |
9 |
|
0 |
1 |
2 |
i=3 |
j=4 |
5 |
6 |
7 |
8 |
|
0 |
1 |
2 |
8 |
2 |
6 |
|
2 |
9 |
|
0 |
1 |
2 |
j=3 |
i=4 |
5 |
6 |
7 |
8 |
|
0 |
1 |
2 |
2 |
8 |
6 |
5 |
2 |
9 |
|
0 |
j=1 |
2 |
3 |
i=4 |
5 |
6 |
7 |
8 |
|
0 |
1 |
2 |
2 |
8 |
6 |
5 |
2 |
9 |
Левият подмасив включва
елементите с индекси от 0 до 3 (i-1), а десният- елементите с индекси
от 2(j+1) до 8 (n-1 ).
С право възниква въпросът не може
ли стойностите равни на х да не ги местим, т.е. уравнението a[i]<x да стане a[i]<=x и съответно a[j]>x да стане a[j]>=x. Принципно е възможно, но крие
опасност от излизане извън границите на масива.
Пример
|
0 |
i=1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
2 |
3 |
2 |
8 |
2 |
6 |
5 |
2 |
9 |
x=a[4]=2
Индексът i стартира от 0 и се увеличава докато a[i]<=x и когато се достигне до стойност a[i] >x спира (в случая i=1).
Индексът j стартира от 8 (n-1 ) и се намалява,
докато a[j]>=x, но в случая всички елементи са >=2 и няма
ограничение, което да спре индекса да не излезе извън границите на масива.
Блоковата схема на алгоритъма на
едно сканиране (първото) е показана на фиг.1, а функцията на листинг1. За
среден елемент на масива се избира елемента със среден индекс. Индексната
променлива i следи сканирането отляво, а
индексната променлива j - сканирането
отдясно.Сканирането продължава докато (i<=j), т.е. докато двете сканирания се срещнат някъде по
средата на масива. Не е задължително това да е елемента x.
Блокова схема на алгоритъма
Листинг1
void
partition(
)
{ float x, pom;
int i=0, j=n-1;
x=a[(i+j)/2]; // среден елемент
do {
while (a[i]<x) i++; //сканиране отляво
while (a[j]>x) j--; //сканиране
отдясно
if(i<=j)
{ pom=a[i]; //размяна
a[i]=a[j]; //размяна
a[i]=pom; //размяна
i++; j--; //сканирането продължава
}
}
while(i<=j);
}
По условие
този алгоритъм е рекурсивен. При първото сканиране масивът се разделя на два
подмасива - ляв и десен. Левият подмасив от своя страна също се разделя на два
подмасива. Десния подмасив - също. Тези подмасиви от своя страна отново се
разделят на по два, докато се стигне до подмасив от по един елемент.
За това е
подходящо да се използва и рекурсивната функция при кодирането на
алгоритъма(листинг2).
Функцията е
sort(int l, int r). Аргумента l сочи първия индекс
на подмасива за сканиране, а r -
последният му индекс. В началният момент l=0, а r =n-1.
Листинг2
#include <iostream.h>
#include
<conio.h>
int
n;
float
a[100];
void
input (void)
{
int i;
cout<<"n=";cin>>n;
for(i = 0; i<n;i++)
{ cout<<"a["<<i<<"]="; cin>>a[i]; }
}
void
output (void)
{
int i;
for(i=0;i<n;i++)
{
cout<<a[i]<<'\t';
}
}
void
sort (float a[100],int left, int right)
{
float x, pom;
int i,j;
i = left;
j = right;
x = a[(left +right)/2];
do {
while
(a[i]<x) i++;
while (a[j]>x) j--;
if (i <= j)
{ pom=a[i];
a[i]=a[j];
a[j]=pom;
i++; j--;
}
} while (i <= j);
if
(left <j) sort (a, left,j);
if
(i<right) sort (a, i, right);
}
void
QuickSort (float a[100], int n)
{
sort (a, 0,n-1);
}
void
main(void)
{
int n;
float a[100];
input (a,n) ;
QuickSort (a,n) ;
output (a,n) ;
}