streamalism.org

1. Introduksjon

I denne veiledningen beskriver vi Shell-sorteringsalgoritmen i Java.

2. Skjellsorteringsoversikten

2.1. Beskrivelse

La oss først beskrive Shell-sorteringsalgoritmen, slik at vi vet hva vi prøver å implementere.

Skalsortering er basert på Insertion-sorteringsalgoritmen, og den tilhører gruppen av svært effektive algoritmer. Generelt, algoritmen bryter et originalt sett i mindre delmengder, og deretter sorteres hvert av dem ved hjelp av Insertion sort.

Men hvordan det gjør delmengdene er ikke greit. Det velger ikke naboelementer for å danne et delsett som vi kunne forvente. Snarere bruker skallsortering såkalt intervall eller mellomrom for delminnelagelse. For eksempel hvis vi har gapet Jeg, betyr det at ett delsett vil inneholde elementene som er Jeg stillinger fra hverandre.

For det første sorterer algoritmen elementene som er langt borte fra hverandre. Da blir gapet mindre og nærmere elementer blir sammenlignet. På denne måten kan noen elementer som ikke er i riktig posisjon posisjoneres raskere enn om vi laget delmengdene av de nærliggende elementene.

2.2. Et eksempel

La oss se dette i eksemplet med hullene på 3 og 1 og den usorterte listen over 9 elementer:

Hvis vi følger beskrivelsen ovenfor, i den første iterasjonen, har vi tre delmengder med 3 elementer (fremhevet med samme farge):

Etter å ha sortert hvert av delmengdene i den første iterasjonen, vil listen se ut som:

Vi kan merke oss at selv om vi ikke har en sortert liste ennå, er elementene nå nærmere ønskede posisjoner.

Til slutt må vi gjøre en mer sortering med økningen av en, og det er faktisk en grunnleggende innsettingssort. Antall skiftende operasjoner vi trenger å utføre for å sortere en liste er nå mindre enn det ville være tilfellet hvis vi ikke gjorde den første iterasjonen:

2.3. Velge hullsekvensene

Som vi nevnte, har skallsorteringen en unik måte å velge gap-sekvenser på. Dette er en vanskelig oppgave, og vi bør være forsiktige med å ikke velge for få eller for mange hull. Flere detaljer finner du i listen over de mest foreslåtte gap-sekvensene.

3. Gjennomføring

La oss nå se på implementeringen. Vi bruker Shells opprinnelige sekvens for intervallintervaller:

N / 2, N / 4,…, 1 (kontinuerlig divisjon med 2)

Selve implementeringen er ikke for kompleks:

public void sort (int arrayToSort []) {int n = arrayToSort.length; for (int gap = n / 2; gap> 0; gap / = 2) {for (int i = gap; i = gap && arrayToSort [j - gap]> nøkkel) {arrayToSort [j] = arrayToSort [j - gap ]; j - = gap; } arrayToSort [j] = nøkkel; }}}

Vi opprettet først en gap sekvens med en for loop, og deretter sorterte innsettingen for hver gap størrelse.

Nå kan vi enkelt teste metoden vår:

@Test offentlig ugyldighet gittUnsortedArray_whenShellSort_thenSortedAsc () {int [] input = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort (inngang); int [] forventet = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals ("de to matriser er ikke like", forventet, input); }

4. Kompleksitet

Som regel, Shell sorteringsalgoritmen er veldig effektiv med mellomstore lister. Kompleksiteten er vanskelig å bestemme siden det avhenger mye av gap-sekvensen, men tidskompleksiteten varierer mellom PÅ) og O (N ^ 2).

Det verste tilfellet er romkompleksitet PÅ) med O (1) hjelpeplass.

5. Konklusjon

I denne opplæringen beskrev vi Shell sort og illustrerte hvordan vi kan implementere det i Java.

Som vanlig kunne hele koden bli funnet på GitHub.