Sortowanie Przez Mapowanie

Wstęp

Sortowanie Przez Mapowanie to uogólnienie sortowania Kubełkowego w połączeniu z Sortowaniem Przez Wstawianie. W ten sposób dane mogą zostać posortowane w czasie zbliżonym do liniowego. Jednak takie sortowanie wymaga dodatkowej pamięci.

Algorytm

Przed przystąpieniem do sortowania należy zastanowić się jak będzie odbywał się przydział do odpowiedniego kosza. Może to wymagać dodatkowej analizy tablicy. Po opracowaniu odpowiedniej strategii należy utworzyć odpowiednią ilość koszy. Każdy kolejny element należy dołączyć do odpowiedniego kosza, ale musi on zostać wstawiony tak, aby elementy w koszu były posortowane. Na koniec wystarczy do tablicy przepisać zawartość z każdego kosza po kolei, aby uzyskać posortowane dane.

Przykład

Prześledźmy sortowanie listy liczb rzeczywistych L:={1.1, 2.3, 1.8, 1.4, 4.6, 4.4, 1.7}. Na początek należy określić strategię według której dane zostaną wrzucane do koszy. W tym przypadku lista zostanie najpierw przeanalizowana tak, aby znaleźć element maksymalny i minimalny. W celu wyliczenia numera kosza przyporządkowania danego elementu zostanie on pomniejszony o minimum, a potem zostanie usunięta część dziesiętna. Wtedy liczba koszy wyniesie tyle co różnica maksimum zaokrąglonego w górę oraz minimum zaokrąglonego w dół powiększone o 1.

W tym przypadku min = 1.1, a max = 4.6, więc łączna liczba koszy wyniesie = 5 - 1 + 1 = 5. Oznacza to, że do kosza o indeksie 0 trafią wszystkie liczby postaci 1.xx.

Na koniec pozostaje scalić wszystkie elementy umieszczone w koszach, aby uzyskać posortowaną listę L':={1.1, 1.4, 1.8, 2.3, 3.7, 4.4, 4.6}.

Złożoność Czasowa

Najlepsza możliwa złożoność czasowa jest liniowa O(n). Jest to również średnia złożoność algorytmu pod warunkiem, że dane będą dzielone w miarę równo pomiędzy kubełki. Najgorszy możliwy przypadek jest wtedy, gdy wszystkie elementy trafią do jednego kubełka. Wtedy złożoność algorytmu wzrasta do kwadratowej O(n²). Złożoność pamięciowa w każdym przypadku jest zawsze liniowa O(n).

Zadanie

Napisz funkcję sortuj(), która posortuje listę liczb rzeczywistych, która zostanie wprowadzona przez użytkownika. Program powinien wypisać posortowaną listę liczb na ekran.

Rozwiązanie

Funkcja Mapująca

W przykładowym rozwiązaniu zadania zostanie zastosowana strategia, która została opisana w przykładzie sortowania. Funkcja mapuj() akceptuje dwa argumenty: a - wartość do przydzielenia kosza oraz min - minimalna wartość na liście.

1. int mapuj(double a, double min) {
2.   return (int)(floor(a - min));
3. }

Sortowanie

Oto przykładowa funkcja sortująca, która posortuje liczby w tablicy dane. Funkcja nic nie zwraca, ponieważ posortowane dane zostają przepisane do przekazanej tablicy.

1. void sortuj(double* dane, double n) {
2.   double min = dane[0], max = dane[0];
3.   for (int i = 1; i < n; i++) {
4.     if (dane[i] < min) {
5.       min = dane[i];
6.     } else if (dane[i] > max){
7.       max = dane[i];
8.     }
9.   }
10.   int ilekoszy = ceil(max) - floor(min) + 1;
11.   vector< vector<double> > kosze;
12.   for (int i = 0; i < ilekoszy; i++) {
13.     vector<double> v;
14.     kosze.push_back(v);
15.   }
16.   for (int i = 0; i < n; i++) {
17.     int kosz = mapuj(dane[i], min);
18.     int q = 0;
19.     while (kosze[kosz].size() > q && kosze[kosz][q] < dane[i])
20.       q++;
21.     kosze[kosz].insert(kosze[kosz].begin() + q, dane[i]);
22.   }
23.   int zapis = 0;
24.   for (int i = 0; i < ilekoszy; i++) {
25.     for (int j = 0; j < kosze[i].size(); j++) {
26.       dane[zapis++] = kosze[i][j];
27.     }
28.   }
29. }

Na początku (2. - 9.) tablica jest analizowana w celu znalezienia wartości minimalnej oraz maksymalnej. Na tej podstawie (10.) wyliczona zostaje ilość koszy. Kolejny etap polega na (11. - 15.) przygotowaniu pustych koszy. (16. - 22.) Następnie każdy kolejny element zostaje wrzucony do opowiedniego kosza, ale (18. - 21.) na odpowiedniej pozycji. Na koniec (22. - 27.) wszystkie elementy posortowane wewnątrz każdego kosza zostają przepisane do oryginalnej tablicy.

Testowanie funkcji

W celu przetestowania działania napisanej funkcji, a także, aby rozwiązać do końca zadanie potrzebny jest poniższy kod. Wczytuje on od użytkownika ile jest elementów n, a następnie wywyołuje sortowanie i wypisuje wynik.

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 Implementacja

Zadania

Zadanie 1

Napisz funkcję, która posortuje malejąco wprowadzoną listę liczb całkowitych zgodnie z porządkiem leksykograficznym.

Przykładowa posortowana tablica liczb L:={1, 7, 31, 4, 65, 42, 2, 53} będzie wyglądać następująco:

1. 7 65 53 4 42 31 2 1

• Kod źródłowy Zadanie 1