Razlika između vrste umetanja i sortiranja

2019

Sortiranje sortiranja i vrsta sortiranja su tehnike koje se koriste za sortiranje podataka. Sortiranje i sortiranje većim unosom mogu se razlikovati metodom koju koriste za sortiranje podataka. Sortiranje umetanja umeće vrijednosti u unaprijed raspoređenu datoteku kako bi razvrstalo skup vrijednosti. S druge strane, vrsta odabira pronalazi najmanji broj s popisa i sortira ga nekim redoslijedom.

Razvrstavanje je osnovna operacija u kojoj su elementi niza uređeni u određenom redoslijedu kako bi se poboljšala mogućnost pretraživanja. Jednostavnim riječima, podaci se razvrstavaju tako da se mogu lako pretraživati.

Tablica usporedbe

Osnova za usporedbu	Sortiranje umetanja	Sortiranje sortiranja
Osnovni, temeljni	Podaci se razvrstavaju umetanjem podataka u postojeću sortiranu datoteku.	Podaci se razvrstavaju odabirom i stavljanjem uzastopnih elemenata na sortiranu lokaciju.
Priroda	Stabilan	nestabilan
Postupak koji treba slijediti	Elementi su unaprijed poznati dok se pretražuje mjesto postavljanja.	Mjesto je prethodno poznato, dok se elementi pretražuju.
Trenutačni podaci	Insertion sort je tehnika sortiranja uživo koja se može baviti neposrednim podacima.	Ne može se baviti neposrednim podacima, mora biti prisutan na početku.
Najbolja složenost slučaja	Na)	O (n `2` )

Definicija sortiranja umetanja

Umetanje sortira radi umetanja skupa vrijednosti u postojeću sortiranu datoteku. On konstruira sortirano polje umetanjem jednog elementa u isto vrijeme. Taj se postupak nastavlja dok se cijeli niz ne sortira nekim redom. Primarna koncepcija koja stoji iza vrste umetanja je umetanje svake stavke na odgovarajuće mjesto na konačnom popisu. Metoda sortiranja umetanja sprema učinkovitu količinu memorije.

Rad vrste Insertion

Koristi dva niza polja gdje se pohranjuju razvrstani podaci i drugo na nesortirane podatke.
Algoritam za razvrstavanje radi dok ne postoje elementi u nesortiranom skupu.
Pretpostavimo da u nizu postoje elementi 'n' broja. U početku, element s indeksom 0 (LB = 0) postoji u sortiranom skupu. Preostali elementi nalaze se u nesortiranoj particiji popisa.
Prvi element nesortiranog dijela ima indeks polja 1 (ako je LB = 0).
Nakon svake iteracije odabire prvi element nesortirane particije i umeće ga u odgovarajuće mjesto u sortiranom skupu.

Prednosti sortiranja umetaka

Lako se implementira i vrlo je učinkovita kada se koristi s malim skupom podataka.
Zahtjev dodatnog memorijskog prostora za sortiranje unosa je manji (tj. O (1)).
Smatra se da je to tehnika sortiranja uživo, jer se popis može razvrstati po primitku novih elemenata.
To je brže od drugih algoritama za sortiranje.

Primjer :

Definicija sortiranja sortiranja

Sortiranje odabira vrši sortiranje potragom za brojem minimalne vrijednosti i stavljanjem na prvu ili zadnju poziciju prema redoslijedu (uzlazno ili silazno). Proces traženja minimalnog ključa i njegovo postavljanje u ispravan položaj nastavlja se sve dok svi elementi ne budu postavljeni na pravo mjesto.

Rad sortiranja sortiranja

Pretpostavimo polje ARR s N elemenata u memoriji.
U prvom prolazu pretražuje se najmanji ključ zajedno s njegovim položajem, a ARR [POS] zamjenjuje se s ARR [0]. Stoga je ARR [0] razvrstan.
U drugom prolazu, opet se određuje položaj najmanje vrijednosti u sub-nizu N-1 elemenata. Zamijenite ARR [POS] s ARR [1].
U prolazu N-1, isti se postupak provodi kako bi se razvrstao N broj elemenata.

Primjer :

Ključne razlike između vrste umetanja i sortiranja

Sortiranje umetanja obično izvodi operaciju umetanja. Naprotiv, selekcijska vrsta provodi odabir i pozicioniranje potrebnih elemenata.
Smatra se da je vrsta umetanja stabilna, a vrsta odabira nije stabilan algoritam.
U algoritmu sortiranja umetaka elementi su prethodno poznati. Nasuprot tome, sortna selekcija unaprijed sadrži mjesto.
Sortiranje umetanjem je tehnika živog sortiranja u kojoj se dolazni elementi odmah sortiraju na popisu, dok sortna selekcija ne može dobro raditi s trenutnim podacima.
Sortiranje umetanja ima vrijeme izvođenja O (n) u najboljem slučaju. Nasuprot tome, najbolja složenost odabira vrste odabira je O (n2).

Složenost vrste umetanja

Najbolja složenost unosa je O (n) puta, tj. Kada je niz prethodno sortiran. Na isti način, kada je niz sortiran obrnutim redoslijedom, prvi element nesortiranog niza treba usporediti sa svakim elementom u sortiranom skupu. Dakle, u najgorem slučaju, vrijeme izvođenja vrste Insertion je kvadratno, tj. O (n2) . U prosječnom slučaju također mora napraviti minimalne (k-1) / 2 usporedbe. Dakle, prosječni slučaj također ima kvadratno vrijeme rada O (n2).

Složenost sortiranja

Kao rad selekcije, sortiranje ne ovisi o izvornom redoslijedu elemenata u nizu, tako da ne postoji velika razlika između najboljeg slučaja i najgoreg slučaja složenosti sortne selekcije.

Vrsta odabira odabire element minimalne vrijednosti, u procesu odabira skenira se cijeli broj n 'elemenata; stoga je u prvom prolazu napravljeno n-1 usporedba. Zatim se elementi zamjenjuju. Slično tome, u drugom prolazu također je potrebno pronaći drugi najmanji element koji zahtijeva skeniranje ostalih n-1 elemenata i proces se nastavlja sve dok se cijeli niz ne sortira.

Prema tome, složenost odabranog tipa odabira vremena izvođenja je O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)

Zaključak

Među oba algoritma za razvrstavanje, sortiranje je brzo, učinkovito i stabilno, dok sortna selekcija djeluje učinkovito samo kada je uključen mali skup elemenata ili je popis djelomično prethodno sortiran. Broj usporedbi napravljenih odabirom je veći od pokreta koji se izvode, dok je u obliku umetanja broj puta premještanje ili zamjena elementa veći od izvršenih usporedbi.