radix rendezés

Üdvözlöm, Ön a radix rendezés szó jelentését keresi. A DICTIOUS-ban nem csak a radix rendezés szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a radix rendezés szót egyes és többes számban mondani. Minden, amit a radix rendezés szóról tudni kell, itt található. A radix rendezés szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Aradix rendezés és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Kiejtés

  • IPA:

Főnév

radix rendezés

  1. (matematika) A Radix Sort egy nem összehasonlításos rendezési algoritmus, amely a számokat helyiértékük alapján rendezi. Ez egy stabil algoritmus, amely általában egész számok vagy sztringek rendezésére használható.



Elmélet

  1. Helyiérték szerinti rendezés:
    • A számokat az egyes helyiértékek szerint rendezzük, kezdve a legkevésbé jelentős helyiértéktől (pl. egyesek helye) a legjelentősebb helyiértékig (pl. ezresek helye).
  2. Alapművelet (Counting Sort):
    • Egy stabil, helyi rendező algoritmust, például Counting Sortot, alkalmazunk az egyes helyiértékekre.
  3. Hatékonyság:
    • A számok maximális hossza ((d)) határozza meg az iterációk számát.
    • Az egyes iterációk során a rendezés (O(n))-ben történik.
    • Összesen: (O(d n)).
  4. Feltételek:
    • A bemeneti elemeknek diszkrét (pl. számjegyek) helyiértékekkel kell rendelkezniük.



Pszeudokód

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.)

Counting Sort (Radix Sort segédalgoritmusaként)

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

Python implementáció

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: 

C++ implementáció

#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

Összegzés

  • Előnyök:
    • (O(n d)) időkomplexitás, ami gyors lehet bizonyos esetekben.
    • Stabil algoritmus.
  • Hátrányok:
    • Csak egész számokra vagy fix formátumú sztringekre működik.
    • Extra memóriaigény ((O(n))).

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).

Fordítások