Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Meseria se fura, ingineria se invata.Telecomunicatii, comunicatiile la distanta, Retele de, telefonie, VOIP, TV, satelit




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
Sortarea radix directa


Sortarea radix directa


Sortarea radix directa

O alta varianta de implementare a sortarii radix este aceea de a examina bitii cheilor elementelor de la dreapta la stanga.

Este metoda utilizata de vechile masini de sortat cartele.

o      Teancul de cartele trece de 80 de ori prin masina, cate odata pentru fiecare coloana incepand de la dreapta spre stanga, fiecare trecere realizand sortarea dupa o coloana.



o      In cazul cheilor, cand se ajunge la bitul i venind dinspre dreapta, cheile sunt gata sortate pe ultimii i-1 biti ai lor.

o      Sortarea continua extragand toate elementele ale caror chei au zero pe pozitia i si plasandu-le in fata celor care au 1 pe aceeasi pozitie.

Nu este usor de demonstrat ca metoda este corecta: de fapt ea este corecta numai in situatia in care sortarea dupa 1 bit este stabila.


Datorita acestei cerinte, sortarea radix prin interschimbare nu poate fi utilizata deoarece nu este o metoda de sortare stabila.

  • In ultima instanta trebuie sortat stabil un tablou cu numai doua valori 0 si 1.
  • Metoda bazata pe determinarea distributiilor (distribution counting) poate fi utilizata cu succes in acest scop.
    • Se considera algoritmul de sortare bazat pe determinarea distributiei cheilor in care:
      • Se ia m = 2 si
      • Se inlocuieste a[i].cheie cu biti(a[i].cheie,k,1) pentru  k = 0, 1, 2, , b -1 (adica se extrage din cheie 1 bit situat la distanta k fata de sfarsitul cheii) .
    • Se obtine astfel, o metoda de sortare stabila a tabloului a, dupa bitul k, de la dreapta la stanga, rezultatul fiind memorat intr-o tablou temporar t .
    • Se reia sortarea bazata pe determinarea distributiilor pentru fiecare bit al cheii respectiv pentru pentru  k = 0, 1, 2, , b -1
    • Rezulta ca pentru sortare sunt necesare b treceri unde b este lungimea cheii.
  • De fapt, nu este indicat sa se lucreze cu m = 2 , ci este convenabil ca m sa fie cat mai mare.
  • Daca se prelucreaza m biti odata, timpul de sortare scade, dar tabela de distributii creste ca dimensiune ea trebuind sa contina  m1 = 2 locatii.
  • In acest mod, sortarea radix-directa devine o generalizare a sortarii bazate pe determinarea distributiilor.
  • Algoritmul din secventa [3.2.9.2.a] sorteaza dupa aceasta metoda tabloul a[1..n],
    • Cheile sunt de b biti lungime,
    • Cheile sunt parcurse de la dreapta la stanga, procesand cate m biti odata.
    • Se utilizeaza tabloul suplimentar t[1..n].
  • Procedura functioneaza numai daca b este multiplu de m deoarece algoritmul de sortare divizeaza bitii cheilor intr-un numar intreg de parti de dimensiuni egale care se proceseaza deodata.
  • Daca se ia   m = b  se obtine sortarea bazata pe determinarea distributiilor;
  • Daca se ia  =  rezulta sortarea radix directa.
  • Implementarea propusa sorteaza tabloul a in tabloul t si dupa fiecare pas de sortare recopiaza tabloul t in a (ultima bucla FOR).







Politica de confidentialitate





Copyright © 2023 - Toate drepturile rezervate