RadixSort(A, d): az A tömb legnagyobb számjegyű elemének számjegyhosszát vegyük d-nek helyiértékrend = 1 amíg helyiértékrend ≤ d: CountingSort(A, helyiértékrend) növeld a helyiértékrendet (tízesek, százasok stb.)
CountingSort(A, helyiértékrend): hozz létre egy üres tömböt (B) az eredményhez számolj meg minden számjegyet (C) halmozd össze a C tömb értékeit töltsd ki B-t stabil módon másold vissza B tartalmát A-ba
def counting_sort(arr, exp):
n = len(arr)
output = * n # Kimeneti tömb
count = * 10 # Számjegyek számlálása (0–9)
# Számjegyek számlálása a helyiértékenként
for i in range(n):
index = (arr // exp) % 10
count += 1
# Halmozott számlálás
for i in range(1, 10):
count += count
# Kimeneti tömb feltöltése (stabil rendezés)
for i in range(n - 1, -1, -1):
index = (arr // exp) % 10
output - 1] = arr
count -= 1
# Az eredményt visszamásoljuk az eredeti tömbbe
for i in range(n):
arr = output
def radix_sort(arr):
# A legnagyobb elem helyiérték-számítása
max_num = max(arr)
exp = 1 # Kezdő helyiérték (egyesek helye)
# Iterálunk minden helyiértéken
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
# Példa használat
data =
radix_sort(data)
print("Rendezett tömb:", data)
Kimenet:
Rendezett tömb:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Counting Sort a Radix Sorthoz
void countingSort(vector<int>& arr, int exp) {
int n = arr.size();
vector<int> output(n); // Kimeneti tömb
int count = {0}; // Számjegyek számlálása (0–9)
// Számjegyek számlálása a helyiértékenként
for (int i = 0; i < n; i++) {
int index = (arr / exp) % 10;
count++;
}
// Halmozott számlálás
for (int i = 1; i < 10; i++) {
count += count;
}
// Kimeneti tömb feltöltése (stabil rendezés)
for (int i = n - 1; i >= 0; i--) {
int index = (arr / exp) % 10;
output - 1] = arr;
count--;
}
// Az eredményt visszamásoljuk az eredeti tömbbe
for (int i = 0; i < n; i++) {
arr = output;
}
}
// Radix Sort algoritmus
void radixSort(vector<int>& arr) {
// A legnagyobb elem helyiérték-számítása
int max_num = *max_element(arr.begin(), arr.end());
for (int exp = 1; max_num / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
int main() {
vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(data);
cout << "Rendezett tömb: ";
for (int num : data) {
cout << num << " ";
}
cout << endl;
return 0;
}
Kimenet:
Rendezett tömb: 2 24 45 66 75 90 170 802
A Radix Sort különösen hatékony nagy, homogén típusú adathalmazokon (pl. egész számok), de nem olyan rugalmas, mint összehasonlítás-alapú algoritmusok (pl. quicksort).