AlgorytmyTeoriaSortowanieNumeryczneSzyfrowanieKompresjaGrafikaLiczby kontrolneTurbo PascalC++JavaVisual Basic 6 Aplikacje internetowe MySQL Excel DOS

Algorytmy: Algorytmy sortowania

Przedstawione tu algorytmy służą do sortowania niemalejącego tablicy jednowymiarowej (wektora danych), której wszystkie elementy są liczbami. Przy drobnych modyfikacjach można je wykorzystać do sortowania nierosnącego tablic o elementach nienumerycznych i/lub do sortowania tablic wielowymiarowych.

Jest to chyba najprostszy i najbardziej popularny algorytm sortowania.
Sprawdzamy całą tablicę od początku do końca i jeżeli trafimy na parę elementów (liczb), w której większy poprzedza mniejszy, to zamieniamy je miejscami i zaczynamy przeszukiwać tablicę od początku. Czynność powtarzamy tak długo, aż podczas sprawdzania całej tablicy nie wystąpi ani jedna zamiana elementów. Realizujemy to najczęściej za pomocą zmiennej logicznej.
Algorytm nosi nazwę bąbelkowego, gdyż największe liczby "wypływają" z dołu tablicy na jej szczyt.
Jeżeli tablica wejściowa będzie posortowana, to algorytm wykona tylko jeden przebieg, co jest dużą zaletą tego sortowania, gdyż niektóre metody będą sortowały ciąg nawet jeśli będzie on już posortowany.
Z kolei najgorszym zestawem danych dla tego algorytmu jest ciąg posortowany nierosnąco.

Opis tego algorytmu można przedstawić następująco:

1. Ustaw wskaźnik na 1-szy element tablicy.
    
2. Porównaj wybrany element tablicy z następnym. Jeżeli następny element jest mniejszy od bieżącego, to zamień je miejscami i wróć do kroku nr 1.
    
3. Jeżeli wybrany element jest przedostatnim elementem tablicy, to zakończ sortowanie,
    
4. Zwiększ wskaźnik elementu o 1 i przejdź do kroku nr 2.
    

Zasada działania tego algorytmu jest często porównywana do porządkowania kart w wachlarz podczas czasie gry: kolejne karty wstawiamy w odpowiednie miejsce, tzn. po młodszej, ale przed starszą. Podobnie jest z liczbami.
Idea działania algorytmu opiera się na podziale ciągu na dwie części: pierwsza jest posortowana, druga jeszcze nie. Wybieramy kolejną liczbę z drugiej części i wstawiamy ją do pierwszej. Ponieważ jest ona posortowana, to szukamy dla naszej liczby takiego miejsca, aby liczba na lewo była niewiększa a liczba na prawo niemniejsza.

Schemat algorytmu wygląda następująco:

1. Ustaw wskaźnik na 2-gi element tablicy.
    
2. Zapamiętaj wartość wybranego elementu tablicy.
    
3. Zapamiętaj wskaźnik wybranego elementu tablicy w N.
    
4. Dopóki N-1 element tablicy jest mniejszy od zapamiętanego i nie osiągnąłeś początku tablicy przenoś element z pozycji N-1 na pozycję o wskaźniku N i zmniejsz wartość N o 1.
    
5. Wstaw zapamiętaną wartość elementu tablicy na pozycję N.
    
6. Zwiększ wskaźnik elementu tablicy o 1.
    
7. Jeżeli nie przekroczyłeś zakresu tablicy, to wróć do kroku nr 2.
    

Metoda nazywana jest sortowaniem przez wymianę, gdyż polega na zamianie miejscami par elementów tablicy.
Na początku szukany jest najmniejszy element, a po znalezieniu go jest on zamieniany z pierwszym elementem tablicy. Następnie szukany jest znów najmniejszy element, ale począwszy od elementu drugiego (pierwszy - najmniejszy jest już wstawiony na odpowiednie miejsce), po jego znalezieniu jest on zamieniany z drugim elementem tablicy. Czynność tą powtarzamy na kolejnych elementach aż do n-tego.

Schemat algorytmu wygląda następująco:

1. Ustaw wskaźnik bieżącego elementu (N) na 1-szy element tablicy.
    
