Warning: Use of undefined constant JMF_THEMER_MODE - assumed 'JMF_THEMER_MODE' (this will throw an Error in a future version of PHP) in /informatyka/plugins/system/djjquerymonster/djjquerymonster.php on line 210
Porządkowanie przez zliczanie (counting sort)
Drukuj

 

Opis programu

Kod programu:


#include <iostream>
using namespace std;

const int N = 10; //ilość liczb do posortowania
const int MAX_DANA = 20; //każda liczba do posortowania mieści się w zakresie od 0 do 99

int liczby[N]; //tablica dla liczb do posortowania (w podręczniku nazywa się a[N])

// funkcja wprowadzająca do programu liczby do posortowania
void wprowadzDane()
{
	int i;
	cout << "\nSortowanie przez zliczania - wersja podrecznikowa, str 101-102\n";
	cout << "\nIlosc liczb do posortowania: " << N;
	cout << "\nLiczby do posortowania musza byc w przedziale od 0 do " << MAX_DANA << "\n";
	// pętla wprowadzająca liczby do posortowania
	for (i = 0; i < N; i++)
	{
		cout << "podaj liczbe nr " << i << " (z przedzialu od 0 do " << MAX_DANA << " ): ";
		cin >> liczby[i];
		//jeśli podano liczbę ujemną, to wstawi się 0
		if (liczby[i] < 0) liczby[i] = 0; 
		//jeśli podano liczbę większą od maksymalnej, to wstawi się ta maksymalna
		if (liczby[i] > MAX_DANA) liczby[i] = MAX_DANA; 
	}
}

//funkcja sortująca
void sortZlicz()
{
	//tablica liczników poszczególnych liczb
	int licznik[MAX_DANA + 1] = {}; //na początku wszędzie jest 0
	int i, j;	
	//w pętli zwiększamy licznik wystąpień każdej liczby
	for (i = 0; i < N; i++) licznik[liczby[i]]++;
	int poz = 0;
	//układanie liczb zgodnie z kolejnością i ilością powtórzeń
	for (i = 0; i <= MAX_DANA; i++)
	{
		for (j = 0; j < licznik[i]; j++) liczby[poz++] = i;
	}
}
// funkcja wyświetlająca wyniki
void wyprowadzDane(){
	cout << "\n\nLiczby posortowane rosnaco algorytmem \"przez zliczanie\"\n";
	for (int i = 0; i < N; i++) cout << liczby[i] << " ";
}

int main() {
	wprowadzDane();
	sortZlicz();
	wyprowadzDane();
	return 0;
}

Użycie kodu: