Przeczytaj

Sortowanie pozycyjne jest to rodzaj sortowania, używający wewnętrznego stabilnego algorytmu sortowania do ułożenia elementów zgodnie z wcześniej ustalonymi warunkami (np. według alfabetycznej kolejności znaków lub w kolejności rosnących cyfr). Pomocniczy algorytm należy wywołać wielokrotnie, uwzględniając znaki od najmniej do najbardziej znaczących.

W tym materiale zaimplementujemy algorytm sortowania pozycyjnego dat w języku C++.

Specyfikacja problemu:

Dane:

rozmiar - liczba całkowita przechowująca informację dotyczącą liczby sortowanych dat,
daty[0..rozmiar - 1] - tablica jednowymiarowa przechowująca sortowane daty w formie napisu; daty w tablicy przechowywane są jako napisy w formacie RRRR‑MM‑DD.

Wynik:

daty[0..rozmiar - 1] – zawiera daty posortowane chronologicznie (od najwcześniejszej do najpóźniejszej)

Użyjemy stabilnego algorytmu sortowaniastabline algorytmy sortowaniastabilnego algorytmu sortowania – sortowania bąbelkowegosortowanie bąbelkowesortowania bąbelkowego (omówiono go w e‑materiale Sortowanie bąbelkowePCfvfjgLkSortowanie bąbelkowe). Zacznijmy od zadeklarowania tablicy zawierającej łańcuchy znaków string – daty do posortowania. W zmiennej rozmiar będzie przechowany rozmiar tablicy daty[].

Przykład 1

Do sprawdzenia poprawności naszego programu użyjemy następujących przykładowych dat: 13.02.1979, 10.03.1957, 05.03.2020, 20.04.2012, 03.12.1234. Zapiszemy je w formacie zgodnym ze specyfikacją (tj. RRRR‑MM‑DD)

#include <string>
using namespace std;

string daty[] = {
    "1979-02-13",
    "1957-03-10",
    "2020-03-05",
    "2012-04-20",
    "1234-12-03"
};

int rozmiar = 5;

Następnie definiujemy funkcję sortowanieBabelkowe(), która wykona sortowanie bąbelkowe zbioru dat według określonej pozycji. Pozycja ta zostanie przekazana jako parametr funkcji i będzie typu całkowitego int (int index).

#include <string>
using namespace std;

void sortowanieBabelkowe(int index) {
    string temp;
    bool nastapilaZmiana = false;
    
    for(int i = 0; i < rozmiar; i++) {
        for (int j = 0; j < rozmiar - i - 1; j++) {
            if ((daty[j][index]) > (daty[j+1][index])) {
                temp = daty[j];
                daty[j] = daty[j+1];
                daty[j+1] = temp;
                
                nastapilaZmiana = true;
            }
        }
        
        if (nastapilaZmiana == false) {
            break;
        }
    }
}

W funkcji sortowanieBabelkowe() został zaimplementowany algorytm sortowania bąbelkowego. Jedyną różnicą, w stosunku do wersji algorytmu dla liczb, jest warunek zamiany elementów (linijka 10.). O zmianie kolejności elementów nie decyduje wartość elementu, lecz znak znajdujący się na określonej pozycji w ciągu znaków reprezentującym datę.

Algorytm sortowania bąbelkowego został zoptymalizowany poprzez dodanie flagi bool, która sprawdza, czy zachodzą zmiany pozycji elementów. Jeżeli nie zachodzą, to znaczy, że elementy są już ustawione we właściwej kolejności i nie ma potrzeby podejmowania dalszych prób zamiany tych elementów. Algorytm kończy działanie, aby uniknąć niepotrzebnych iteracji.

Kolejnym krokiem jest zadeklarowanie funkcji sortowaniePozycyjne(), która uruchamia funkcję sortowania bąbelkowego tyle razy, ile jest cyfr w naszej dacie – czyli 8 razy (dzień – 2 cyfry, miesiąc – 2 cyfry oraz rok – 4 cyfry). Należy rozpocząć od cyfry najmniej znaczącej (cyfra jedności dnia, skrajnie prawa, indeks 9), a zakończyć na cyfrze najbardziej znaczącej (cyfra tysięcy roku, skrajnie lewa, indeks 0).

using namespace std;

void sortowaniePozycyjne() {
    for (int i = 9; i >= 0; i--) {
        if (i != 4 && i != 7) {
            sortowanieBabelkowe(i);
        }
    }
}

Funkcja sortowaniePozycyjne() iteruje po kolejnych, idąc od końca, znakach elementów zbioru daty[] i dla każdego znaku (z pominięciem znaku 4. i 7.) wywołuje funkcję sortowania bąbelkowego. Pominięcie znaku na indeksie 4 oraz znaku na indeksie 7 jest uzasadnione narzuconym przez specyfikację formatem daty. W formacie RRRR‑MM‑DD separatory (myślniki) znajdują się właśnie na tych indeksach. Dla innego formatu daty, należałoby tę funkcję odpowiednio zmodyfikować.

Przejdźmy teraz do funkcji głównej programu main(), w której uruchomimy funkcję sortowania pozycyjnego i sprawdzimy, czy działa poprawnie, uruchamiając ją dla przykładowych danych i sprawdzając, czy uzyskaliśmy poprawne wyniki.

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {

    sortowaniePozycyjne();
    
    for (int i = 0; i < rozmiar; i++) {
        cout << daty[i] << endl;
    }
    
    return 0;
}

