Diszkrét matematikai algoritmusok

Digitális válogatás (radix rendezés)

A digitális válogatás azon a megfigyelésen alapul, hogy ha a számokat már az L. L -1, ..., 1 alsó sorrendű bitek sorrendje szerint rendezik, akkor a legmagasabb számjegyekkel rendezhetők. P -1, ..., L +1, feltéve, hogy A rendezés úgy történik, hogy a legmagasabb számjegyű azonos számjegyű számok relatív sorrendjét nem sértik. Ez az elgondolás a lyukasztókhoz tartozó mechanikus válogató eszközök alapja.

A karton lyukasztott kártyákban speciális perforator lyukasztott lyukakat. A 0-9. Ábrákat a megfelelő oszlop 0-9 soraiban lévő egy lyukak kódolják. A válogatógépet az oszlop jelöli, amelyen a válogatást elvégezni kellett, és 10 lyukra szétosztotta a lyukasztókártyát, attól függően, hogy a 0-9 lyukak közül melyiket lyukasztották a jelzett oszlopban.

A legegyszerűbb az alacsonyabb renddel kezdeni, 10 kötegre osztva, attól függően, hogy a lyuk az "alsó" oszlopban van-e lyukasztva. Az így kapott 10 halom kell majd hajtogatott egyetlen ebben a sorrendben: .. Először kártya 0, akkor a kártya 1, stb A kapott fedélzet ismét rassortiruem 10 halom, de összhangban a mentesítési tíz, hozzá a kapott verem egy egyszintes, és így tovább; ha d-jegyű számokat írtak a lyukasztott kártyákra, akkor a rendezőgépet d alkalommal kell használni.

Fontos, hogy ez a fajta algoritmus eltér a legtöbb fajtatól, mivel nem a számok összehasonlításán alapul, hanem a számok ábrázolásán.

Példa: Adjuk meg a 439, 432, 120, 065 számokat.
Amint a példákból látható, a legnagyobb szám három számjegyből áll, ezért az első, második és harmadik kategóriák szerint kell rendezni:
az első: 120, 432, 065, 439,
a második: 120, 432, 439, 065,
a harmadik: 065, 120, 432, 439.
Gyakorlati problémák esetén célszerű a számrendszer bázisát választani a 2 n értékkel, mert ebben az esetben a szükséges kisülés kimutatását csak a műszak és a maszkolás műveletei végezik, ami lényegesen felgyorsítja az algoritmus munkáját.

Vödörfajta

A szétválasztás a lineáris átlagos idő alatt működik. Az az elképzelés, az algoritmus, hogy a [0, 1) van osztva n egyenlő részre, majd a számok az egyes rész van rendelve egy „box-gombóc” (vödör), valamint az n egész szám lehet válogatni jelennek meg ezeket a dobozokat. Mivel a számok egyenletesen oszlanak el a [0, 1] intervallumon belül, elvárható, hogy minden egyes dobozban kevés legyen. Most rendezni a számokat minden doboz külön-külön és menjen át a dobozokat emelkedő sorrendben írásával csapdába minden szám növekvő sorrendben.

Sorszámozás

A számlálás szerinti rendezés algoritmusa akkor alkalmazható, ha a rendezett szekvencia mindegyik eleme pozitív egész szám egy ismert tartományban (nem haladja meg az ismert k értéket). Ha k = O (n), akkor a rendezési algoritmus számláláskor O (n) időben működik.

Ennek az algoritmusnak az elgondolása, hogy először számoljon ki minden egyes elemre vonatkozóan x az input szekvencia hány eleme kisebb mint x. akkor írjon x-et közvetlenül ennek a számnak megfelelően (ha például a bemeneti tömb 9 eleme kisebb mint x, akkor az x kimeneti tömböt a 10-es számmal kell írni). Ez a séma kissé módosul, mert a rendezett sorozatban lehet egyenlő szám, hogy ne írj több számot egyetlen helyre.

A számlálási algoritmus fontos tulajdonsággal rendelkezik, amelyet stabilitásnak neveznek (stabil). Pontosabban, ha a bemeneti tömbben több egyenlő szám van, akkor a kimeneti tömbben ugyanolyan sorrendben vannak, mint a bemeneti tömbben.