Przeczytaj

Sortowanie przez zliczanie – algorytm w C++

Do algorytmu sortowania przez zliczanie dostosowanego do pracy z liczbami naturalnymi dodamy funkcjonalność sortowania liczb całkowitych.

Zanim przystąpimy do właściwej implementacji algorytmu, wyszukujemy największą i najmniejszą wartość w zadanym zbiorze.

Przykład 1

Zbiór, który posortujemy, składa się z następujących elementów: {1, -5, -6, 4, 5, 2}. Elementem największym jest 5, a najmniejszym: -6.

Specyfikacja:

Dane:

dane – zbiór elementów do posortowania; tablica liczb całkowitych
liczbaElementow – liczba elementów w zbiorze; liczba naturalna
elementNajmniejszy – minimalna wartość w zbiorze
elementNajwiekszy – maksymalna wartość w zbiorze

Wynik:

dane – posortowana niemalejąco tablica liczb całkowitych

#include <iostream>
#include <climits>

using namespace std;

int main() {
	int liczbaElementow = 6;
	int dane[liczbaElementow] = {1, -5, -6, 4, 5, 2};

	int elementNajmniejszy = dane[0];
	int elementNajwiekszy  = dane[0];

	return 0;
}

Wyszukiwanie najmniejszego i największego elementu zrealizujemy, wykorzystując znany już algorytm.

Iterując po wszystkich elementach tablicy, sprawdzamy, czy aktualnie przetwarzany element jest mniejszy od tego zapisanego w zmiennej elementNajmniejszy. Jeżeli warunek jest prawdziwy, zapisujemy jego wartość do zmiennej elementNajmniejszy.

W drugiej instrukcji warunkowej wykonujemy podobną operację. Sprawdzamy, czy aktualnie przetwarzany element jest większy od zapisanego w zmiennej elementNajwiekszy i odpowiednio nadpisujemy wartość.

#include <iostream>

using namespace std;

int main() {
	int liczbaElementow = 6;
	int dane[liczbaElementow] = {1, -5, -6, 4, 5, 2};

	int elementNajmniejszy = dane[0];
	int elementNajwiekszy  = dane[0];
    
    for(int i = 1; i < liczbaElementow; i++){
        if(dane[i] < elementNajmniejszy){
            elementNajmniejszy = dane[i];
        }
        if(dane[i] > elementNajwiekszy){
            elementNajwiekszy = dane[i];
        }
    }

	return 0;
}

Po wyszukaniu najmniejszego i największego elementu należy zliczyć elementy. Realizację tego kroku zaczniemy od weryfikacji, ile różnych elementów mamy do zliczenia. W tym celu odejmujemy od elementu największego element najmniejszy i dodajemy 1 (tablice w języku C++ indeksujemy od 0).

Przykład 2

Wiemy już, że dla zbioru: {1, -5, -6, 4, 5, 2} elementem największym jest 5, a najmniejszym: -6. Możemy policzyć, że tablica zliczeń będzie składać się z $5 - (-6) + 1 = 12$ elementów.

Na podstawie uzyskanego wyniku, tworzymy tablicę tablicaZliczen, którą zerujemy.

#include <iostream>

using namespace std;

int main() {
	int liczbaElementow = 6;
	int dane[liczbaElementow] = {1, -5, -6, 4, 5, 2};

	int elementNajmniejszy = dane[0];
	int elementNajwiekszy  = dane[0];
    
    for(int i = 1; i < liczbaElementow; i++){
        if(dane[i] < elementNajmniejszy){
            elementNajmniejszy = dane[i];
        }
        if(dane[i] > elementNajwiekszy){
            elementNajwiekszy = dane[i];
        }
    }
    
    int rozpietoscElementow = elementNajwiekszy - elementNajmniejszy + 1;
    int tablicaZliczen[rozpietoscElementow];

    for(int i = 0; i < rozpietoscElementow; i++){
        tablicaZliczen[i] = 0;
    }

	return 0;
}

Następnie zliczamy elementy. W tym celu iterujemy po wszystkich elementach zbioru dane. Wyznaczamy indeks komórki w tablicy tablicaZliczen, której wartość będziemy inkrementować. Odejmujemy od aktualnie przetwarzanej wartości tablicy dane wartość odczytaną ze zmiennej elementNajmniejszy.

Przykład 3

Dla zbioru dane: {1, -5, -6, 4, 5, 2} możemy wygenerować następującą tablicę tablicaZliczen:

