Co to jest sortowanie tablic?
Sortowanie tablic to proces pobierania poszczególnych elementów tablicy i układania ich w pewnego rodzaju logicznej kolejności zgodnie z serią reguł określonych przez użytkownika. Proces obejmuje przechodzenie przez tablicę, jeden element na raz i testowanie tego elementu względem elementów otaczających w celu ustalenia, czy należy go przenieść do innego indeksu w tablicy. Podczas sortowania tablic można zastosować kilka algorytmów, zwłaszcza gdy warunki sortowania są liczbowe, a nie coś bardziej arbitralnego. Większość algorytmów sortowania tablic mierzy się ich szybkością i wydajnością, przy czym najwolniejsze algorytmy są najłatwiejsze do zaprogramowania, a najszybsze znacznie bardziej złożone.
Najprostszy algorytm sortowania tablic nazywa się sortowaniem bąbelkowym i jest również najwolniejszy. Proces rozpoczyna się od pętli, która przechodzi przez każdy element w tablicy. Bieżący element jest porównywany z kolejnym elementem w tablicy, a jeśli następny element ma niższą wartość niż element bieżący, dane w indeksach są przełączane. Wadą sortowania bąbelkowego jest to, że musi on kilkakrotnie zapętlić tablicę, aby wykonać wszystkie niezbędne wymiany w celu posortowania tablicy. W najbardziej podstawowych implementacjach sortowanie będzie zapętlało całą tablicę jeden pełny czas dla każdego elementu, który zawiera.
Sortowanie selekcyjne wykorzystuje algorytm, który wykonuje sortowanie tablic w nieco bardziej wydajny sposób niż sortowanie bąbelkowe, ale nadal wymaga wielu iteracji przez tablicę. Sortowanie rozpoczyna się od zapętlenia tablicy, aby znaleźć element o najniższej wartości. Ten element jest następnie umieszczany w pierwszym indeksie tablicy, a niektóre zmienne śledzące są zwiększane. Cykl następnie się powtarza, szukając teraz następnej najniższej wartości, która zostanie następnie umieszczona w drugim indeksie tablicy. Proces ten trwa do momentu umieszczenia elementu o najwyższej wartości w ostatnim indeksie tablicy.
Metoda sortowania tablic, która może być wydajna, ale czasem złożona do wdrożenia, znana jest jako szybkie sortowanie. Szybkie sortowanie polega na przyjęciu wartości znajdującej się pośrodku wszystkich możliwych wartości przechowywanych w tablicy. Algorytm przechodzi przez wszystkie elementy tablicy i umieszcza wszystkie wartości większe niż mediana na końcu tablicy, a niższe wartości na początku. Proces ten jest wykonywany rekurencyjnie na blokach tablicy, aż na końcu cała tablica zostanie posortowana. Zakładając, że środkowa wartość użyta dla tablicy jest dość dokładna, może to być bardzo szybki sposób sortowania.
Jednym z czynników, który może wpływać na algorytm sortowania tablic, są środki, za pomocą których dane są testowane pod kątem równoważności. Proste liczby są łatwe do porównania, dla których wartość jest większa, ale może nie być tak w przypadku złożonych klas danych, w których należy porównać wiele warunków. Im dłużej trwa porównywanie, czy jeden element jest większy czy mniejszy od drugiego, tym dłużej algorytm posortuje tablicę.