Przeczytaj

Sortowanie kubełkowe

Algorytm sortowania kubełkowego polega na zliczeniu wystąpień danych wartości w tablicy wejściowej, a następnie na wygenerowaniu tablicy wyjściowej, zawierającej dane w odpowiednich kubełkachkubełekkubełkach, posortowane zgodnie z ich liczbą.

Sortowanie liczb całkowitych

Algorytm pozwala sortować liczby całkowite.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów tablicy tabWejsciowa
tabWejsciowa – n‑elementowa tablica, przechowująca liczby całkowite

Wynik:

tabPosortowana – posortowana niemalejąco tablica liczb całkowitych

W algorytmie pod indeksem 0 w tabZliczajaca znajduje się kubełek przeznaczony dla liczb o najmniejszej wartości ze zbioru wejściowego. Natomiast ostatni element tablicy zliczającej staje się kubełkiem do zliczania wartości maksymalnej.

Zaczynamy od znalezienia wartości minimalnej i maksymalnej wśród sortowanych liczb. Wykorzystamy poznany już algorytm, który został zaprezentowany w e‑materiale Sortowanie kubełkowePPpmzST7zSortowanie kubełkowe.

// znajdowanie wartości minimalnej i maksymalnej
int minLiczba = tabWejsciowa[0];
int maxLiczba = tabWejsciowa[0];

for(int i = 1; i < n; i++)
	{
	if(tabWejsciowa[i] < minLiczba)
		minLiczba = tabWejsciowa[i];
	else if(tabWejsciowa[i] > maxLiczba)
		maxLiczba = tabWejsciowa[i];
	}

Kolejnym krokiem jest utworzenie tablicy zliczeń. Rozmiar tablicy zliczającej zapiszemy w zmiennej k. Wyznaczamy go jako różnicę wartości maksymalnej i minimalnej powiększonej o 1: k = maxLiczba - minLiczba + 1. Następnie zerujemy wszystkie jej elementy.

	// przygotowanie tablicy zliczającej
    int k = maxLiczba - minLiczba + 1;
	int tabZliczajaca[k] = {0};

Przykład 1

Na podstawie kilku zbiorów możemy sprawdzić, czy podany wzór na rozmiar tablicy jest poprawny.

Dla zbioru:

{0, 5, 4} – zbiór z liczbami nieujemnymi
max: 5, min: 0
wymagane kubełki: {0, 1, 2, 3, 4, 5}

obliczymy zgodnie z podanym wcześniej wzorem rozmiar tablicy:

$5 - 0 + 1 = 6$

Rzeczywiście liczba wymaganych kubełków zgadza się z otrzymaną długością tablicy.

Dla zbioru:

{-3, -1} – zbiór z liczbami ujemnymi
max: -1, min: -3
wymagane kubełki: {-3, -2, -1}

obliczamy zgodnie z wcześniej podanym wzorem długość tablicy:

$-1 - (-3) + 1 = 3$

Ponownie otrzymaliśmy poprawną długość tablicy, która zgadza się z liczbą wymaganych kubełków.

Dla zbioru:

{0, -1, 2} – zbiór z liczbami dodatnimi i ujemnymi
max: 2, min: -1
wymagane kubełki: {-1, 0, 1, 2}

obliczamy zgodnie z podanym wcześniej wzorem długość tablicy:

$2 - (-1) + 1 = 4$

Po raz kolejny liczba wymaganych kubełków zgadza się z otrzymaną długością tablicy.

Przeglądamy wartości z tablicy wejściowej i zapisujemy ich wystąpienia w tablicy zliczeń. Indeks licznika dla danej wartości wyliczamy jako różnicę tej wartości i wartości minimalnej.

for(int i = 0; i < n; i++)
{
    int wartosc = tabWejsciowa[i];
    tabZliczajaca[wartosc - minLiczba]++;
}

Przykład 2

Zbiór posiada elementy: {-5, 0, 2}, sprawdźmy, pod jakim indeksem będą one zliczane.

minLiczba = -5
maxLiczba = 2
k = 2 - (-5) + 1 = 8
tabZliczajaca[k] = {0, 0, 0, 0, 0, 0, 0, 0}

Indeks dla wartości -5 obliczamy w następujący sposób: -5 - (-5) = 0. Najmniejsza wartość będzie zliczana w komórce o indeksie 0.

Indeks dla wartości 2 wynosi: 2 - (-5) = 7. Największa wartość będzie zliczana w komórce o indeksie 7.

