Metody sortowania ciągów liczbowych

Sortowanie bąbelkowe (ang. bubble sort) 

- prosta metoda sortowania o złożoności czasowej  i pamięciowej .

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.

Ciąg wejściowy . Każdy wiersz symbolizuje wypchnięcie kolejnego największego elementu na koniec ("wypłynięcie największego bąbelka"). Niebieskim kolorem oznaczono końcówkę ciągu już posortowanego.

Sortowanie przez wybieranie

 - jedna z prostszych metod sortowania o złożoności O(n²). Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.

Algorytm przedstawia się następująco:

1. wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy
2. zamień wartość minimalną, z elementem na pozycji i

Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu.

Algorytm jest niestabilny. Przykładowa lista to: [2a,2b,1] → [1,2b,2a] (gdzie 2b=2a)

Sortowanie przez zliczanie 

– metoda sortowania danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy.

Algorytm zakłada, że klucze elementów należą do skończonego zbioru (np. są to liczby całkowite z przedziału 0..100), co ogranicza możliwości jego zastosowania.

Sortowanie przez wstawianie (ang. Insert Sort, Insertion Sort) 

- jeden z najprostszych algorytmów sortowania, którego zasada działania odzwierciedla sposób w jaki ludzie ustawiają karty - kolejne elementy wejściowe są ustawiane na odpowiednie miejsca docelowe. Jest efektywny dla niewielkiej liczby elementów, jego złożoność wynosi O(n²)^[1]. Pomimo tego, że jest znacznie mniej wydajny od algorytmów takich jak quicksort czyheapsort, posiada pewne zalety:

• jest wydajny dla danych wstępnie posortowanych
• jest wydajny dla zbiorów o niewielkiej liczebności
• jest stabilny

Schemat działania:

1. Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze zbioru nieposortowanego.
2. Weź dowolny element ze zbioru nieposortowanego.
3. Wyciągnięty element porównuj z kolejnymi elementami zbioru posortowanego póki nie napotkasz elementu równego lub elementu większego (jeśli chcemy otrzymać ciąg niemalejący) lub nie znajdziemy się na początku/końcu zbioru uporządkowanego.
4. Wyciągnięty element wstaw w miejsce gdzie skończyłeś porównywać.
5. Jeśli zbiór elementów nieuporządkowanych jest niepusty wróć do punkt 2.

Sortowanie kubełkowe (ang. bucket sort) 

– jeden z algorytmów sortowania. Jest on najczęściej stosowany, gdy liczby w zadanym przedziale są rozłożone jednostajnie, ma on wówczas złożoność Θ(n). W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n²).

Pomysł takiego sortowania podali po raz pierwszy w roku 1956 E. J. Issac i R. C. Singleton.

Schemat działania:

1. Podziel zadany przedział liczb na n podprzedziałów (kubełków) o równej długości.
2. Przypisz liczby z sortowanej tablicy do odpowiednich kubełków.
3. Sortuj liczby w niepustych kubełkach.
4. Wypisz po kolei zawartość niepustych kubełków.

Zazwyczaj przyjmuje się, że sortowane liczby należą do przedziału od 0 do 1. Jeśli tak nie jest, to można podzielić każdą z nich, przez największą możliwą (jeśli znany jest przedział) lub wyznaczoną. Należy tu jednak zwrócić uwagę, że wyznaczanie największej możliwej liczby w tablicy m-elementowej ma złożoność obliczeniową O(m).

1. #include <iostream>
3. using namespace std;
5. int main(int argc, char *argv[])
6. {
7.     int max,min,count,*t,*t2;
8.     char exit;
9.     cout << "Ile liczb chcesz posortowac?";
10.     cin >> count;
11.     t = new int[count]; // Stworzenie tablicy dla danych wejĹ›ciowych
12.     for(int i=0;i<count;i++){ // Podanie liczb do sortowania
13.       cout << "Podaj " << i+1 << " liczbe: ";
14.       cin >> t[i];
15.     }
16.     max = t[0];
17.     min = t[0];
18.     for(int i=0;i<count;i++){ // Znalezienie najmniejszej i najwiÄ™kszej liczby
19.       max = max<t[i]?t[i]:max;
20.       min = min>t[i]?t[i]:min;
21.     }
22.     t2 = new int[max-min+1]; // Stworzenie tablicy z kubeĹ‚kami
23.     for(int i=0;i<=count;i++) t2[t[i]-min] += 1; // WypeĹ‚nianie kubeĹ‚kĂłw
24.     cout << "Kolejność rosnÄ…ca: ";
25.     for(int i=0;i<max-min+1;i++) if(t2[i]>0) for(int j=1;j<=t2[i];j++) cout << i+min << "  "; // Wypisanie wyniku
26.     cin >> exit;
27.     return 0;
28. }