Složenost unutrašnjeg sortiranja

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 1a). Sada je dovoljno premeštati pokazivače u pomoćnom vektoru umesto samih zapisa, a krajnji poredak, prikazan na slici 1b, je određen upravo vektorom pokazivača i na osnovu njega se zapisi mogu konačno i fizički premestiti.
b) posle sortiranja

Drugi način je ulančavanje zapisa između sebe u listu bez njihovog premeštanja. Tada svaki zapis treba da ima i dodatno polje link koje ukazuje na zapis sa sledećom vrednošću ključa, kao i spoljašnji pokazivač first koji pokazuje na zapis sa najmanjim (ili najvećim) ključem (slika 2). Ovde se potreba za premeštanjem izbegava prevezivanjem liste bez fizičkog pomeranja zapisa.