Następnie do tablicy wyjściowej dopisujemy odpowiednią liczbę wystąpień zliczonych wartości. Do tablicy zapisujemy indeks powiększony o wartość minLiczba. Jest to operacja odwrotna do wcześniejszej, kiedy indeks w tablicy zliczeń wyliczaliśmy jako pomniejszenie zliczanej wartości o wartość minLiczba.

	int tabPosortowana[n];
	int j = 0;
	for(int i = 0; i < k; i++)
	{
		while(tabZliczajaca[i] > 0)
		{
			tabPosortowana[j] = i + minLiczba;
			tabZliczajaca[i]--;
			j++;
		}
	}

Już wiesz

Ze względu na numerowanie komórek tablicy zliczającej od 0:

indeks wartości zliczanej ustalamy, korzystając ze wzoru: indeks = wartość - wartość_minimalna,
zliczaną wartość wyznaczamy zgodnie ze wzorem: wartość = indeks + wartość_minimalna.

Cały kod prezentuje się następująco:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny climits zamknij nawias ostrokątny. Linia 4. using namespace std średnik. Linia 6. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 7. otwórz nawias klamrowy. Linia 8. int tabWejsciowa otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 3 przecinek 2 przecinek 3 przecinek 4 przecinek minus 4 przecinek 2 przecinek 3 przecinek 2 przecinek 0 przecinek minus 5 zamknij nawias klamrowy średnik. Linia 9. int n znak równości 10 średnik. Linia 11. prawy ukośnik prawy ukośnik znajdowanie wartości minimalnej i maksymalnej. Linia 12. int minLiczba znak równości tabWejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 13. int maxLiczba znak równości tabWejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 15. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły. Linia 16. otwórz nawias klamrowy. Linia 17. if otwórz nawias okrągły tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny minLiczba zamknij nawias okrągły. Linia 18. minLiczba znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 19. else if otwórz nawias okrągły tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny maxLiczba zamknij nawias okrągły. Linia 20. maxLiczba znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 21. zamknij nawias klamrowy. Linia 23. prawy ukośnik prawy ukośnik przygotowanie tablicy zliczającej. Linia 24. int k znak równości maxLiczba minus minLiczba plus 1 średnik. Linia 25. int tabZliczajaca otwórz nawias kwadratowy k zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 0 zamknij nawias klamrowy średnik. Linia 27. prawy ukośnik prawy ukośnik zliczanie wartości. Linia 28. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły. Linia 29. otwórz nawias klamrowy. Linia 30. int wartosc znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 31. tabZliczajaca otwórz nawias kwadratowy wartosc minus minLiczba zamknij nawias kwadratowy plus plus średnik. Linia 32. zamknij nawias klamrowy. Linia 34. prawy ukośnik prawy ukośnik porządkowanie. Linia 35. int tabPosortowana otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 36. int j znak równości 0 średnik. Linia 37. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny k średnik i plus plus zamknij nawias okrągły. Linia 38. otwórz nawias klamrowy. Linia 39. while otwórz nawias okrągły tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 zamknij nawias okrągły. Linia 40. otwórz nawias klamrowy. Linia 41. tabPosortowana otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości i plus minLiczba średnik. Linia 42. tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy minus minus średnik. Linia 43. j plus plus średnik. Linia 44. zamknij nawias klamrowy. Linia 45. zamknij nawias klamrowy. Linia 47. prawy ukośnik prawy ukośnik wypisanie uporządkowanych wartości. Linia 48. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły. Linia 49. otwórz nawias klamrowy. Linia 50. cout otwórz nawias ostrokątny otwórz nawias ostrokątny tabPosortowana otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 51. zamknij nawias klamrowy. Linia 53. return 0 średnik. Linia 54. zamknij nawias klamrowy.

#include <iostream>
#include <climits>

using namespace std;

