Sortowanie pozycyjne

Sortowanie pozycyjne liczb jest metodą sortowania opierającą się na porządkowaniu elementów ze względu na cyfry umieszczone na tych samych pozycjach.

W tej sekcji zapoznamy się z implementacją algorytmu sortowania pozycyjnego liczb, wykorzystującego sortowanie bąbelkoweP77EQCGCtsortowanie bąbelkowe. Ten algorytm, podobnie jak algorytm sortowania przez zliczanie, cechuje stabilność. Sortowanie bąbelkowe swoje działanie opiera na dwóch zagnieżdżonych pętlach. Jeżeli elementy nie zostały umieszczone w odpowiedniej kolejności, zamienia je miejscami.

Implementacja w języku C++

Zanim przystąpimy do implementacji, zapoznajmy się ze specyfikacją.

Specyfikacja:

Dane:

• dane[] – jednowymiarowa tablica liczb naturalnych; dane do posortowania

• liczbaElementow – liczba naturalna; długość tablicy dane

• liczbaCyfr – liczba naturalna dodatnia; liczba cyfr tworzących największą liczbę z tablicy dane

Wynik:

• dane – posortowana niemalejąco tablica liczb naturalnych

Mamy do posortowania następujący zbiór: {562, 3, 11, 25, 303, 4, 500}. Zaczynamy od stworzenia tablicy o nazwie dane, w której umieszczamy elementy zbioru. Ponadto tworzymy dwie zmienne: liczbaElementow, przechowującą liczbę elementów zbioru, a także liczbaCyfr, której przypiszemy liczbę cyfr, z jakiej składa się największa liczba w zbiorze.

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

int dane[] = {562, 3, 11, 25, 303, 4, 500};
int liczbaElementow = 7;
int liczbaCyfr = 3;

Następnie implementujemy funkcję typu void, która jest odpowiedzialna za sortowanie liczb na danej pozycji za pomocą algorytmu sortowania bąbelkowegosortowanie bąbelkowesortowania bąbelkowego. Funkcja przyjmuje parametr równy numerowi aktualnej pozycji.

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

int dane[] = {562, 3, 11, 25, 303, 4, 500};
int liczbaElementow = 7;
int liczbaCyfr = 3;

void sortowanieBabelkowe(int pozycjaCyfry) {
}

Algorytm sortowania bąbelkowego (ang. bubble sort) bazuje na utworzeniu zagnieżdżonej pętli for, w której sprawdzane jest, czy element poprzedni jest większy od następnego, to znaczy, czy ułożone są one w kolejności malejącej. Jeżeli jest to prawda, zamieniamy elementy ze sobą, ponieważ naszym celem jest posortowanie tablicy w porządku niemalejącym.

W algorytmie sortowania pozycyjnego sortujemy liczby na pojedynczych pozycjach. Tworzymy zatem dodatkowo zmienną wspolczynnikCyfry, która jest potrzebna do odczytania cyfry na odpowiedniej pozycji liczby ze zbioru. Nie będziemy sortować całych liczb, lecz tylko cyfry na konkretnej pozycji. Umożliwi nam to operacja polegająca na podzieleniu liczby przez wspolczynnikCyfry, a następnie obliczeniu reszty z dzielenia jej przez 10.

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

int dane[] = {562, 3, 11, 25, 303, 4, 500};
int liczbaElementow = 7;
int liczbaCyfr = 3;

void sortowanieBabelkowe(int pozycjaCyfry) {

    int wspolczynnikCyfry = pow(10, pozycjaCyfry);

    for(int i = liczbaElementow - 1; i >=0; i--) {
        for(int j = 0; j < i; j++) {
            if(((dane[j] / wspolczynnikCyfry) % 10) > ((dane[j+1] / wspolczynnikCyfry) % 10)) {
                int temp = dane[j];
                dane[j] = dane[j+1];
                dane[j+1] = temp;
            }
        }
    }
}

Możemy zoptymalizować kod, wprowadzając flagę, dzięki której zredukujemy liczbę niepotrzebnych iteracji pętli. Wystarczy, że dodamy zmienną logiczną bool o nazwie czyZmiana, która domyślnie będzie przyjmować wartość false – taką ustawiamy wartość początkową flagi.

