Aspecte ale algoritmilor de sortare prin numărare

Cu toate ca dictionarele definesc sortarea ca un proces de separare si aranjare a lucrarilor dupa clase si fel, este traditional pentru programatorii de calculatoare sa utilizeze cuvantul intr-un sens mult mai special, de sortare a lucrurilor intr-o ordine ascendenta sau descendenta. Procesul, probabil, ar trebui numit ordonare si nu sortare; dar oricine incearca sa-i spuna ordonare va ajunge foarte curand in situatii foarte confuze, din cauza intelesurilor diferite atasate acestui cuvant. Unii au sugerat ca termen secventare sa fie numele dat procesului de ordonare dar acest cuvant nu reda uneori sensul corect, in mod special in cazul prezentei unor elemente egale. Este adevarat ca sortare este un cuvant foarte solicitat, dar este unanim acceptat in limbajul legat de calculatoare. a) solutionarea problemei legate de punerea impreuna a tuturor articolelor care au aceeasi identitate. b) daca doua sau mai multe fisiere au fost sortate in aceeasi ordine, devine posibila gasirea intrarilor identice printr-o singura trecere prin ele, fara intoarceri inapoi. Sortarea face posibila utilizarea adresarii secventiale in fisiere mari, ca un substitut fezabil adresarii directe. c) Sortarea este de asemenea un mijloc ajutator pentru cautare, permitand astfel ca iesirile de la calculator sa devina mai adecvate necesitatilor umane. Cu toate ca sortarea a fost utilizata traditional in prelucrari de date cu caracter economic, ea este un mijloc de baza pe care programatorul trebuie sa o considere, pentru cele mai variate situatii. Tehnicile de sortare asigura o ilustrare excelenta a ideilor generale legate de analiza algoritmilor, adica a ideilor utilizate pentru a determina performantele algoritmilor astfel incat sa se poata face un discernamant inteligent intre diferitele metode. In lucrarea de fata este folosita o anumita terminologie pe ca o prezint in randurile ce urmeaza. Se dau N articole R1, , RN care urmeaza a fi sortate; ele vor fi numite inregistrari. Intreaga colectie de N inregistrari va fi denumita fisier. Fiecare inregistrare R j, are o cheie Kj care guverneaza procesul de sortare. Poate exista si alta informatie in inregistrare in afara cheii; aceasta informatie satelit nu va avea nici un efect asupra procesului de sortare, in afara faptului ca ea va ramane cu inregistrarea respectiva. O alta relatie de ordonare < este specificata asupra cheilor, astfel, ca pentru orice valoare a celor trei chei a, b, c, urmatoarele conditii sa fie satisfacute: 1) Numai una din posibilitatile a< b, a=b, b ...