int main()
{
	int tabWejsciowa[] = {3, 2, 3, 4, -4, 2, 3, 2, 0, -5};
	int n = 10;

    // znajdowanie wartości minimalnej i maksymalnej
    int minLiczba = tabWejsciowa[0];
    int maxLiczba = tabWejsciowa[0];

    for(int i = 1; i < n; i++)
        {
        if(tabWejsciowa[i] < minLiczba)
            minLiczba = tabWejsciowa[i];
        else if(tabWejsciowa[i] > maxLiczba)
            maxLiczba = tabWejsciowa[i];
        }

	// przygotowanie tablicy zliczającej
    int k = maxLiczba - minLiczba + 1;
	int tabZliczajaca[k] = {0};

	// zliczanie wartości
    for(int i = 0; i < n; i++)
    {
        int wartosc = tabWejsciowa[i];
        tabZliczajaca[wartosc - minLiczba]++;
    }

	// porządkowanie
	int tabPosortowana[n];
	int j = 0;
	for(int i = 0; i < k; i++)
	{
		while(tabZliczajaca[i] > 0)
		{
			tabPosortowana[j] = i + minLiczba;
			tabZliczajaca[i]--;
			j++;
		}
	}

	// wypisanie uporządkowanych wartości
	for(int i = 0; i<n; i++)
	{
		cout << tabPosortowana[i] << " ";
	}

return 0;
}

Wynikiem algorytmu jest posortowana tablica: {-5 -4 0 2 2 2 3 3 3 4}.

Ważne!

Korzystamy z maxLiczba - minLiczba + 1 komórek pamięci.

Algorytm ma więc złożoność pamięciową O(max - min + 1).

Sortowanie liczb rzeczywistych

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów tablicy tabWejsciowa
tabWejsciowa – n‑elementowa tablica, przechowująca liczby rzeczywiste

Wynik:

tabWejsciowa – posortowana niemalejąco tablica liczb rzeczywistych

Liczby rzeczywiste również mogą być porządkowane z użyciem algorytmu sortowania kubełkowego. Będzie się on jednak różnił od dotychczas przedstawionego.

W przypadku algorytmu dla liczb całkowitych każda liczba ma własny osobny kubełek, który zawiera licznik jej wystąpień. Natomiast podczas sortowania liczb rzeczywistych kubełki są przedziałami, do których trafiają liczby należące do danego przedziału. Przedziały mogą być wyznaczane dowolnie, jednak wymaga to odpowiedniego dostosowania algorytmu.

W implementacji wykorzystamy taką samą liczbę kubełków (przedziałów), jak w wersji algorytmu dla liczb całkowitych. Wartości, które trafią do danego kubełka, będą się mieścić w przedziałach [x, x + 1) dla liczb nieujemnych i (x - 1, x] dla liczb ujemnych. Np. liczba 3.7 trafi do kubełka reprezentującego przedział [3, 4), a liczba -4.2 do przedziału (-5, -4].

Przeanalizujmy program, który wyszukuje wartość minimalną i maksymalną, przygotowuje tablicę zliczającą, zapisuje kolejne wartości w odpowiednich kubełkach i drukuje ich zawartość.

#include <iostream>
#include <climits>
#include <vector>

using namespace std;

void wyswietlTablice(vector<float>* tab, int k) {
 	for (int i = 0; i < k; i++)
	{
		if (!tab[i].empty())
		{
			cout << "Kubełek numer " << i <<" : ";
			for (int j = 0; j < (int)tab[i].size(); j++)
			{
				cout << tab[i].at(j) << "; ";
			}
			cout << endl;
		}
	}
    cout << endl;
}

int main()
{
	float tabWejsciowa[] = { 3.5, -4.2, 3.2, 4, -4, 2, 3.9, 2, 0, -5.5 };
	int n = 10;

    int minLiczba = tabWejsciowa[0];
    int maxLiczba = tabWejsciowa[0];

    for(int i = 1; i < n; i++)
        {
        if(tabWejsciowa[i] < minLiczba)
            minLiczba = tabWejsciowa[i];
        else if(tabWejsciowa[i] > maxLiczba)
            maxLiczba = tabWejsciowa[i];
        }

	const int k = maxLiczba - minLiczba + 1;
	vector<float> *tabZliczajaca = new vector<float>[k];

	// zliczanie wartości
	for (int i = 0; i < n; i++)
	{
		float wartosc = tabWejsciowa[i];
		int indeksKubelka = (int)wartosc - (int)minLiczba;
		tabZliczajaca[indeksKubelka].push_back(wartosc);
	}

	// wypisanie tabZliczajaca
 	wyswietlTablice(tabZliczajaca, k);

	delete[] tabZliczajaca;
	return 0;
}

Elementami tablicy zliczającej są tablice dynamiczne typu vector. Używamy takich tablic jako kubełków, ponieważ nie wiemy, ile wartości do nich trafi. Tablice tego typu umożliwiają zastosowanie wielu użytecznych metod ułatwiających dodawanie i przeglądanie elementów.

