Sortowanie przez wstawianie (insertion_sort)
void sort_wst(int n)
{
for (int i=2;i<=n;i++) // przechodę tablicę od drugiego elementu do
// końca (n-elementowa tablica
// z indexami od 1 do n)
liczba = tablica[i]; // zapamiętuje aktualną liczbę
wsk = i-1; // zapamiętuje index liczby
// poprzedniej
while(((wsk<=n) && (wsk>0)) && (tablica[wsk]>liczba))
// wykonuję dopóki liczba poprzednia jest większa od kolejnej
tablica[wsk+1]=tablica[wsk];
tablica[wsk]=liczba;
// zamieniam dwie sąsiednie liczby miejscami
wsk--; // cofam się w tabeli o jedno miejsce
}
Przechodzę kolejno tablicę i sprawdzam czy aktualny element jest mniejszy od poprzedniego, jeśli tak to zamieniam miejscami, aż element wcześniejszy nie będzie większy (tak jak przy ustawianiu kart w ręce).
Złożoność: optymistyczna – O(n), pesymistyczna – O(n2)
Budowanie kopca
void budowanie_kopca(int tablica[])
heap_size=n; // jako wielkość kopca podstawiam wielkość tabeli
for(int j=(n/2);j>=1;j--)
// dla każdego węzła (bo węzły kończą się się na indexie – połowie
// wielkości kopca) wywołuje funkcję przywracania kopca
przy_kop(tablica, j);
Dla każdego węzła wywołuje funkcję przywracania kopca.
Złożoność: O(n)
Przywracanie własności kopca
void przy_kop(int tablica[], int i) // i – index elementu psującego kopiec
while(true) // wykonuje pętle aż do przerwania przy przywróceniu kopca
lewy=2*i; // za zmienną podstawiam index lewego syna
// (zawsze 2 razy jego index)
prawy=(2*i+1); // za zmienną podstawiam index prawego syna
// (zawsze 2 razy plus 1 jego index)
if (lewy<=heap_size && tablica[lewy]>tablica[i])
// jeśli lewy syn jest większy od elementu, to do zmiennej podstawiam jego // index
maks=lewy;
else
// jeśli nie to podstawiam index elementu
maks=i;
if (prawy<=heap_size && tablica[prawy]>tablica[maks])
// jeśli prawy syn jest większy od elementu lub lewego syna (w zależności // od wcześniejszego wyboru), to do zmiennej podstawiam jego index
maks=prawy;
if (maks!=i)
// jeśli jakiś syn jest większy od elementu
tmp=tablica[i];
tablica[i]=tablica[maks];
tablica[maks]=tmp;
// zamieniam miejscami element z synem
i=maks; // za i podstawiam aktualny index elementu
// jeśli żaden syn nie jest większy od elementu, to przerywam pętle
break;
Wybieram element który „psuje kopiec” i sprawdzam, który jego następnik jest większy od niego i zamieniam je miejscami. Robię tak dopóki synowie danego elementu będą od niego więksi.
Złożoność: O(lg n)
Sortowanie przez kopcowanie (heap_sort)
void sortowanie_kopcowanie(int tablica[])
budowanie_kopca(tablica); // budowanie kopca
for(int i=n; i>=2; i--)
tablica[i]=tablica[1];
tablica[1]=tmp;
// zamieniam miejscami korzeń z ostatnim liściem
heap_size--;
// zmniejszam rozmiar kopca, ponieważ ostatni jego element jest już
// posortowany
przy_kop(tablica, 1);
// przywracam kopiec, przysyłając jako argument index korzenia
Buduje kopiec. Największy element znajduje się zawsze w korzeniu, więc zamieniam go miejscami z ostatnim elementem tablicy (ostatnim liściem), a następnie przywracam kopiec dla właśnie wymienionego liścia. Wcześniej zmniejszam długość kopca o jeden, aby ostatni element nie brał udziału w przywracaniu kopca.
Złożoność: O(n lg n)
Wstawianie do kopca
void wstawianie_kopiec(int tablica[], int i)
// i jest to rozmiar wstawianego elementu
heap_size++; // zwiększamy rozmiar kopca i tam wstawiamy element
z=heap_size; // do zmiennej przypisujemy rozmiar kopca
while (z>1 && tablica[z/2]<i)
// dopóki nie doszliśmy do korzenia i aktualny ojcec wstawianego elementu // jest mniejszy od wstawionego elementu
tablica[i]=tablica[z/2]; // za wstawiony element zamieniam
// jego ojca
z=tablica[z/2]; // zapisuje aktualną pozycję
tablica[z]=i; // na końcową pozycję wstawiam
// wartość dodawanego elementu
Dodawany element wstawiam na koniec kopca (jako ostatni liść) i przesuwam go w górę dopóki jego rodzice są od niego mniejsi, a rodziców wstawiam za zwolnione miejsce (zamieniam miejscami).
Sortowanie szybkie (quick_sort)
int dziel(int tablica[], int poczatek, int koniec)
x=tablica[poczatek]; // wybieram „pivota” – pierwsza liczba w tabeli
i=poczatek;
j=koniec;
while(true)
// wykonuję pętle aż do przerwania
while(tablica[j]>x)
j--;
// cofam się od końca podtabeli aż znajdę liczbę
// mniejszą lub równą pivotowi
while(tablica[i]<x)
i++;
// przesuwam się do końca podtabeli aż znajdę liczbę
// większą lub równą pivotowi
if(i<j)
// jeśli te dwa przesuwacze nie minęły się…
tablica[i]=tablica[j];
tablica[j]=tmp;
// …to zamieniam te liczby miejscami
j--; // zmniejszam/zwiększam obydwa indexy
// jeśli się minęły
return j; // zwracam “srodkową wartość” i przerywam pętle
void sortowanie_szybkie(int tablica[], int poczatek, int koniec)
if (poczatek<koniec)
// jeśli index początkowy jest mniejszy od końcowego w podtabeli
srodek = dziel(tablica, poczatek, koniec);
// wywołuję funkcję dzielącą na podtabele
// i zwracającą punkt dzielący
sortowanie_szybkie(tablica, poczatek, srodek);
sortowanie_szybkie(tablica, srodek+1, koniec);
// wywołuję funkcję sortującą dla każdej podtabeli
Wybieram dowolną liczbę – pivota, w tym przypadku pierwszą w każdej podtabeli i rozdzielam ją na dwie podtabele z liczbami większymi i mniejszymi od pivota i kolejno wywołuję funkcję rekurencyjnie dla każdej podtabeli.
Złożoność...
Hubert1997