Indeks	Jaki klucz reprezentuje	Zawartość `tablicaZliczen[indeks]`
0	-6	1
1	-5	1
2	-4	0
3	-3	0
4	-2	0
5	-1	0
6	0	0
7	1	1
8	2	1
9	3	0
10	4	1
11	5	1

#include <iostream>

using namespace std;

int main() {
	int liczbaElementow = 6;
	int dane[liczbaElementow] = {1, -5, -6, 4, 5, 2};

	int elementNajmniejszy = dane[0];
	int elementNajwiekszy  = dane[0];
    
    for(int i = 1; i < liczbaElementow; i++){
        if(dane[i] < elementNajmniejszy){
            elementNajmniejszy = dane[i];
        }
        if(dane[i] > elementNajwiekszy){
            elementNajwiekszy = dane[i];
        }
    }
    
    int rozpietoscElementow = elementNajwiekszy - elementNajmniejszy + 1;
    int tablicaZliczen[rozpietoscElementow];

    for(int i = 0; i < rozpietoscElementow; i++){
        tablicaZliczen[i] = 0;
    }
    
    for(int i = 0; i < liczbaElementow; i++){
        tablicaZliczen[dane[i] - elementNajmniejszy]++;
    }

	return 0;
}

Następnie, zaczynając od komórki o indeksie 1, sumujemy kolejne elementy tablicaZliczen, dodając do aktualnie zapisanej wartości zawartość komórki o indeksie o jeden mniejszym. Uzyskujemy w ten sposób pozycję, na której powinien zostać umieszczony ostatni element o wskazanym kluczu.

Przykład 4

Po przeprowadzeniu operacji sumowania dla zbioru dane: {1, -5, -6, 4, 5, 2}, otrzymujemy następującą tablicę tablicaZliczen:

Indeks	Jaki klucz reprezentuje	Zawartość `tablicaZliczen[indeks]`
0	-6	1
1	-5	2
2	-4	2
3	-3	2
4	-2	2
5	-1	2
6	0	2
7	1	3
8	2	4
9	3	4
10	4	5
11	5	6

#include <iostream>

using namespace std;

int main() {
	int liczbaElementow = 6;
	int dane[liczbaElementow] = {1, -5, -6, 4, 5, 2};

	int elementNajmniejszy = dane[0];
	int elementNajwiekszy  = dane[0];
    
    for(int i = 1; i < liczbaElementow; i++){
        if(dane[i] < elementNajmniejszy){
            elementNajmniejszy = dane[i];
        }
        if(dane[i] > elementNajwiekszy){
            elementNajwiekszy = dane[i];
        }
    }
    
    int rozpietoscElementow = elementNajwiekszy - elementNajmniejszy + 1;
    int tablicaZliczen[rozpietoscElementow];

    for(int i = 0; i < rozpietoscElementow; i++){
        tablicaZliczen[i] = 0;
    }
    
    for(int i = 0; i < liczbaElementow; i++){
        tablicaZliczen[dane[i] - elementNajmniejszy]++;
    }
    
    for(int i = 1; i < rozpietoscElementow; i++){
        tablicaZliczen[i] = tablicaZliczen[i] + tablicaZliczen[i-1];
    }

	return 0;
}

Następnie tworzymy tablicę wynikową o nazwie tablicaPosortowana. Ma ona długość równą tablicy wejściowej dane. Idąc od ostatniego elementu nieposortowanejsortowanie niestabilnenieposortowanej tablicy dane, odejmujemy wartość odczytaną ze zmiennej elementNajmniejszy. Uzyskujemy w ten sposób indeksElementuWTablicyZliczen.

Odejmując 1 od wartości odczytanej z tablicaZliczen[indeksElementuWTablicyZliczen], otrzymujemy indeksElementuWTablicyPosortowanej – pod tym indeksem zapisujemy wartość odczytaną z tablicy dane do tablicaPosortowana.

Pamiętajmy o dekrementacji wartości w tablicaZliczen.