Zwróćmy uwagę na kilka fragmentów kodu:

vector – utworzenie tablicy tabZliczajaca, której elementami jest k tablic pozwalających przechowywać wartości typu float,
if (!tablicaWektorow[i].empty()) – metoda empty() zwraca prawdę, jeżeli tablica jest pusta, dzięki temu sprawdzamy, czy kubełek zawiera jakieś liczby,
tablicaWektorow[i].at(j) – z kubełka o indeksie i przy użyciu metody at() odczytujemy element o indeksie j,
delete[] tabZliczajaca; – usuwamy tablicę z pamięci.

W pętli umieszczającej liczby w odpowiednich kubełkach:

	for (int i = 0; i < n; i++)
	{
		float wartosc = tabWejsciowa[i];
		int indeksKubelka = (int)wartosc - (int)minLiczba;
		tabZliczajaca[indeksKubelka].push_back(wartosc);
	}

Odczytane z tablicy wejściowej wartości oraz wartość minimalną konwertujemy na liczby całkowite, co powoduje ich ewentualne zaokrąglenie. Np. dla wartości 3.2 i 3.9 po konwersji otrzymamy 3, dla wartości -2.2 i -2.9 otrzymamy -2.

Następnie indeks kubełka, do którego trafi liczba, wyznaczamy podobnie jak w przypadku algorytmu dla liczb całkowitych: indeksKubelka = (int)wartosc - (int)minLiczba.

Do posortowania zawartości poszczególnych kubełków użyjemy sortowania bąbelkowegoP77EQCGCtsortowania bąbelkowego. Elementy kubełków zostaną posortowane w porządku nierosnącym za pomocą funkcji sortowanieBabelkowe().

void sortowanieBabelkowe(vector<float>& tab)
{
	for (int j = tab.size() - 1; j > 0; j--)
		for (int i = 0; i < j; i++) {
			if (tab[i] < tab[i + 1]) {
				float tmp = tab[i];
				tab[i] = tab[i + 1];
				tab[i + 1] = tmp;
			}
		}
}

Wywołanie funkcji sortującej umieścimy w pętli:

	for (int i = 0; i < k; i++)
	{
		if (!tabZliczajaca[i].empty())
		{
			sortowanieBabelkowe(tabZliczajaca[i]);
		}
	}

Kolejnym krokiem jest przepisanie elementów do tablicy wejściowej. Po kolei odczytujemy kubełki z tablicy zliczającej i przepisujemy zawarte w nich liczby do tablicy wyjściowej, zaczynając od ostatniej, czyli najmniejszej:

	int j = 0;
	for (int i = 0; i < k; i++)
	{
		while (!tabZliczajaca[i].empty())
		{
			tabWejsciowa[j] = tabZliczajaca[i].back();
			tabZliczajaca[i].pop_back();
			j++;
		}
	}

Metoda back() pozwala na odczytanie ostatniego elementu tablicy typu vector, a metoda pop_back() usuwa ostatni element takiej tablicy.

Na koniec wypisujemy tablicę wejściową:

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

