20 kwietnia 2005 23:11Sortowanie szybkiePaweł Gniadkowski [Kardon] Algorytm sortowania szybkiego jest dość prosty i jego zrozumienie nie powinno nikomu sprawić problemu.
Najpierw przedstawię implementację w C++: #include <iostream>
using namespace std;
/**********************************
FUNKCJA SORTUJACA
**********************************/
int quick(int *tabl, int l, int p)
{
int v=tabl[(l+p)/2];
int i,j,temp;
i=l;
j=p;
do
{
while (tabl[i]<v) i++;
while (v<tabl[j]) j--;
if (i<=j)
{
temp=tabl[i];
tabl[i]=tabl[j];
tabl[j]=temp;
i++;
j--;
}
}
while (i<=j);
if (l<j) quick(tabl,l,j);
if (i<p) quick(tabl,i,p);
}
/**********************************
FUNKCJA MAIN()
**********************************/
int main()
{
int n;
cout << "Ile liczb mam posortowac?\n";
cin >> n;
int tabl[n];
for (int i=0;i<n;i++)
{
cout << "\nPodaj " << i+1 << " liczbe: ";
cin >> tabl[i];
}
cout << "\n\n";
quick(tabl,0,n-1);
for (int i=0;i<n;i++)
{
cout << tabl[i] << " ";
}
}
Za mechanzm sortowania będzie odpowiadać funkcja quick, której parametrami są odpowiednio: wskaźnik na sortowaną tablicę, lewy kraniec sortowanego przedziału oraz prawy kraniec sortowanego przedziału. W pierwszej kolejności funkcja znajduje środkowy element sortowanej tablicy (linia 10). Następnie wszystkie elementy tablicy większe od środkowego są przenoszone na prawo od niego. Analogicznie elementy mniejsze od środkowego są przenoszone na lewą stronę.
W kolejnym kroku dwukrotnie wywoływana jest funkcja quick - najpierw dla lewej części przeszukiwanego obszaru, następnie dla prawej (granicę między tymi obszarami wyznacza element środkowy znaleziony wcześniej). Sortowanie lewej i prawej części obszaru odbywa się analogicznie - najpierw szukanie elementu środkowego, następnie przenoszenie elementów na lewą lub prawą stronę elementu środkowego, a na końcu wywołanie funkcji sortowania dla połówek obszaru (dopóki połówka ma więcej, niż jeden element).
Paweł Gniadkowski [Kardon]
