Unutrašnje sortiranje algoritama

UVOD

Unutrašnje sortiranje se primenjuje na skupove podataka čija veličina dozvoljava da se svi podaci istovremeno nalaze u operativnoj memoriji. Najčešće su podaci smešteni u vidu jednog vektora, pa se svakom podatku može direktno pristupiti. Zato se unutrašnje sortiranje često naziva i sortiranjem nizova. Ponekad se niz podataka može predstaviti i ulančanom listom, ali tada podacima mora da se pristupa sekvencijalno, pa je ovakvo sortiranje generalno sporije. Zato se u daljem izlaganju, ako drugačije nije naglašeno, smatra da su podaci koji se sortiraju smešteni u nizu a[1], …, a[n].

Kako je jedan od zahteva pri sortiranju efikasno korišćenje prostora, sa ovog aspekta poželjni su algoritmi koji vrše sortiranje in situ (na mestu), koristeći prostor gde je smešten neuređeni niz uz još samo konstantan broj dodatnih pomoćnih lokacija nezavisan od broja podataka. Još važniji je kriterijum vremenske složenosti kao pokazatelja performansi ovih metoda. Uobičajeni indikatori performanse metoda unutrašnjeg sortiranja u zavisnosti od broja podataka n koji se sortiraju su:

• broj koraka algoritma da bi se došlo do rešenja,
• broj poređenja ključeva (C),
• broj premeštanja zapisa (M).

Većina metoda u radu podrazumeva premeštanje zapisa sa jednog mesta na drugo da bi se oni konačno doveli u uređeni poredak. Međutim, kod većih zapisa ovo može biti vremenski skupo i može se izbeći po cenu malog dodatnog prostora. Jedan način je sortiranje po adresi što podrazumeva korišćenje pomoćnog vektora koji sadrži pokazivače na zapise (slika 1.1a). Sada je dovoljno premeštati pokazivače u pomoćnom vektoru umesto samih zapisa, a krajnji poredak, prikazan na slici 1.1b, je određen upravo vektorom pokazivača i na osnovu njega se zapisi mogu konačno i fizički premestiti.