streamalism.org

1. Pregled

U ovom uputstvu ćemo raspraviti algoritam sortiranja umetanja i pogledajte njegovu implementaciju Java.

Sortiranje umetanja učinkovit je algoritam za naručivanje malog broja predmeta. Ova metoda temelji se na načinu na koji igrači karta sortiraju ruku igraćih karata.

Počinjemo s praznom lijevom rukom i kartama položenim na stol. Zatim uklanjamo po jednu kartu sa stola i stavljamo je u ispravan položaj u lijevoj ruci. Da bismo pronašli ispravan položaj za novu kartu, uspoređujemo je s već razvrstanim nizom karata u ruci, zdesna nalijevo.

Krenimo od razumijevanja koraka algoritma u obliku pseudokoda.

2. Pseudokod

Predstavit ćemo naš pseudokod za sortiranje umetanja kao postupak pod nazivom INSERCIJSKO-SORTIRANJE, uzimajući kao parametar niz A [1 .. n] od n predmeta za sortiranje. Algoritam sortira ulazni niz na mjestu (preslagivanjem predmeta unutar polja A).

Nakon završetka postupka, ulazni niz A sadrži permutaciju ulaznog niza, ali poredanim redoslijedom:

INSERTION-SORT (A) za i = 2 do A. tipka dužine = A [i] j = i - 1 dok je j> 0 i A [j]> tipka A [j + 1] = A [j] j = j - 1 A [j + 1] = tipka

Kratko pređimo na gornji algoritam.

Indeks ja označava položaj trenutne stavke u polju za obradu.

Počinjemo od druge stavke jer se po definiciji niz s jednom stavkom smatra sortiranim. Stavka u indeksu ja naziva se a ključ. Jednom kad je ključ, drugi dio algoritma bavi se pronalaženjem njegovog ispravnog indeksa. Ako je ključ je manja od vrijednosti predmeta u indeksu j, zatim se tipka pomiče za jedan položaj ulijevo. Proces se nastavlja sve do slučaja kada dođemo do elementa manjeg od ključa.

Važno je napomenuti da prije početka iteracije za pronalaženje ispravnog položaja ključ u indeksu ja, niz A [1 .. j - 1] je već razvrstano.

3. Imperativna provedba

U imperativu ćemo napisati funkciju tzv insertionSortImperative, uzimajući kao parametar niz cijelih brojeva. Funkcija započinje iteraciju preko niza iz druge stavke.

U bilo kojem trenutku tijekom iteracije, mogli bismo pomisliti da je ovaj niz logično podijeljen u dva dijela; lijeva strana je razvrstana, a desna strana sadrži stavke koje još nisu razvrstane.

Ovdje je važna napomena da nakon pronalaska ispravnog položaja na koji ćemo umetnuti novu stavku, premještamo (i ne mijenjamo) stavke udesno osloboditi prostor za to.

javna statička praznina insertionSortImperative (int [] input) {for (int i = 1; i = 0 && input [j]> tipka) {input [j + 1] = input [j]; j = j - 1; } ulaz [j + 1] = tipka; }}

Dalje, kreirajmo test za gornju metodu:

@Test javna praznina givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc () {int [] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative (ulaz); int [] očekuje se = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("dva polja nisu jednaka", očekuje se, ulaz); }

Gornji test dokazuje da algoritam pravilno sortira ulazni niz u rastućem redoslijedu .

4. Rekurzivna provedba

Poziva se funkcija za rekurzivni slučaj insertionSortRekskurzivan i prihvaća kao ulaz niz čitavih brojeva (isto kao za imperativ).

Ovdje je razlika od imperativnog slučaja (unatoč činjenici da je rekurzivan) u tome što on poziva preopterećenu funkciju s drugim argumentom koji je jednak broju stavki za sortiranje.

Kako želimo razvrstati kompletni niz, proslijedit ćemo niz predmeta jednakih njegovoj dužini:

javna statička praznina insertionSortRecursive (int [] input) {insertionSortRecursive (input, input.length); }

Rekurzivni slučaj je malo izazovniji. Osnovni slučaj javlja se kada pokušavamo sortirati niz s jednom stavkom. U ovom slučaju ne radimo ništa.

Svi sljedeći rekurzivni pozivi sortiraju unaprijed definirani dio ulaznog polja - počevši od druge stavke pa sve dok ne dođemo do kraja niza:

privatna statička praznina insertionSortRecursive (int [] input, int i) {if (i <= 1) {return; } insertionSortRecursive (ulaz, i - 1); tipka int = ulaz [i - 1]; int j = i - 2; while (j> = 0 && input [j]> key) {input [j + 1] = input [j]; j = j - 1; } ulaz [j + 1] = tipka; }

I ovako izgleda hrpa poziva za ulazni niz od 6 stavki:

insertionSortRecursive (input, 6) insertionSortRecursive (input, 5) i umetnite 6. stavku u sortirani niz insertionSortRecursive (input, 4) i umetnite 5. stavku u sortirani niz insertionSortRecursive (input, 3) i umetnite 4. stavku u sortirano niz insertionSortRecursive (ulaz, 2) i umetnite 3. stavku u sortirani niz insertionSortRecursive (ulaz, 1) i umetnite 2. stavku u sortirani niz

Pogledajmo i test za to:

@Test javna praznina givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc () {int [] input = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive (ulaz); int [] očekuje se = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("dva polja nisu jednaka", očekuje se, ulaz); }

Gornji test dokazuje da algoritam pravilno sortira ulazni niz u rastućem redoslijedu .

5. Složenost vremena i prostora

Vrijeme potrebno za INSERCIJSKO-SORTIRANJE postupak za pokretanje je O (n ^ 2). Za svaku novu stavku ponavljamo zdesna ulijevo preko već razvrstanog dijela niza kako bismo pronašli njegov ispravan položaj. Zatim ga umetnemo pomicanjem predmeta za jedan položaj udesno.

Algoritam sortira na mjestu pa svoj složenost prostora je O (1) za imperativnu provedbu i Na) za rekurzivnu provedbu.

6. Zaključak

U ovom uputstvu vidjeli smo kako implementirati sortiranje umetanja.

Ovaj algoritam koristan je za sortiranje malog broja predmeta. Postaje neučinkovito pri sortiranju ulaznih sekvenci koje imaju više od 100 stavki.

Imajte na umu da se unatoč svojoj kvadratnoj složenosti sortira na mjestu bez potrebe za pomoćnim prostorom kao što je slučaj za spajanje sortirati.

Cijeli kôd mogao se naći na GitHubu.