Po uruchomieniu programu i wyświetleniu wyniku, widać, że nasz zbiór dat daty[] został poprawnie posortowany.

Wynik:

Czy jednak mamy pewność, że nasz algorytm sortuje dane pozycja po pozycji? Aby to sprawdzić, wypiszemy zawartość tablicy daty[], po każdym sortowaniu według kolejnych pozycji. Zrobimy to w funkcji sortowaniePozycyjne(), zaraz po wywołaniu funkcji sortowania bąbelkowego.

#include <iostream>
using namespace std;

void sortowaniePozycyjne() {
    for (int i = 9; i >= 0; i--) {
        if (i != 4 && i != 7) {
            sortowanieBabelkowe(i);
            for (int i = 0; i < rozmiar; i++) {
                cout << daty[i] << endl;
            }
            cout << endl;
        }
    }
}

Spójrzmy teraz na wynik po uruchomieniu programu.

Widzimy wyniki sortowania według kolejnych pozycji i są to wyniki prawidłowe.

Wynik:

Oto cały kod programu:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny string zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. string daty otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 6. cudzysłów 1979 minus 02 minus 13 cudzysłów przecinek. Linia 7. cudzysłów 1957 minus 03 minus 10 cudzysłów przecinek. Linia 8. cudzysłów 2020 minus 03 minus 05 cudzysłów przecinek. Linia 9. cudzysłów 2012 minus 04 minus 20 cudzysłów przecinek. Linia 10. cudzysłów 1234 minus 12 minus 03 cudzysłów. Linia 11. zamknij nawias klamrowy średnik. Linia 13. int rozmiar znak równości 5 średnik. Linia 15. void sortowanieBabelkowe otwórz nawias okrągły int index zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. string temp średnik. Linia 17. bool nastapilaZmiana znak równości false średnik. Linia 19. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny rozmiar średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny rozmiar minus i minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. if otwórz nawias okrągły otwórz nawias okrągły daty otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias kwadratowy index zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias ostrokątny otwórz nawias okrągły daty otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy otwórz nawias kwadratowy index zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. temp znak równości daty otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 23. daty otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości daty otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik. Linia 24. daty otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 26. nastapilaZmiana znak równości true średnik. Linia 27. zamknij nawias klamrowy. Linia 28. zamknij nawias klamrowy. Linia 30. if otwórz nawias okrągły nastapilaZmiana znak równości znak równości false zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. break średnik. Linia 32. zamknij nawias klamrowy. Linia 33. zamknij nawias klamrowy. Linia 34. zamknij nawias klamrowy. Linia 36. void sortowaniePozycyjne otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. for otwórz nawias okrągły int i znak równości 9 średnik i zamknij nawias ostrokątny znak równości 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. if otwórz nawias okrągły i wykrzyknik znak równości 4 ampersant ampersant i wykrzyknik znak równości 7 zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. sortowanieBabelkowe otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 40. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny rozmiar średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 41. cout otwórz nawias ostrokątny otwórz nawias ostrokątny daty otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 42. zamknij nawias klamrowy. Linia 43. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 44. zamknij nawias klamrowy. Linia 45. zamknij nawias klamrowy. Linia 46. zamknij nawias klamrowy. Linia 48. int main otwórz nawias okrągły int argc przecinek const char asterysk argv otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 49. sortowaniePozycyjne otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 50. return 0 średnik. Linia 51. zamknij nawias klamrowy.

#include <iostream>
#include <string>
using namespace std;

string daty[] = {
    "1979-02-13",
    "1957-03-10",
    "2020-03-05",
    "2012-04-20",
    "1234-12-03"
};

int rozmiar = 5;

void sortowanieBabelkowe(int index) {
    string temp;
    bool nastapilaZmiana = false;
    
    for(int i = 0; i < rozmiar; i++) {
        for (int j = 0; j < rozmiar - i - 1; j++) {
            if ((daty[j][index]) > (daty[j+1][index])) {
                temp = daty[j];
                daty[j] = daty[j+1];
                daty[j+1] = temp;
                
                nastapilaZmiana = true;
            }
        }
        
        if (nastapilaZmiana == false) {
            break;
        }
    }
}

void sortowaniePozycyjne() {
    for (int i = 9; i >= 0; i--) {
        if (i != 4 && i != 7) {
            sortowanieBabelkowe(i);
            for (int i = 0; i < rozmiar; i++) {
                cout << daty[i] << endl;
            }
            cout << endl;
        }
    }
}

int main(int argc, const char * argv[]) {
    sortowaniePozycyjne();
    return 0;
}

Słownik

sortowanie bąbelkowe

sortowanie polegające na porównywaniu ze sobą dwóch sąsiadujących elementów w kolejności od lewej do prawej i zamianie ich, jeżeli znajdują się w nieprawidłowej kolejności

stabline algorytmy sortowania

algorytm sortowania, który w przypadku elementów o równej wartości, pozostawi je w takiej samej kolejności jak były pierwotnie; do stabilnych algorytmów sortowania należą między innymi: sortowanie bąbelkowe, sortowanie przez zliczanie, sortowanie przez wstawianie, sortowanie kubełkowe, sortowanie przez scalanie

Wprowadzenie

Film samouczek

Słownik