Sortowanie Karciane

Opis

Sortowanie Karciane można powiązać z grą Pasjans, ponieważ polega ono na utworzeniu stosików kart na których każda następna karta jest mniejsza. Jednak w tym przypadku nie ma ograniczenia ile stosików można utworzyć.

Algorytm

Na początku należy przygotować tablicę z danymi, a następnie dla każdego kolejnego elementu znaleźć stos na którym po dołożeniu aktualnie wybranego elementu zostanie zachowana reguła, że każdy dokładany element na stos musi być mniejszy niż ten, który już leży na wierzchu. Jeśli elementu nie można dołożyć na żaden stos to należy utworzyć nowy stos i tam położyć element. Po rozłożeniu wszystkich elementów należy przejść do drugiego etapu, który polega na wybraniu najmniejszego elementu na wierzchu wszystkich stosów, a następnie zapisaniu go jako kolejny element na tablicy. Proces należy powtórzyć tak długo, aż wszystkie stosy będą puste.

Przykład

Dane

Rozpatrzmy Sortowanie Karciane na przykładzie, gdzie do posortowania jest tablica {5, 1, 3, 4, 2}. Proces zostanie przeanalizowany krok po kroku.

Etap I

Etap pierwszy polega na podzieleniu tablicy na stosy liczb:

Etap II

Drugi etap polega na wyborze najmmniejszej wartości na każdym ze stosów, a następnie ich przepisywanie do tablicy:

Złożoność

Złoność pamięciowa algorytmu wynosi O(n), ponieważ na początek istnieje potrzeba rozłożenia elementy na stos i będzie to wielkość proporcjonalna to rozmiaru tablicy n. W przypadku złożoności czasowej znaczenie mają tu dwa czynniki: ilość stosów - wpływa na czas szukania najmniejszego elementu oraz ilość elementów na stosie - im stosy mają podobną ilość elementów tym większa szansa, że do końca przeszukiwań zawsze będzie tyle samo stosów do przeszukania. Dzieląc n elementową tablicę na k elementów to w każdej grupie będzie po n/k elementów, więc w przybliżeniu potrzeba O(2n·k·n/k) = O(n²). Jednak ze względu na to, że podczas dzielenia na stosy zachodzi wstępne sortowanie to bardzo mało prawdopodobne, że dla k zajdzie k² = n, więc przyjmuje się złożoność O(n·logn).

Implementacja

Funkcja sortuj() sortuje dane w miejscu zgodnie z algorytmem Sortowania Karcianego. Funkcja nic nie zwraca.

1. void sortuj(int* dane, int n) {
2.   vector< stack<int> > v;
3.   for (int i = 0; i < n; i++) {
4.     int wybor = 0;
5.     while (wybor < v.size() && dane[i] > v[wybor].top())
6.       wybor++;
7.     if(wybor == v.size())
8.       v.push_back(stack<int>());
9.     v[wybor].push(dane[i]);
10.   }

(2.) Na początku należy przygotować zmienną, która będzie przechowywać stosy. (3.) Dla każdego elementu w tablicy: (4. - 6.) wybieramy stos do którego ten element dodajemy. (7.) Jeśli indeks wskazuje nie istniejący stos to (8.) należy go utworzyć. Następnie (9.) do odpowiedniego stosu dokładamy kolejny element.

11.   for (int i = 0; i < n; i++) {
12.     int min = 0;
13.     for (int j = 1; j < v.size(); j++)
14.       if (v[j].top() < v[min].top())
15.         min = j;
16.     dane[i] = v[min].top();
17.     v[min].pop();
18.     if (v[min].size() == 0)
19.       v.erase(v.begin() + min);
20.   }
21. }

Drugi etap (11.) polega na: (12. - 15.) sprawdzeniu na którym stosie znajduje się aktualnie najmniejsza wartość, a następnie (16. - 17.) przepisujemy ją do tablicy i zdejmujemy ze stosu. (18.) Jeśli wybrany stos zostanie opróżniony to (19.) usuwamy go.

Testowanie funkcji

W celu przetestowania napisanej funkcji sortuj() można skorzystać z poniższego fragmentu kodu, który wczyta od użytkownika rozmiar tablicy n i wczyta n liczb, które następnie zostaną wypisane posortowane.

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. }

• Kod źródłowy Implementacja