Sortowanie Gnoma

Wstęp

Sortowanie Gnoma to metoda sortowania danych, która wymaga jedynie jednej pętli. Implementacja częściowo opiera się na pomyśle z sortowania bąbelkowego. Złożoność tego algorytmu to Θ(n₂). W najlepszym przypadku złożoność może być liniowa. Algorytm wymaga tylko zmiennej do zapamiętania aktualnej pozycji sortowania, więc złożoność pamięciowa to Θ(1).

Algorytm

Sortowanie rozpoczyna się od pierwszego elementu na liście. Jeśli aktualnie rozpatrywany element jest pierwszym elementem na liście, albo spełnia warunki posortowania to należy zwiększyć numer indeksu. W przeciwnym wypadku należy zamienić aktualny element z poprzednim i zmniejszyć indeks o 1.

Istnieje jeszcze zoptymalizowana wersja tego algorytmu. Podczas rozpoczęcia cofania elementu algorytm zapamiętuje aktualną pozycję i po przesunięciu elementu na jego właściwą pozycję wraca do zapamiętanej pozycji. W ten sposób pomijany jest proces przechodzenia element po elemencie do opuszczonej pozycji.

Przykład

Weźmy przykładowo listę L:=[1, 5, 2, 4, 3]. Początkowy indeks pos = 0 (wskazuje na pierwszy element na liście). Lista będzie sortowana rosnąco:

W podanym przykładzie algorytm cofał się łącznie cztery razy i dokonał tyle samo niepotrzebnych ruchów do przodu. Nadmiarowe kroki w wersji zoptymalizowanej są pomijane poprzez zapamiętanie pozycji na której algorytm znalazł nie ustawiony element. Warto zauważyć, że podczas ustawiania elementu algorytm zachowuje się jak algorytm sortowania bąbelkowego.

Implementacja

Podstawowa wersja

Do zaimplementowania sortowania Gnoma wystarczy tylko jedna pętla oraz indeks, który będzie wskazywał dokąd zaszło sortowanie. Poniżej znajduje się gotowa implementacja algorytmu:

1. void sortuj(double* lista, int n) {
2.   int pos = 0;
3.   while (pos < n) {
4.     if (pos == 0 || lista[pos] >= lista[pos - 1]) {
5.       pos++;
6.     } else {
7.       swap(lista[pos], lista[pos - 1]);
8.       pos = pos - 1;
9.     }
10.   }
11. }

(2.) Rozpocznij sortowanie od pozycji 0. (3.) Dopóki indeks nie wykroczy poza granice tabeli (4.) podejmij decyzję jaką akcję wykonać. W przypadku, gdy indeks wynosi 0 lub dany element jest posortowany względem poprzedniego to (5.) przejdź do następnej pary elementów. (6.) W przeciwnym wypadku: (7.) zamień aktualny element z poprzednim i (8.) zmniejsz indeks o 1.

Wersja zoptymalizowana

Jak wcześniej zostało wspomniane algorytm wykonuje zbędne kroki po ustawieniu elementu w posortowanej części listy. Można temu zapobiec dodając dodatkowy indeks. W poniższym rozwiązaniu jego rolę spełnia zmienna last_pos.

Ważne jest to, aby zauważyć, że ostatnią pozycję należy zapamiętać przed pierwszą zamianą, a następnie można wrócić do zapamiętanego indeksu dopiero jak następi zwiększenie indeksu. Wtedy można przejść nawet o jedną pozycję dalej niż wartość zapamiętana. Zadanie realizuje poniższy kod:

1. void sortuj(double* lista, int n) {
2.   int pos = 0;
3.   int ost_pos = 0;
4.   while (pos < n) {
5.     if (pos == 0 || lista[pos] >= lista[pos - 1]) {
6.       pos = ost_pos + 1;
7.       ost_pos = pos;
8.     } else {
9.       swap(lista[pos], lista[pos - 1]);
10.       pos = pos - 1;
11.     }
12.   }
13. }

Zoptymalizowana wersja nie zmienia samej struktury algorytmu, ale dodaje dodatkowe warunki. (2.) Ponownie sortowanie zaczyna się od pierwszego elementu i (3.) należy zaznaczyć, że zapamiętana pozycja też ma tę samą wartość. W dalszej części algorytmu podczas zwiększania wartości (6.) należy przejść o jedną pozycję dalej niż zapamiętana oraz (7.) zapamiętać nową wyliczoną wartość jako ostatnią wartość. Podczas przesuwania elementów pozycja ost_pos nie jest modyfikowana, więc algorytm wróci do niej jak tylko zakończy ustawianie elementu.

Testowanie funkcji

W celu przetestowania działania każdej z implementacji można skorzystać z poniższej funkcji main(). Wczyta ona od użytkownika potrzebne dane, a następnie wypisze posortowaną listę na ekran.

1. int main() {
2.   int n;
3.   cout << "Podaj ilosc elementow: ";
4.   cin >> n;
5.   cout << "Podaj " << n << " elementow:\n";
6.   double* lista = new double[n];
7.   for (int i = 0; i < n; i++)
8.     cin >> lista[i];
9.   sortuj(lista, n);
10.   cout << "Posortowana lista to:\n";
11.   for (int i = 0; i < n; i++)
12.     cout << lista[i] << " ";
13.   delete lista;
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Podstawowa wersja
• Kod źródłowy Wersja zoptymalizowana

Zadania

Zadanie 1

Napisz funkcję o nagłówku double* sortuj(const double* lista, int n), która posortuje element na liście lista malejąco. Przykładowo dla tablicy L:=[45, 12, 42, 33, 34] program wypisze:

1. 12 33 34 42 45

• Kod źródłowy Zadanie 1