Program kończymy, wypisując zawartość posortowanejsortowanie stabilneposortowanej tablicy.

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int liczbaElementow znak równości 6 średnik. Linia 7. int dane otwórz nawias kwadratowy liczbaElementow zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 1 przecinek minus 5 przecinek minus 6 przecinek 4 przecinek 5 przecinek 2 zamknij nawias klamrowy średnik. Linia 9. int elementNajmniejszy znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 10. int elementNajwiekszy znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 12. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny elementNajmniejszy zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. elementNajmniejszy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 15. zamknij nawias klamrowy. Linia 16. if otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny elementNajwiekszy zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. elementNajwiekszy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 18. zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 21. int rozpietoscElementow znak równości elementNajwiekszy minus elementNajmniejszy plus 1 średnik. Linia 22. int tablicaZliczen otwórz nawias kwadratowy rozpietoscElementow zamknij nawias kwadratowy średnik. Linia 24. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny rozpietoscElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. tablicaZliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 26. zamknij nawias klamrowy. Linia 28. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. tablicaZliczen otwórz nawias kwadratowy dane otwórz nawias kwadratowy i zamknij nawias kwadratowy minus elementNajmniejszy zamknij nawias kwadratowy plus plus średnik. Linia 30. zamknij nawias klamrowy. Linia 32. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny rozpietoscElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. tablicaZliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości tablicaZliczen otwórz nawias kwadratowy i zamknij nawias kwadratowy plus tablicaZliczen otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 34. zamknij nawias klamrowy. Linia 36. int tablicaPosortowana otwórz nawias kwadratowy liczbaElementow zamknij nawias kwadratowy średnik. Linia 38. for otwórz nawias okrągły int i znak równości liczbaElementow minus 1 ś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 39. int indeksElementuWTablicyZliczen znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy minus elementNajmniejszy średnik. Linia 40. int indeksElementuWTablicyPosortowanej znak równości tablicaZliczen otwórz nawias kwadratowy indeksElementuWTablicyZliczen zamknij nawias kwadratowy minus 1 średnik. Linia 41. tablicaZliczen otwórz nawias kwadratowy indeksElementuWTablicyZliczen zamknij nawias kwadratowy minus minus średnik. Linia 42. tablicaPosortowana otwórz nawias kwadratowy indeksElementuWTablicyPosortowanej zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 43. zamknij nawias klamrowy. Linia 45. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 46. cout otwórz nawias ostrokątny otwórz nawias ostrokątny tablicaPosortowana otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 47. zamknij nawias klamrowy. Linia 49. return 0 średnik. Linia 50. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

int main() {
	int liczbaElementow = 6;
	int dane[liczbaElementow] = {1, -5, -6, 4, 5, 2};

	int elementNajmniejszy = dane[0];
	int elementNajwiekszy  = dane[0];
    
    for(int i = 1; i < liczbaElementow; i++){
        if(dane[i] < elementNajmniejszy){
            elementNajmniejszy = dane[i];
        }
        if(dane[i] > elementNajwiekszy){
            elementNajwiekszy = dane[i];
        }
    }
    
    int rozpietoscElementow = elementNajwiekszy - elementNajmniejszy + 1;
    int tablicaZliczen[rozpietoscElementow];

    for(int i = 0; i < rozpietoscElementow; i++){
        tablicaZliczen[i] = 0;
    }
    
    for(int i = 0; i < liczbaElementow; i++){
        tablicaZliczen[dane[i] - elementNajmniejszy]++;
    }
    
    for(int i = 1; i < rozpietoscElementow; i++){
        tablicaZliczen[i] = tablicaZliczen[i] + tablicaZliczen[i-1];
    }
    
    int tablicaPosortowana[liczbaElementow];

    for(int i = liczbaElementow - 1; i >= 0; i--){
        int indeksElementuWTablicyZliczen = dane[i] - elementNajmniejszy;
        int indeksElementuWTablicyPosortowanej = tablicaZliczen[indeksElementuWTablicyZliczen] - 1;
        tablicaZliczen[indeksElementuWTablicyZliczen]--;
        tablicaPosortowana[indeksElementuWTablicyPosortowanej] = dane[i];
    }

    for(int i = 0; i < liczbaElementow; i++){
        cout << tablicaPosortowana[i] << " ";
    }

	return 0;
}

Słownik

sortowanie niestabilne

sortowanie niezachowujące kolejności występowania elementów w tablicy o tej samej wartości w posortowanej tablicy wynikowej

sortowanie stabilne

sortowanie zachowujące kolejność występowania elementów w tablicy o tej samej wartości w posortowanej tablicy wynikowej

Film samouczek

Sprawdź się

Sortowanie przez zliczanie – algorytm w C++

Słownik