Strona główna » Algorytmy » Sortowanie » Sortowanie Grawitacyjne
 

Sortowanie Grawitacyjne

https://mattomatti.com/fs16

Opis

Algorytm Sortowania Grawitacyjnego został opracowany na obserwacji naturalnego zjawiska w codziennym życiu. Jego działanie polega na zastosowaniu tego zjawiska w celu przyciąganie w dół większe liczby. Idea działania poprawnie jedynie dla liczb naturalnych. Każda liczba na liście jest początkowo zamieniana na kamyczki i ustawiana na takiej wysokości jaką ma pozycję w tablicy. Następnie w każdym słupku jest przeprowadzana symulacja opadania - w celu przyśpieszenia tego procesu należy zebrać wszystkie kamyczki w kolumnie i dostawić od dołu. Potem w celu odczytania liczb wystarczy sprawdzić ile kamyczków jest na danym poziomie.

Przykład

Weźmy przykładowo tablicę L := {1, 7, 3, 4}. Pierwszy krok polega na rozrysowaniu schematu: dla i-tej liczby rysujemy na wysokości i w wierszu od lewej strony tyle kamyczków jaką wartość ma dana pozycja. Oto przykładowo wizualizacja:

Teraz należy przeprowadzic symulację opadania. W każdej kolumnie zliczamy ile znajduje się kamyczków. Wiadomo, że kamyczek nie opadnie jeśli bedzie pod nim inny kamyczek. Z tego powodu możliwe jest przestawienie k kamyczków w kolumnie na pierwsze k pozycji od dołu. Po przeprowadzeniu operacji opadania otrzymamy następujący obrazek:

Teraz pozostaje jedynie odczytać wartości liczb po posortowaniu. Jeśli chcemy, aby liczby zostały posortowane rosnąco to należy je odczytać od najwyższej wysokości do najniższej. W celu odczytania liczby w wierszu należy policzyć ile kamyczków się w niej znajduje.

Złożoność

Implementacja powyższego algorytmu w komputerze wymaga znalezienia maksymalnego elementu max na liście w czasie O(n2), zadeklarowania O(n·max) miejsca w pamięci. Algorytm będzie wykona dokładnie n z liczeń w każdej z max kolumn. Na koniec w podobnym czasie można odczytać wartości znajdujące się na liście. Podsumowując algorytm działa w czasie O(n·max) i jego złożoność pamięciowa wynosi O(n2).

Implementacja

Sortowanie danych należy rozpocząć od znalezienia największego elementu w tablicy. Dopiero na tej podstawie możliwe będzie utworzonie dwuwymiarowej tablicy - tutaj zostanie uproszczona do tablicy jednowymiarowej.

C++
C#
  1. void sortuj(int* tab, int n) {
  2.   int max = tab[0];
  3.   for (int i = 1; i < n; i++)
  4.     if (tab[i] > max)
  5.       max = tab[i];
  6.   bool* dane = new bool[max*n];
  7.   for (int i = 0; i < n; i++) {
  8.     for (int j = 0; j < tab[i]; j++)
  9.       dane[i*max + j] = true;
  10.     for (int j = tab[i]; j < max; j++)
  11.       dane[i*max + j] = false;
  12.   } 
  13.   for (int j = 0; j < max; j++) {
  14.     int ile = 0;
  15.     for (int i = 0; i < n; i++) {
  16.       ile += dane[i*max + j] ? 1 : 0;
  17.       dane[i*max + j] = false;
  18.     }
  19.     for (int i = n - ile; i < n; i++)
  20.       dane[i*max + j] = true;
  21.   }
  22.   for (int i = 0; i < n; i++) {
  23.     int ile = 0;
  24.     while (ile < max && dane[i*max + ile])
  25.       ile++;
  26.     tab[i] = ile;
  27.   }
  28. }

(2. - 5.) Znajdź maksimum i na tej podstawie (6.) zadeklaruj odpowiednio dużo pamięci. Potem (7. - 12.) do kolejnego wiersza zaznacz tyle pozycji ile ma kolejna liczba z tablicy. Na tej podstawie (13. - 21.) dla każdej kolumny zlicz ile jest zaznaczonych pozycji i przesuń do dołu. Na koniec (22. - 27.) odczytaj kolejne liczby po posortowaniu i przepisz do tablicy wejściowej.

Testowanie funkcji

Poniższy fragment kodu pozwala wczytać od użytkownika tablicę elementów do posortowania, a potem wypisać posortowaną tablicę.

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "Podaj ile jest elementow\n n = ";
  4.   cin >> n;
  5.   int* tab = new int[n];
  6.   cout << "Podaj elementy:\n";
  7.   for (int i = 0; i < n; i++)
  8.     cin >> tab[i];
  9.   sortuj(tab, n);
  10.   cout << "Po posortowaniu:\n";
  11.   for (int i = 0; i < n; i++)
  12.     cout << tab[i] << " ";
  13.   system("pause");
  14.   return 0;
  15. }

Zadania

Zadanie 1

Przedstawiona implementacja deklaruje zawsze tyle kolumn jaką wartość ma największy element na liście. Zapotrzebowanie na pamięć można poprawić poprzez znalezienie dodatkowo elementu najmniejszego. To pozwoli na ograniczenie ilości do minimum.

Napisz funkcję sortuj(), która skorzysta z przedstawionej wskazówki. Przetestuj napisane rozwiązanie.