Shell Sort i Java

1. Introduktion

I denne vejledning beskriver vi Shell-sorteringsalgoritmen i Java.

2. Shell Sort Oversigt

2.1. Beskrivelse

Lad os først beskrive Shell-sorteringsalgoritmen, så vi ved, hvad vi prøver at implementere.

Shell-sortering er baseret på Insertion-sorteringsalgoritmen, og den tilhører gruppen af ​​meget effektive algoritmer. Generelt, algoritmen bryder et originalt sæt i mindre delmængder, og derefter sorteres hver af dem ved hjælp af Indsnitssortering.

Men hvordan det gør delmængderne er ikke ligetil. Det vælger ikke naboelementer til at danne et undersæt, som vi kunne forvente. Snarere bruger skalesortering den såkaldte interval eller hul til oprettelse af delmængder. For eksempel hvis vi har kløften jegbetyder det, at et undersæt vil indeholde de elementer, der er jeg positioner fra hinanden.

For det første sorterer algoritmen de elementer, der er langt væk fra hinanden. Derefter bliver afstanden mindre, og tættere elementer sammenlignes. På denne måde kan nogle elementer, der ikke er i den korrekte position, placeres hurtigere, end hvis vi lavede delmængderne af de omkringliggende elementer.

2.2. Et eksempel

Lad os se dette i eksemplet med hullerne 3 og 1 og den usorterede liste over 9 elementer:

Hvis vi følger ovenstående beskrivelse, i den første iteration, har vi tre undergrupper med 3 elementer (fremhævet med samme farve):

Efter at have sorteret hvert af delmængderne i den første iteration, ser listen ud:

Vi kan bemærke, at selvom vi endnu ikke har en sorteret liste, er elementerne nu tættere på de ønskede positioner.

Endelig er vi nødt til at gøre en mere sortering med stigningen i en, og det er faktisk en grundlæggende indsættelsessort. Antallet af skiftende operationer, som vi skal udføre for at sortere en liste, er nu mindre, end det ville være tilfældet, hvis vi ikke udførte den første iteration:

2.3. Valg af hulsekvenser

Som vi nævnte, har shell-sorteringen en unik måde at vælge gap-sekvenser på. Dette er en vanskelig opgave, og vi skal være forsigtige med ikke at vælge for få eller for mange huller. Flere detaljer kan findes i den mest foreslåede oversigt over gap-sekvenser.

3. Implementering

Lad os nu se på implementeringen. Vi bruger Shells originale sekvens til intervallintervaller:

N / 2, N / 4,…, 1 (kontinuerligt divideret med 2)

Selve implementeringen er ikke for kompleks:

offentlig tomrums sortering (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øgle) {arrayToSort [j] = arrayToSort [j - gap ]; j - = hul; } arrayToSort [j] = nøgle; }}}

Vi oprettede først en hulsekvens med en for-løkke og derefter sorterede indsættelsen for hver mellemrumsstørrelse.

Nu kan vi nemt teste vores metode:

@Test offentlig ugyldighed givenUnsortedArray_whenShellSort_thenSortedAsc () {int [] input = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort (input); int [] forventet = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals ("de to arrays er ikke ens", forventet, input); }

4. Kompleksitet

Generelt, Shell-sorteringsalgoritmen er meget effektiv med mellemstore lister. Kompleksiteten er vanskelig at bestemme, da det afhænger meget af gap-sekvensen, men tidskompleksiteten varierer mellem PÅ) og O (N ^ 2).

Den værst tænkelige rumkompleksitet er PÅ) med O (1) hjælpeplads.

5. Konklusion

I denne vejledning beskrev vi Shell-sortering og illustrerede, hvordan vi kan implementere det i Java.

Som sædvanlig kunne hele koden findes på GitHub.