Cały kod prezentuje się następująco:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny climits zamknij nawias ostrokątny. Linia 3. kratka include otwórz nawias ostrokątny vector zamknij nawias ostrokątny. Linia 5. using namespace std średnik. Linia 7. void sortowanieBabelkowe otwórz nawias okrągły vector otwórz nawias ostrokątny float zamknij nawias ostrokątny ampersant tab zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy. Linia 9. for otwórz nawias okrągły int j znak równości tab kropka size otwórz nawias okrągły zamknij nawias okrągły minus 1 średnik j zamknij nawias ostrokątny 0 średnik j minus minus zamknij nawias okrągły. Linia 10. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny j średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. if otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny tab otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. float tmp znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 13. tab otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy średnik. Linia 14. tab otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy znak równości tmp średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 19. void wyswietlTablice otwórz nawias okrągły vector otwórz nawias ostrokątny float zamknij nawias ostrokątny asterysk tab przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny k średnik i plus plus zamknij nawias okrągły. Linia 21. otwórz nawias klamrowy. Linia 22. if otwórz nawias okrągły wykrzyknik tab otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka empty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 23. otwórz nawias klamrowy. Linia 24. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Kubełek numer cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny i otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów średnik. Linia 25. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka size otwórz nawias okrągły zamknij nawias okrągły średnik j plus plus zamknij nawias okrągły. Linia 26. otwórz nawias klamrowy. Linia 27. cout otwórz nawias ostrokątny otwórz nawias ostrokątny tab otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka at otwórz nawias okrągły j zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów średnik cudzysłów średnik. Linia 28. zamknij nawias klamrowy. Linia 29. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 32. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 33. zamknij nawias klamrowy. Linia 35. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 36. otwórz nawias klamrowy. Linia 37. float tabWejsciowa otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 3 kropka 5 przecinek minus 4 kropka 2 przecinek 3 kropka 2 przecinek 4 przecinek minus 4 przecinek 2 przecinek 3 kropka 9 przecinek 2 przecinek 0 przecinek minus 5 kropka 5 zamknij nawias klamrowy średnik. Linia 38. int n znak równości 10 średnik. Linia 40. prawy ukośnik prawy ukośnik znajdowanie wartości minimalnej i maksymalnej. Linia 41. int minLiczba znak równości tabWejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 42. int maxLiczba znak równości tabWejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 44. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły. Linia 45. otwórz nawias klamrowy. Linia 46. if otwórz nawias okrągły tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny minLiczba zamknij nawias okrągły. Linia 47. minLiczba znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 48. else if otwórz nawias okrągły tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny maxLiczba zamknij nawias okrągły. Linia 49. maxLiczba znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 50. zamknij nawias klamrowy. Linia 52. const int k znak równości maxLiczba minus minLiczba plus 1 średnik. Linia 53. vector otwórz nawias ostrokątny float zamknij nawias ostrokątny asterysk tabZliczajaca znak równości new vector otwórz nawias ostrokątny float zamknij nawias ostrokątny otwórz nawias kwadratowy k zamknij nawias kwadratowy średnik. Linia 55. prawy ukośnik prawy ukośnik zliczanie wartości. Linia 56. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły. Linia 57. otwórz nawias klamrowy. Linia 58. float wartosc znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 59. int indeksKubelka znak równości otwórz nawias okrągły int zamknij nawias okrągły wartosc minus otwórz nawias okrągły int zamknij nawias okrągły minLiczba średnik. Linia 60. tabZliczajaca otwórz nawias kwadratowy indeksKubelka zamknij nawias kwadratowy kropka push podkreślnik back otwórz nawias okrągły wartosc zamknij nawias okrągły średnik. Linia 61. zamknij nawias klamrowy. Linia 63. prawy ukośnik prawy ukośnik wypisanie tabZliczajaca. Linia 64. wyswietlTablice otwórz nawias okrągły tabZliczajaca przecinek k zamknij nawias okrągły średnik. Linia 66. prawy ukośnik prawy ukośnik sortowanie kubełków. Linia 67. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny k średnik i plus plus zamknij nawias okrągły. Linia 68. otwórz nawias klamrowy. Linia 69. if otwórz nawias okrągły wykrzyknik tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka empty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 70. otwórz nawias klamrowy. Linia 71. sortowanieBabelkowe otwórz nawias okrągły tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 72. zamknij nawias klamrowy. Linia 73. zamknij nawias klamrowy. Linia 75. prawy ukośnik prawy ukośnik wypisanie tabZliczajaca. Linia 76. wyswietlTablice otwórz nawias okrągły tabZliczajaca przecinek k zamknij nawias okrągły średnik. Linia 78. prawy ukośnik prawy ukośnik przepisanie elementów do tablicy wejściowej. Linia 79. int j znak równości 0 średnik. Linia 80. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny k średnik i plus plus zamknij nawias okrągły. Linia 81. otwórz nawias klamrowy. Linia 82. while otwórz nawias okrągły wykrzyknik tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka empty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 83. otwórz nawias klamrowy. Linia 84. tabWejsciowa otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka back otwórz nawias okrągły zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik odczytanie ostatniego elementu. Linia 85. tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik usunięcie ostatniego elementu. Linia 86. j plus plus średnik. Linia 87. zamknij nawias klamrowy. Linia 88. zamknij nawias klamrowy. Linia 90. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły. Linia 91. otwórz nawias klamrowy. Linia 92. cout otwórz nawias ostrokątny otwórz nawias ostrokątny tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 93. zamknij nawias klamrowy. Linia 95. delete otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca średnik. Linia 96. return 0 średnik. Linia 97. zamknij nawias klamrowy.