Jeżeli chociaż w jednej iteracji pętli wewnętrznej zostaną zamienione ze sobą dwa elementy tablicy, ustawiamy wartość flagi na true. W przypadku, gdy pętla wewnętrzna zakończy swoje działanie, a w jednym całym przejściu nie zostaną zamienione ze sobą żadne elementy, wartość flagi nie zmieni się, tym samym kończąc sortowanie.

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

int dane[] = {562, 3, 11, 25, 303, 4, 500};
int liczbaElementow = 7;
int liczbaCyfr = 3;

void sortowanieBabelkowe(int pozycjaCyfry) {

    int wspolczynnikCyfry = pow(10, pozycjaCyfry);
    bool czyZmiana = false;

    for(int i = liczbaElementow - 1; i >=0; i--) {
        for(int j = 0; j < i; j++) {
            if(((dane[j] / wspolczynnikCyfry) % 10) > ((dane[j+1] / wspolczynnikCyfry) % 10)) {
                int temp = dane[j];
                dane[j] = dane[j+1];
                dane[j+1] = temp;

                czyZmiana = true;
            }
        }

        if(!czyZmiana) {
            break;
        }
    }
}

Następnie w głównej funkcji programu używamy sortowania bąbelkowego w sortowaniu pozycyjnym zbioru liczb. Tworzymy pętlę for, która będzie iterować po pozycjach liczb – od pozycji 0 do pozycji równej wartości zapisanej w zmiennej liczbaCyfr. Dla każdej pozycji zostanie wywołana funkcja sortowanieBabelkowe z argumentem równym pozycji sortowanej cyfry.

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

int dane[] = {562, 3, 11, 25, 303, 4, 500};
int liczbaElementow = 7;
int liczbaCyfr = 3;

void sortowanieBabelkowe(int pozycjaCyfry) {

    int wspolczynnikCyfry = pow(10, pozycjaCyfry);

    for(int i = liczbaElementow - 1; i >=0; i--) {
        for(int j = 0; j < i; j++) {
            if(((dane[j] / wspolczynnikCyfry) % 10) > ((dane[j+1] / wspolczynnikCyfry) % 10)) {
                int temp = dane[j];
                dane[j] = dane[j+1];
                dane[j+1] = temp;
            }
        }
    }
}
int main() {

    for(int numerCyfry = 0; numerCyfry < liczbaCyfr; numerCyfry++){
        sortowanieBabelkowe(numerCyfry);
    }

    return 0;
}

Na koniec wyświetlamy posortowaną tablicę. Tak wygląda skończony kod programu sortującego zbiór liczb algorytmem sortowania pozycyjnego:

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

int dane[] = {562, 3, 11, 25, 303, 4, 500};
int liczbaElementow = 7;
int liczbaCyfr = 3;

void sortowanieBabelkowe(int pozycjaCyfry) {

    int wspolczynnikCyfry = pow(10, pozycjaCyfry);

    for(int i = liczbaElementow - 1; i >=0; i--) {
        for(int j = 0; j < i; j++) {
            if(((dane[j] / wspolczynnikCyfry) % 10) > ((dane[j+1] / wspolczynnikCyfry) % 10)) {
                int temp = dane[j];
                dane[j] = dane[j+1];
                dane[j+1] = temp;
            }
        }
    }
}
int main() {

    for(int numerCyfry = 0; numerCyfry < liczbaCyfr; numerCyfry++){
        sortowanieBabelkowe(numerCyfry);
    }
    for(int i = 0; i < liczbaElementow; i++){
        cout << dane[i] << " ";
    }

    return 0;
}

Algorytm sortowania bąbelkowego nie jest wykorzystywany w praktyce przy implementacji sortowania pozycyjnego z powodu jego kwadratowej złożoności czasowej. Program, który przeanalizowaliśmy, jest przykładowy, został przedstawiony w celu poznania możliwości sortowania pozycyjnego. Częściej wykorzystuje się inne algorytmy, np. sortowanie kubełkowesortowanie kubełkowesortowanie kubełkowe, czy sortowanie przez zliczanie, którego główną zaletą jest liniowa złożoność czasowa $O(n+k)$, gdzie $n$ to liczebność sortowanego zbioru, a $k$ to rozpiętość danych. W przypadku sortowania przez zliczanie użytego w algorytmie sortowania pozycyjnego rozpiętość danych nie jest duża (sortujemy liczby dziesiętne, więc na każdej pozycji sortujemy liczby z zakresu 0–9).

Słownik