2. Zapamiętaj w zmiennej MIN wskaźnik N.
    
3. Ustaw wskaźnik przeszukiwania (M) na wskaźnik bieżącego elementu (N) + 1.
    
4. Jeżeli element o wskaźniku M jest mniejszy od elementu o wskaźniku N, to zapamiętaj wskaźnik M w zmiennej MIN.
    
5. Jeżeli wskaźnik M nie osiągnął końca tablicy, to zwiększ go o 1 i wróć do kroku 4.
    
6. Zamień miejscami elementy tablicy N i M.
    
7. Jeżeli wskaźnik N osiągnął koniec tablicy, to zakończ sortowanie.
    
8. Zwiększ wskaźnik N o 1 i wróć do kroku 2.
    

Sortowanie przez zliczanie działa w czasie liniowym, a więc jest bardzo szybkie. Pozwala jednak tylko na sortowanie liczb całkowitych.
Obie cechy wynikają ze sposobu sortowania. Polega ono na liczeniu, ile razy dana liczba występuje w ciągu, który mamy posortować. Następnie wystarczy utworzyć nowy ciąg, korzystając z danych zebranych wcześniej.

Ten algorytm charakteryzują następujące cechy:

1. Proces zliczania odbył się w jednym kroku (+)
    
2. Nie doszło do ani jednej zamiany elementów (+)
    
3. Proces tworzenia tablicy wynikowej odbył się w jednym kroku (+)
    
4. Do przechowywania liczby wyrazów ciągu musimy użyć tablicy, o liczbie elementów równej największemu elementowi ciągu (-)
    
5. Sortować można jedynie liczby całkowite (-)
    

Schemat algorytmu wygląda następująco:

1. Utwórz tablicę o ilości elementów równej maksymalnej wartości w sortowanej tablicy.
    
2. Wyzeruj wszystkie elementy tablicy pomocniczej.
    
3. Dla każdego elementu sortowanej tablicy dodaj 1 do elementu tablicy pomocniczej o wskaźniku równym wartości sortowanego elementu.
    
4. Dla każdego elementu tablicy pomocniczej wstaw do sortowanej tablicy tyle elementów o wartości wskaźnika tablicy pomocniczej ile wynosi wartość tego elementu.
    

Jest to jeden z najpopularniejszych algorytmów sortowania. Algorytm sortowania szybkiego jest uważany za najszybszy algorytm dla danych losowych oraz jest prosty do implementacji. W praktyce jest to najszybszy algorytm sortowania dużych tablic danych oparty na rekurencji.

Sortowanie szybkie opiera się na technice "dziel i zwyciężaj". Wejściowa tablica jest dzielona (po przestawieniu niektórych z jej elementów) na dwie mniejsze. Każdy element pierwszej tablicy nie jest większy niż każdy element drugiej tablicy. Liczbę, według której dokonuje się podziału to najczęściej pierwszy element tablicy. Następnie dla tych dwóch podtablic wywoływany jest rekurencyjnie ten sam algorytm. Wywołania rekurencyjne kończą się, gdy któraś z kolejnych podtablic zawiera tylko jeden element.

Ogólna idea szybkiego sortowania tablicy o N elementach wygląda tak:

• Procedurę sortującą wywołuje się z dwoma parametrami start i end. Określają one krańce podciągu do posortowania. Pierwsze wywołanie to: ProceduraSortująca(1, N).
   
• Wybieramy jeden element ciągu X (najczęściej pierwszy). Dzielimy ciąg na trzy części: część elementów mniejszych, część elementów równych i część elementów większych od X.
   
• Jeżeli ciąg elementów mniejszych od X jest dłuższy niż 1, wywołujemy rekurencyjnie procedurę sortującą dla tego ciągu.
   
• Jeżeli ciąg elementów większych od X jest dłuższy niż 1, wywołujemy rekurencyjnie procedurę sortującą dla tego ciągu.
   

Algorytm podziału na części polega na znajdywaniu par: (element > X) - (element < X) i zamianie ich miejscami. Najlepiej byłoby wybrać taki element dzielący X, który podzieli nasz ciąg na połowy. Nie opłaca się jednak zbyt długo szukać mediany z ciągu, dlatego często bierze się element pierwszy z brzegu.