#include <iostream>
#include <climits>
#include <vector>

using namespace std;

void sortowanieBabelkowe(vector<float>& tab)
{
	for (int j = tab.size() - 1; j > 0; j--)
		for (int i = 0; i < j; i++) {
			if (tab[i] < tab[i+1]) {
				float tmp = tab[i];
				tab[i] = tab[i+1];
				tab[i+1] = tmp;
			}
		}
}

void wyswietlTablice(vector<float>* tab, int k) {
 	for (int i = 0; i < k; i++)
	{
		if (!tab[i].empty())
		{
			cout << "Kubełek numer " << i <<" : ";
			for (int j = 0; j < (int)tab[i].size(); j++)
			{
				cout << tab[i].at(j) << "; ";
			}
			cout << endl;
		}
	}
    cout << endl;
}

int main()
{
	float tabWejsciowa[] = { 3.5, -4.2, 3.2, 4, -4, 2, 3.9, 2, 0, -5.5 };
	int n = 10;

	// znajdowanie wartości minimalnej i maksymalnej
    int minLiczba = tabWejsciowa[0];
    int maxLiczba = tabWejsciowa[0];

    for(int i = 1; i < n; i++)
        {
        if(tabWejsciowa[i] < minLiczba)
            minLiczba = tabWejsciowa[i];
        else if(tabWejsciowa[i] > maxLiczba)
            maxLiczba = tabWejsciowa[i];
        }

	const int k = maxLiczba - minLiczba + 1;
	vector<float> *tabZliczajaca = new vector<float>[k];

	// zliczanie wartości
	for (int i = 0; i < n; i++)
	{
		float wartosc = tabWejsciowa[i];
		int indeksKubelka = (int)wartosc - (int)minLiczba;
		tabZliczajaca[indeksKubelka].push_back(wartosc);
	}

	// wypisanie tabZliczajaca
	wyswietlTablice(tabZliczajaca, k);

	// sortowanie kubełków
	for (int i = 0; i < k; i++)
	{
		if (!tabZliczajaca[i].empty())
		{
			sortowanieBabelkowe(tabZliczajaca[i]);
		}
	}

	// wypisanie tabZliczajaca
	wyswietlTablice(tabZliczajaca, k);

	// przepisanie elementów do tablicy wejściowej
	int j = 0;
	for (int i = 0; i < k; i++)
	{
		while (!tabZliczajaca[i].empty())
		{
			tabWejsciowa[j] = tabZliczajaca[i].back(); //odczytanie ostatniego elementu
			tabZliczajaca[i].pop_back(); //usunięcie ostatniego elementu
			j++;
		}
	}

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

	delete[] tabZliczajaca;
return 0;
}

W programie umieściliśmy dodatkowe wywołanie funkcji wypisującej kubełki (tablicę zliczającą), aby pokazać wynik działania funkcji sortowanieBabelkowe().

Po uruchomieniu programu powinniśmy zobaczyć następujące komunikaty:

Kubełek numer 0 : -5.5;
Kubełek numer 1 : -4.2; -4;
Kubełek numer 5 : 0;
Kubełek numer 7 : 2; 2;
Kubełek numer 8 : 3.5; 3.2; 3.9;
Kubełek numer 9 : 4;

Kubełek numer 0 : -5.5;
Kubełek numer 1 : -4; -4.2;
Kubełek numer 5 : 0;
Kubełek numer 7 : 2; 2;
Kubełek numer 8 : 3.9; 3.5; 3.2;
Kubełek numer 9 : 4;

-5.5  -4.2  -4  0  2  2  3.2  3.5  3.9  4

Słownik

indeks tablicy

numer, dzięki któremu możemy odnieść się do konkretnego elementu w tej tablicy

kubełek

komórka w pamięci, obiekt, czy innego rodzaju struktura, identyfikowana jednoznacznie poprzez unikalną cechę sortowanego zbioru (w przypadku tablicy liczb każdy kubełek identyfikowany byłby unikalną liczbą), w których zliczamy liczbę wystąpień elementów, zawierających daną cechę

typ całkowitoliczbowy

typ prymitywny, w którym nie ma wartości po przecinku; może przechowywać jedynie wartości całkowitoliczbowe, w tym wartości ujemne

Film samouczek

Sprawdź się

Sortowanie kubełkowe

Sortowanie liczb całkowitych

Sortowanie liczb rzeczywistych

Słownik