Uvod
Bok! Ja sam Sanjula i nadam se da ću vas u ovom vodiču naučiti malo o algoritmu sortiranja umetanja, uključujući:
- Što je vrsta umetanja?
- Zašto je vrsta umetanja važna?
- Izvedba sortiranja umetanja
- Kako funkcionira sortiranje umetanjem?
- Java implementacija sortiranja umetanja
Započnimo!
Što je vrsta umetanja?
To je jednostavan algoritam za sortiranje koji sortira niz po jednu stavku.
Zašto je vrsta umetanja važna?
Razvrstavanje umetanja ima nekoliko prednosti, uključujući:
- Čista jednostavnost algoritma.
- Relativni redoslijed stavki s jednakim ključevima ne mijenja se.
- Mogućnost sortiranja popisa po primanju.
- Učinkovito za male skupove podataka, posebno u praksi od ostalih kvadratnih algoritama - tj. O (n²).
- Potrebna je samo konstantna količina dodatnog prostora u memoriji - O (1).
Izvedba sortiranja umetanja
- Najlošija izvedba sortiranja umetanja je usporedba i zamjena O (n²).
- Najbolje izvedbe su O (n) usporedbe i O (1) zamjene.
- Prosječna izvedba slučaja je O (n²) usporedba i zamjena.
Kako funkcionira sortiranje umetanjem?
U svakoj iteraciji sortiranje umetanjem uspoređuje trenutni element sa sljedećim elementom i utvrđuje je li trenutni element veći od onog s kojim je uspoređen.
Ako je to istina , tada ostavlja element na svom mjestu i prelazi na sljedeći element. Ako je netočno , tada pronalazi svoj ispravan položaj u razvrstanom nizu i premješta ga na taj položaj pomicanjem svih elemenata koji su veći u razvrstanom nizu na jedan položaj ispred.
Java implementacija sortiranja umetanja
PS - Pokušajte to primijeniti sami!
Čestitamo!!! Sad ste usvojili osnovno, ali bitno znanje o tome kako funkcionira sortiranje umetanja.
Za probleme s referencama ili izvješćivanjem u vezi s gornjim kodom upotrijebite sljedeću javnu vezu GitHub Gist.
Nadam se da je ovo bilo korisno. Hvala na čitanju! :)