: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > sortowanie >

S O R T O W A N I E   T O P O L O G I C Z N E

 

0 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 29 30

 
       

Zbiory takie jak zbiór liczb, zbiór liter, zbiór słów w słowniku, zbiór dat urodzenia, są zbioramy, w których określony jest tzw. porządek - dla każdej pary różnych elementów a i b takiego zbioru można określić, który z nich jest mniejszy: albo a<b (mówimy, że a poprzedza b), albo b<a. Jeśli w zbiorze elementów dla pewnych par określone są relacje mniejszości (poprzedzania), zaś dla innych są one nieznane, to zbiór taki może posiadać właśność częściowego porządku. Częściowy porządek R jest relacją spełniającą trzy warunki:

  1. nieprawdą jest, że x R x - przeciwzwrotność - nieprawda, że element poprzedza sam siebie,

  2. jeśli x R y, to nieprawda że y R x - antysymetryczność - jeśli x poprzedza y, to nie jest możliwe, aby y poprzedzało x

  3. jeśli x R y i y R x, to x R z - przechodniość - jeśli x poprzedza y oraz y poprzedza z, to x poprzedza też z.

Jeśli popatrzymy na szkolny program nauczania matematyki, to funkcja liniowa powinna znaleźć się w nim przed funkcją kwadratową, zaś funkcja kwadratowa przed wielomianami, objętość prostopadłościanu po polu powierzchni prostokąta, liczby wymierne po liczbach całkowitych, itp. Ale wielomian ma raczej niewiele wspólnego z liczbami wymiernymi, czy obwodem koła - dla takich par porządek może w ogóle nie być określony.

Elementy zbioru, w którym określono częściowy porządek można przedstawić na grafie skierowanym. Graf taki będzie zawierał krawędź (u, v) gdy element u zbioru poprzedza element v - własności przeciwzrotności oraz przechodniości gwarantują, że otrzymany w ten sposób graf będzie acykliczny - nie wystąpią w nim cykle. Oprócz tego, graf taki zawiera co najmniej jeden wierzchołek, który nie ma swojego poprzednika, gdyby każdy wierzchołek miał co najmniej jeden poprzednik, to musiałby powstać cykl.

Sortowanie topologiczne jest algorytmem porządkującym elementy zbioru, w którym określona jest relacja częściowego porządku - elementy zbioru należy ustawić w ciąg w taki sposób, aby dla każdej pary elementów a i b, jeśli a poprzedza b, to powinien w ciągu wystąpić wcześniej.

Dla zbioru {1, 2, 3, 4, 5}, w którym określono porządek pomiędzy następującymi parami:

1<2 1<3 1<4 2<3 2<4 3<5

nieznana jest relacja pomiędzy elementami 4 i 5. Liczby tego zbioru można ustawić w posortowany ciąg na dwa sposoby:

1 2 3 4 5
1 2 3 5 4

Zbiór n-elementowy można posortować wykonując iterację o n przebiegach - jeśli usuniemy ze zbioru element nie posiadajacy poprzednika oraz wszystkie krawędzie wchodzące do niego, to w otrzymanym zbiorze również określony jest częściowy porządek i wystąpi w nim ponownie element nie posiadający poprzednika.