Menu

Shell Sort In C ++ med eksempler

shell sort c with examples

Prøv Vores Instrument Til At Fjerne Problemer

Shell Sort teknik i C ++: En komplet oversigt.

Shell-sort betegnes ofte som en forbedring i forhold til indsætningssortering. I indsættelsessortering tager vi trin på 1 for at sammenligne elementer og sætte dem i deres rette position.

I shell-sortering sorteres listen ved at opdele den i et antal mindre underlister. Det er ikke nødvendigt, at listerne skal have sammenhængende elementer. I stedet bruger shell-sorteringsteknikken trin i, som også kaldes 'hul' og bruger den til at oprette en liste over elementer, der adskiller 'i' -elementer.

=> Se her for at udforske den komplette C ++ tutorials-liste.

hvor du finder netværkssikkerhedsnøglen

Shell Sort

Hvad du vil lære:

Generel algoritme

Den generelle algoritme for skalesortering er angivet nedenfor.

shell_sort (A, N)
hvor A - liste, der skal sorteres; N - hulstørrelse

sæt gap_size = N, flag = 1
mens gap_size> 1 eller flag = 1, gentag
begynde
sæt flag = 0
sæt gap_size = (gap_size + 1) / 2
ende
for i = 0 til i<(N-gap_size) repeat
begynde
hvis A (i + gap_størrelse)> A (i)
skift A (i + gap_størrelse), A (i)
sæt flag = 0
ende
ende

Således i ovenstående algoritme indstiller vi først N, som er kløften til sortering af array A ved hjælp af shell-sortering. I det næste trin opdeler vi arrayet i underarrays ved hjælp af mellemrummet. Så i det næste trin sorterer vi hver af underarrayerne, så vi i slutningen af ​​sløjfen får et sorteret array.

Lad os derefter overveje et detaljeret eksempel for bedre at forstå shell-sorteringen ved hjælp af en billedlig gengivelse.

Illustration

Lad os illustrere Shell-sorteringen med et eksempel.

Overvej følgende række med 10 elementer.

matrix med 10 elementer

Hvis vi giver et hul på 3, har vi følgende underlister med hvert element, der er 3 elementer fra hinanden. Vi sorterer derefter disse tre underlister.

underlister

De sorterede underlister og den resulterende liste, som vi opnår efter kombination af de tre sorterede underlister, vises nedenfor.

sorterede underlister og den resulterende liste

Ovenstående matrix, som vi har opnået efter sammenlægning af de sorterede underarrays, er næsten sorteret. Nu kan vi udføre indsættelsessortering på denne liste og sortere hele arrayet. Dette sidste trin vises nedenfor til din reference.

Det sidste trin

Som det ses ovenfor, efter at have udført shell-sortering og fletning af de sorterede sublister, krævede vi kun tre træk for at sortere listen fuldstændigt. Således kan vi se, at vi kan reducere antallet af nødvendige trin for at sortere arrayet markant.

Valget af forøgelse til oprettelse af underlister er et unikt træk ved shell-sortering.

C ++ Eksempel

Lad os se implementeringen af ​​shell-sortering i C ++ nedenfor.

#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted: '; for (int i=0; i

Produktion:

Array, der skal sorteres:

45 23 53 43 18 24 8 95101

Array efter shell sortering:

8 18 23 24 43 45 53 95 101

Vi har brugt den samme liste, som vi brugte i illustrationen, og vi kan se, at vi først begynder med at oprette to underlister og derefter indsnævre kløften yderligere. Når sublister er oprettet i henhold til det angivne hul, sorterer vi hver af sublisterne. Når alle underlister er sorteret, får vi den næsten sorterede liste. Nu kan denne liste sorteres ved hjælp af den grundlæggende indsættelsessortering, som tager meget få træk.

Lad os derefter implementere shell-sortering ved hjælp af Java-sprog.

Java-eksempel

// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr()) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } } class Main{ public static void main(String args()) { int arr() = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println('Array to be sorted: '); for (int i=0; i

Produktion:

Array, der skal sorteres:

45 23 53 43 18 24 8 95101

Array efter shell sortering:

8 18 23 24 43 45 53 95 101

Vi har implementeret den samme logik for shell-sortering i både C ++ og Java-programmer. Således som forklaret ovenfor i Java-programmet opdeler vi først arrayet i underarrays og derefter sorterer dem for at opnå et komplet sorteret array.

Konklusion

Shell-sortering er den yderst effektive algoritme, der kommer til en forbedring i forhold til indsættelsessorteringen.

Mens indsættelsessortering fungerer ved at forøge elementerne med 1, bruger skalesortering parameteren 'hul' til at opdele arrayet i underarrays, hvis elementer er 'gap' fra hinanden. Derefter kan vi sortere den enkelte liste ved hjælp af indsættelsessortering for at få det komplette sorterede array.

Shell-sortering udfører hurtigere end indsættelsessortering og tager færre træk for at sortere arrayet sammenlignet med indsættelsessortering. Vores kommende vejledning vil udforske alt om heapsorteringsteknikken til sortering af datastrukturer.

=> Besøg her for at lære C ++ fra bunden.

Anbefalet læsning

^