Urejanje po delih (radix sort)


Glavna stran

Splošno

Algoritmi urejanja po delih (radix-sort) so zasnovani na abstraktnih operacijah "izvleci i-to cifro iz ključa". Na srečo Java omogoča nizko-nivojske operatorje, ki omogočajo enostavno in učinkovito implementacijo take operacije. To dejstvo je pomembno, ker so nekateri jeziki (Pascal), zato da bi nas naučili pisanja programov, ki so neodvisni od sistema, namerno otežili pisanje programov, ki so odvisni od tega, kako določena naprava predstavlja števila. V takšnih programskih jezikih je bilo težko implementirati tehnike bit-za-bitom, ki pravzaprav ustreza večini računalnikov. Urejanj po delih je bilo nekaj časa žrtev te "napredne" filozofije. Toda razvijalci programskih jezikov C, C++ in Jave so spoznali, da je direktna manipulacija z biti pogosto uporabna in bi lahko uporabili prednosti nizko-nivojskega jezika za implementacijo urejanja po delih (radix sort).

Obstajata dva različna postopka urejanja po delih. Prva skupina metod vključuje algoritme, ki pregledajo ključe v smeri od leve proti desni in najprej obdelajo najpomembnejše cifre. Te metode se imenujejo MSD (most significant digit) radix sort. MSD radix sort so zanimivi zato, ker pregledajo minimalno potrebno količino informacij, da uspešno opravijo urejanje. Druga skupina metod pa cifre v ključih pregledajo v smeri od desne proti levi po najmanj pomembnih cifrah. Te metode se imenujejo LSD (least significant digit) radix sort. LSD radix sort deluj ravno obratno kot MSD radix sort, ker uporablja procesorski čas na cifrah, ki ne morejo vplivati na rezultat, lahko pa omilijo problem. Zato je to pogosta metoda pri mnogih urejanjih.