programowanie asembler algorytmy

sortowanie

Sortowanie, a dokładnie jego szybkość, jest bardzo ważnym elementem w wielu programach. Do tej pory wymyślono wiele algorytmów sortowania. Różnią się poziomem skomplikowania i wydajnością oraz zajętością pamięci. Zazwyczaj algorytmy, które dobrze sobie radzą na dużych zbiorach danych przegrywają (pod względem szybkości) z algorytmami o większym średnim czasie wykonania - dlatego trzeba używać innego algorytmu do sortowania tablic kilkuelementowych, innego do sortowania tablic kilkudziesięcioelementowych, a innego do sortowania jakichś potężnych tablic.

Uwaga: w przykładach zakładam, że tablica jest numerowana od zera, a my sortujemy tablicę rosnąco. W nawiasach podaję nazwy anglieskie.

Sortowanie bąbelkowe (bubblesort)

Algorytm najpowszechniej znany ze względu na jego prostotę. Polega na uporządkowywaniu kolejnych par elementów. Po jednym przejściu największy elemnet jest już na ostanim miejscu, więc przy następnym przejściu można go opuścić. Pętlę kończymy, gdy nie ma już elementów do posortowania. Algorytm można przedstawić w następująco:

dla i od rozmiar-2 do 0
  dla j od 0 do i
    jeżeli a[j] wieksze od a[j+1]
      zamień a[j] i a[j+1]

Ma złożoność O(n pow 2) i jest ona niezależna od danych wejściowych.

Sortowanie przez prosty wybór (selectionsort)

Algorytm także bardzo prosty. Polega na wyszukiwaniu w tablicy najmniejszego elementu, zamianie go z pierwszym elementem, zwiększeniu indeksu początku tablicy o jeden i powtarzaniu procesu. Pętlę kończymy, gdy nie ma już elementów do posortowania. Algorytm można przedstawić następująco:

dla i od 0 do rozmiar-1
  n:=i
  dla j od i+1 do rozmiar-1
    jeżeli a[j] mniejsze od a[n]
      n:=j
  zamień a[n] i a[i]

Algorytm także ma złożoność O(n pow 2) i jest ona niezależna od danych wejściowych. Zależnie od rodzaju optymalizacji może być szybszy lub wolniejszy od sortowania bąbelkowego.

Sortowanie przez wstawianie (insertionsort)

Algorytm dzieli tablicę na dwie części: posortowaną i nieposortowaną. Na początku zakłada, że piewszy element jest jednocześnie tą tablicą posortowaną. Potem bierze element stojący bezpośrednio za częścią posortowaną i przesuwa go po jednym miejscu do początku, aż znajdzie się na właściwym miejscu. Proces ten powtarzamy, aż część nieposortowana pozostanie pusta. Algorytm można przedstawić następująco:

dla i od 1 do rozmiar-1
  j:=i
  b:=a[j]
  dopóki j niezerowe oraz b mniejsze od a[j-1]
    a[j]:=a[j-1]
    j:=j-1
  a[j]:=b

Lub tak (dla kilkuelementowych tablic):

dla i od 1 do rozmiar-1
  j:=i
  dopóki j niezerowe oraz a[j] mniejsze od a[j-1]
    zamień a[j] i a[j-1]
    j:=j-1

Algorytm ma średnią złożoność równą O(n pow 2) i w zazwyczaj jest około dwa razy szybszy niż dwa poprzednie algorytmy. Posiada także optymistyczną złożoność równą O(n) dla tablic posortowanych lub *prawie* posortowanych.

Sortowanie metodą Shella (shellsort)

Dawno temu Shell badał algorytm insertionsort i doszedł do wnosku, że:

