Savremena IT u službi prisluškivanja ljudi
Objavio nejra.16 27. mart 2024.
Seminarski radovi, Skripte, Informacione tehnologije
Objavio nenadco 24. jun 2013. Prijavi dokument
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:
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.
Objavio nejra.16 27. mart 2024.
Objavio dragan79 25. mart 2024.
Objavio mija.03 13. mart 2024.
Objavio DJOKO MEKLAUD 27. mart 2024.
Objavio nejra.16 27. mart 2024.
Objavio bojana.petr 27. mart 2024.
Objavio DJOKO MEKLAUD 27. mart 2024.
Objavio nejra.16 27. mart 2024.
Objavio bojana.petr 27. mart 2024.
Komentari
You must be logged in to post a comment.