Sortowanie pozycyjne liczb

W tej sekcji zrealizujemy algorytm sortowania pozycyjnego z wykorzystaniem innego stabilnego algorytmu sortowaniasortowanie stabilnestabilnego algorytmu sortowania. Będzie to sortowanie bąbelkowesortowanie bąbelkowesortowanie bąbelkowe, które zostało omówione w e‑materiale Sortowanie bąbelkowe w języku JavaPxgkD2R5YSortowanie bąbelkowe w języku Java.

Specyfikacja:

Dane:

• A – jednowymiarowa tablica liczb naturalnych; dane do posortowania

Wynik:

• A – jednowymiarowa tablica liczb naturalnych; posortowane niemalejąco liczby naturalne

Przeanalizujmy przykład przedstawiający zasadę działania algorytmu.

Przykład 1

Naszym zadaniem jest posortowanie niemalejąco zbioru pięciu liczb trzycyfrowych.

$$A=\{534,123,452,897,342\}$$

Najpierw, używając dowolnego stabilnego algorytmu sortowania, sortujemy niemalejąco elementy zbioru A, uwzględniając tylko cyfry na pozycji jedności. Potem powtarzamy operację na zmodyfikowanym już zbiorze A, sortując po cyfrach dziesiątek, a następnie setek itd. Grafika przedstawia, jak wygląda zbiór po kolejnych sortowaniach.

RDTnKtjaIV6kv

Ilustracja przedstawia cztery zbiory liczb.
Pierwszy z liczbami nieposortowanymi: 534, 123, 452, 897, 347.
Drugi z liczbami posortowanymi po cyfrach jedności: 452, 342, 123, 534, 897.
Liczby jedności zaznaczono czerwonym kolorem.
Trzeci z liczbami posortowanymi po liczbach dziesiątek: 123, 534, 342, 352, 897.
Liczby dziesiątek zaznaczono kolorem żółtym.
Czwarty z liczbami posortowanymi po liczbach setek czego wynikiem jest całkowicie posortowany zbiór rosnąco: 123, 342, 452, 534, 897.
Liczby setek zaznaczono kolorem zielonym.

Implementacja w języku Java

Teraz możemy przejść do implementacji algorytmu w języku Java. Naszym celem jest napisanie programu, który umożliwi posortowanie dowolnego zbioru liczb naturalnych za pomocą algorytmu sortowania pozycyjnego. Jako pomocniczego stabilnego algorytmu sortowania użyjemy algorytmu sortowania bąbelkowego.

Finalny program ma sortować zadany zbiór liczb pozycyjnie – od pozycji najmniej znaczącej, czyli jedności, do pozycji najbardziej znaczącej. W związku z tym należy napisać funkcję, która znajdzie i zwróci największą liczbę w zadanym zbiorze. Nazwijmy tę funkcję znajdzMax().

static int znajdzMax(int[] tab) {
	int max = tab[0];

	for(int i = 0; i < tab.length; i++) {
		if(tab[i] > max) {
			max = tab[i];
		}
	}

	return max;
}

Przyjmuje ona jeden parametr – int[] tab – czyli tablicę zawierającą zbiór liczb naturalnych. To z tego zbioru ma zostać wybrana największa liczba.

Następnie przejdźmy do zadeklarowania kolejnej funkcji – sortowaniePozycyjne(), która będzie odpowiadać za realizację sortowań dla kolejnych pozycji, począwszy od pozycji jedności.

static void sortowaniePozycyjne(int tab[]) {  
	int max = znajdzMax(tab); 

	for (int poz = 1; max/poz > 0; poz *= 10) {
		sortowanieBabelkowe(tab, poz);
	}
}

Za pomocą wcześniej utworzonej funkcji znajdzMax(), szukamy największej liczby w zadanym zbiorze do posortowania i zapisujemy ją do zmiennej max.

Następnie deklarujemy pętlę for, która wykona tyle iteracjiiteracjaiteracji, ile posiada cyfr największa liczba ze zbioru. Liczba iteracji jest określona poprzez dzielenie liczby max przez kolejne wielokrotności liczby 10 (oprócz pierwszej iteracji).

Dla cyfr na kolejnych pozycjach (najpierw dla jedności, potem dla dziesiątek, setek itd.) następują wywołania funkcji sortowanieBabelkowe().

Funkcja sortowanieBabelkowe() ma za zadanie sortować zbiór liczb według określonej jako parametr pozycji – pozycja.

static void sortowanieBabelkowe(int[] tab, int pozycja) {
	int temp;

	for(int i = 0; i < tab.length; i++) {
		for(int j = 0; j < tab.length - 1; j++) {
			if(((tab[j] / pozycja) % 10) > ((tab[j+1] / pozycja) % 10)) {
				temp = tab[j];
				tab[j] = tab[j+1];
				tab[j+1] = temp;
			}
		}
	}
}

static void sortowanieBabelkowe(int[] tab, int pozycja) {
	int temp;
	boolean czyZmiana = false;

	for(int i = 0; i < tab.length; i++) {
		for(int j = 0; j < tab.length - 1; j++) {
			if(((tab[j] / pozycja) % 10) > ((tab[j+1] / pozycja) % 10)) {
				temp = tab[j];
				tab[j] = tab[j+1];
				tab[j+1] = temp;

				czyZmiana = true;
			}
		}

		if(czyZmiana == false) {
			break;
		}
	}
}

Następnie należy utworzyć dane testowe – zbiór liczb do posortowania oraz wywołać funkcję sortowania pozycyjnego dla zadeklarowanego zbioru:

public static void main(String[] args) {
	int zbior[] = {534, 123, 452, 897, 342}; 
	sortowaniePozycyjne(zbior); 

	for(int i = 0; i < zbior.length; i++) {
		System.out.print(zbior[i] + " ");
	}
}

Ostatnia pętla służy do wypisania posortowanego już zbioru liczb. Wynik sortowania jest poprawny:

123 342 452 534 897

Sprawdźmy, czy nasz algorytm sortowania pozycyjnego działa poprawnie – tzn. czy po kolejnych wywołaniach sortowania bąbelkowego zbiór liczb jest sortowany według odpowiednich pozycji. Wypisywanie kolejnych elementów tablicy zostanie dodane w funkcji sortowaniePozycyjne().

static void sortowaniePozycyjne(int tab[]) {  
	int max = znajdzMax(tab); 

	for (int poz = 1; max/poz > 0; poz *= 10) {
		sortowanieBabelkowe(tab, poz);
		
		for(int i = 0; i < tab.length; i++) {
			System.out.print(tab[i] + " ");
		}
		
		System.out.println();
	}
}

Po uruchomieniu programu wypisywane są następujące wyniki:

452 342 123 534 897 
123 534 342 452 897 
123 342 452 534 897

Cały kod programu do przetestowania wygląda następująco:

Słownik