Bazując na algorytmie insertionsort i powyższych wnioskach stworzył własny algorytm. Polega on na dzieleniu tablicy na wiele kolumn, z których każda jest sortowana algorytmem insertionsort. Następnie tablicę dzielimy na mniejszą liczbę kolumn i powtarzamy sortowanie, aż zostanie jedna kolumna (ją oczywiście też sortujemy). Dzięki takiej konstrukcji elementy zostają ustawione we właściwym miejscu w mniejszej liczbie kroków. Liczby kolumn na ile kolejno dzielimy tablicę tworzą malejący ciąg. Od niego przede wszystkim zależy jaka będzie efektywność algorytmu. Dla źle dobranych ciągów (np: samej jedynki - wtedy algorytm jest zwykłym algorytmem insertionsort) złożoność jest równa O(n pow 2), ale dla dobrze dobranych wartości osiąga złożoność O(n log n log n).

Jednym z lepszych ciągów zapewniających dobrą szybkość sortowania jest ten wymyślony przez Pratta. Każdy kolejny element w ciągu jest opisany wzorem: an=2p3q. Oto początek ciągu (do granicy czterech gigabajtów):

1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2187, 2304, 2592, 2916, 3072, 3456, 3888, 4096, 4374, 4608, 5184, 5832, 6144, 6561, 6912, 7776, 8192, 8748, 9216, 10368, 11664, 12288, 13122, 13824, 15552, 16384, 17496, 18432, 19683, 20736, 23328, 24576, 26244, 27648, 31104, 32768, 34992, 36864, 39366, 41472, 46656, 49152, 52488, 55296, 59049, 62208, 65536, 69984, 73728, 78732, 82944, 93312, 98304, 104976, 110592, 118098, 124416, 131072, 139968, 147456, 157464, 165888, 177147, 186624, 196608, 209952, 221184, 236196, 248832, 262144, 279936, 294912, 314928, 331776, 354294, 373248, 393216, 419904, 442368, 472392, 497664, 524288, 531441, 559872, 589824, 629856, 663552, 708588, 746496, 786432, 839808, 884736, 944784, 995328, 1048576, 1062882, 1119744, 1179648, 1259712, 1327104, 1417176, 1492992, 1572864, 1594323, 1679616, 1769472, 1889568, 1990656, 2097152, 2125764, 2239488, 2359296, 2519424, 2654208, 2834352, 2985984, 3145728, 3188646, 3359232, 3538944, 3779136, 3981312, 4194304, 4251528, 4478976, 4718592, 4782969, 5038848, 5308416, 5668704, 5971968, 6291456, 6377292, 6718464, 7077888, 7558272, 7962624, 8388608, 8503056, 8957952, 9437184, 9565938, 10077696, 10616832, 11337408, 11943936, 12582912, 12754584, 13436928, 14155776, 14348907, 15116544, 15925248, 16777216, 17006112, 17915904, 18874368, 19131876, 20155392, 21233664, 22674816, 23887872, 25165824, 25509168, 26873856, 28311552, 28697814, 30233088, 31850496, 33554432, 34012224, 35831808, 37748736, 38263752, 40310784, 42467328, 43046721, 45349632, 47775744, 50331648, 51018336, 53747712, 56623104, 57395628, 60466176, 63700992, 67108864, 68024448, 71663616, 75497472, 76527504, 80621568, 84934656, 86093442, 90699264, 95551488, 100663296, 102036672, 107495424, 113246208, 114791256, 120932352, 127401984, 129140163, 134217728, 136048896, 143327232, 150994944, 153055008, 161243136, 169869312, 172186884, 181398528, 191102976, 201326592, 204073344, 214990848, 226492416, 229582512, 241864704, 254803968, 258280326, 268435456, 272097792, 286654464, 301989888, 306110016, 322486272, 339738624, 344373768, 362797056, 382205952, 387420489, 402653184, 408146688, 429981696, 452984832, 459165024, 483729408, 509607936, 516560652, 536870912, 544195584, 573308928, 603979776, 612220032, 644972544, 679477248, 688747536, 725594112, 764411904, 774840978, 805306368, 816293376, 859963392, 905969664, 918330048, 967458816, 1019215872, 1033121304, 1073741824, 1088391168, 1146617856, 1162261467, 1207959552, 1224440064, 1289945088, 1358954496, 1377495072, 1451188224, 1528823808, 1549681956, 1610612736, 1632586752, 1719926784, 1811939328, 1836660096, 1934917632, 2038431744, 2066242608, 2147483648, 2176782336, 2293235712, 2324522934, 2415919104, 2448880128, 2579890176, 2717908992, 2754990144, 2902376448, 3057647616, 3099363912, 3221225472, 3265173504, 3439853568, 3486784401, 3623878656, 3673320192, 3869835264, 4076863488, 4132485216, 4294967296

