Sortowanie Częstotliwościowe

Wstęp

Sortowanie Częstotliwościowe to takie sortowanie, które sortuje elementy analizując częstotliwość ich występowania. Oznacza to, że elementy o tej samej wartości o największej liczbie wystąpień znajdą się na początku listy. Istnieją różne metody rozwiązania przedstawionego problemu.

Opis sortowania

Najczęściej spotykana implementacja Sortowania Częstotliwościowego polega na policzeniu ile jest wystąpień każdego elementu. Oczywiście bardzo ważną sprawą jest to, aby przechowywać również informację o tym w jakiej kolejności kolejne elementy zostały odnalezione, ponieważ jeśli dwa różne elementy mają tyle samo wystąpień to powinny zachować kolejność z tablicy wejściowej. Tablicę przechowującą wartość każdego elementu i ilość wystąpień należy teraz posortować zgodnie z ilością wystąpień (tj. częstotliwością występowania elementu). Jednak w przypadku, gdy liczba wystąpień dwóch różnych elementów jest taka sama to należy posortować zgodnie z kolejnością ich wystąpowanie w tablicy wejściowej. Na koniec wystarczy odtworzyć tablicę na podstawie posortowanej tablicy.

Przykład

Do posortowania jest następująca tablica L:={4, 3, 2, 2, 3, 1, 3, 1, 3}. Pierwszy etap polega na policzeniu ile jest wystąpień każdego elementu oraz zapamiętanie pierwszego wystąpienia każdego z elementu.

Dane na liście mogą być posortowane, ponieważ w dalszej części i tak zostaną odpowiednio ustawione dzięki przechowywaniu informacji o pierwszym wystąpieniu. Teraz całą tablicę należy posortować względem wystąpień.

Element 2 znalazł się przed elementem 1, ponieważ pierwszy wystąpił w tablicy wejściowej. Teraz pozostało odczytać wynik na podstawie utworzonej tablicy. Każdy kolejny element zostanie wpisany do tablicy zgodnie z tym ile razy występuje. Posortowana tablica wyjściowa to L':={3, 3, 3, 3, 2, 2, 1, 1, 4}.

Zadanie

Napisz program, który posortuje elementy malejąco względem częstotliwości ich występowania. Elementy o tej samej ilości wystąpień powinny zostać posortowane według indeksu peirwszego wystąpienia elementu. Przetestuj działanie napisanego programu.

Rozwiązanie

Przechowywanie danych

Ze względu na to, że dane najpierw są analizowane i każdy element wymaga przechowania kilku informacji to została napisana specjalna strruktura Element, która pozwala na przechowanie jako obiekt (2.) klucza, (3.) ilości wystąpień oraz (4.) indeks pierwszego wystąpienia.

1. struct Element {
2.   int klucz;
3.   int wystapien;
4.   int indeks;
5. };

Porównywanie danych

Do sortowania danych będących podsumowaniem analizowanej tablicy zostanie wykorzystane sortowanie wbudowane w język programowania. Jednak wymaga to zdefiniowania odpowiedniego fragmentu kodu, który porówna dwa elementy. Poniższa funkcja porownaj() zwraca, który element a czy b jest większy.

1. bool porownaj(Element a, Element b) {
2.   if (a.wystapien != b.wystapien)
3.     return (a.wystapien > b.wystapien);
4.   else return a.indeks < b.indeks;
5. }

Sortowanie danych

Teraz można przejść do pisania właściwego kodu sortowania. Na początku należy (2.) utworzyć listę do przechowywania podsumowania, a następnie (4. - 17.) utworzyć podsumowanie.

1. int* sortuj(int* dane, int n) {
2.   vector<Element> lista;
3.   int p = 0;
4.   for (int i = 0; i < n; i++) {
5.     p = 0;
6.     while (p < lista.size() && dane[i] > lista[p].klucz)
7.       p++;
8.     if (lista.size() == p || dane[i] != lista[p].klucz) {
9.       Element el;
10.       el.klucz = dane[i];
11.       el.wystapien = 0;
12.       el.indeks = i;
13.       lista.insert(lista.begin() + p, el);
14.     }
15.     lista[p].wystapien++;
16.   }
17.   stable_sort(lista.begin(), lista.end(), porownaj);
18.   int* w = new int[n];
19.   p = 0;
20.   for (int i = 0; i < lista.size(); i++) {
21.     for (int j = 0; j < lista[i].wystapien; j++) {
22.       w[p++] = lista[i].klucz;
23.     }
24.   }
25.   return w;
26. }

W celu utworzenia podsumowania należy: (6. - 7.) sprawdzić czy istnieje już wpis dla i-tej wartości. Jeśli nie to (8. - 14.) należy dodać taki wpis, a potem (16.) zwiększyć ilość wystąpień danego elementu. Dalsza część kodu polega na (18.) posortowaniu danych i (19. - 23.) ich następnym przepisaniu.

Testowanie funkcji

W celu przetestowania napisanej funkcji sortującej można skorzystać z poniższego fragmentu kodu:

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

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję, która do sortowania będzie przechowywać jedynie parę wartości: indeks oraz ilość wystąpień. Ponadto tym razem elementy powinny zostać posortowane według częstotliwości w sposób rosnący. W przypadku, gdy dwa elementy mają tyle samo wystąpień to o ich kolejności powinno zadecydować ostatnie ich wystąpienie.

Przykładowo tablica L:={4, 3, 2, 2, 3, 1, 3, 1, 3} powinna zostać posortowana następująco:

1. 4 2 2 1 1 3 3 3 3

Wyjaśnienie

Najpierw należy zbudować odpowiednią tablicę wartości:

Zgodnie z zadaniem klucz nie powinien być przechowywany przez program. Następne posortowanie daje następujący wynik:

Na tej podstawie można wygenerować tablice końcową L':={4, 2, 2, 1, 1, 3, 3, 3, 3}.

• Kod źródłowy Zadanie 1