Algorytm można przedstawić następująco:

hn:=rozmiar_ciągu-1
dopóki rozmiar mniejsze niż ciąg[hn]*2
  hn:=hn-1
dopóki hn nieujemne
  h:=ciąg[hn]
  k:=h-1
  dopóki k nieujemne
    i:=k+h
    dopóki i mniejsze od rozmiar
      j:=i
      b:=a[j]
      dopóki j nie mniejsze od h oraz b mniejsze od a[j-h]
        a[j]:=a[j-h]
        j:=j-h
      a[j]:=b
      i:=i+h
    k:=k-1
  hn:=hn-1

PS: powyższego algorytmu jeszcze nie testowałem (proszę o ew. uwagi).

Sortowanie szybkie (quicksort)

Jest to sortowanie oparte na algorytmie dziel i zwyciężaj. Tablica jest dzielona na część o elementach mniejszych lub równych elementowi dzielącemu oraz na część o elementach większych lub równych elementowi dzielącemu. Jeżeli którakolwiek z tych części ma więcej niż jeden element to sortujemy ją rekurencyjnie.

Średnia złożoność algorytmu to O(n log n), ale w niektórych przypadkach (raczej zamierzonych) może wzrośnąć nawet do O(n pow 2). Jako że algorytm jest rekurencyjny to potrzebuje on stosu na odkładanie zmiennych. Srednia wielkość potrzebnego stosu to O(log n), ale w niektórych przypadkach może wzrosnąć do O(n). W dobrych implementacjach (tylko mniejsza część jest sortowana rekurencyjnie, a druga jest sortowana na tym samym poziomie rekurencji) maksymalna zajętość stosu wynosi O(log n).

Sortowanie stogowe (heapsort)

Algorytm wykorzystuje właświwości kopca. Najpierw układa tablicę tak, aby utworzyła kopiec (element największy jest korzeniem). Następnie korzeń zamienia z ostatnim elementem tablicy, zmniejsza jej rozmiar (dokładniej indeks) i powtarza wcześniejsze kroki, aż do całkowitego posortowania.

Złożoność algorytmu to O(n log n) i jest ona w zasadzie stała. Ponadto nie wymaga przestrzeni na stosie jak to jest w przypadku quicksorta'. Jednak, mimo takiej samej złożoności, jest średnio dwa razy wolniejszy od quicksort'a dlatego, że odwołuje się do "losowych" elementów tablicy, co jest dużo trudniejsze dla pamięci podręcznej procesora niż quicksort, gdzie elementy są sprawdzane w sposób ciągły, tzn. jeden za drugim.

Sortowanie stogowo-szybkie (?) (introsort)

Jest to sortowanie będące połączeniem dwóch powyższych algorytmów. Jest ono w zasadzie quicksortem, ale gdy wykryje, że coś jest nie tak (zbyt duży poziom rekurencji) to automatycznie przełącza się na heapsort. W ten sposób ma średnią prędkość quicksorta, przy złożoności O(n log n). PS: Nazwę ('stogowo-szybkie') sobie wymyśliłem, nie wiem jak ona brzmi po polsku.

Uwaga do trzech powyższych algorytmów

Do tych sortowań, czyli: quicksort'a, heapsort'a i introsort'a nie dałem przykładów, gdyż byłyby one zbyt skomplikowane i długie do przedstawienia na stronie. Jeżeli jesteś ciekaw jak one wyglądają to pobierz (ze mojej strony) program "Algorytmy sortujące" testujący prędkości tych algorytmów.