shell sort c with examples
Shell Sort Technique In C ++: En komplett oversikt.
Skalsortering blir ofte betegnet som en forbedring i forhold til innsettingssortering. Ved innsetting sorterer vi trinn på 1 for å sammenligne elementene og sette dem i riktig posisjon.
I skallsortering sorteres listen ved å dele den opp i et antall mindre underlister. Det er ikke nødvendig at listene må ha sammenhengende elementer. I stedet bruker skallsorteringsteknikk økning i, som også kalles 'gap' og bruker den til å lage en liste over elementer som er 'i' -elementer fra hverandre.
=> Se her for å utforske hele C ++ opplæringslisten.
hvordan du legger til elementer i en array-java
Hva du vil lære:
Generell algoritme
Den generelle algoritmen for skallsortering er gitt nedenfor.
shell_sort (A, N)
hvor A - liste skal sorteres; N - gap_størrelse
sett gap_size = N, flagg = 1
mens gap_størrelse> 1 eller flagg = 1, gjenta
begynne
sett flagg = 0
sett gap_size = (gap_size + 1) / 2
slutt
for i = 0 til i<(N-gap_size) repeat
begynne
hvis A [i + gap_størrelse]> A [i]
bytt A [i + gap_størrelse], A [i]
sett flagg = 0
slutt
slutt
I den ovennevnte algoritmen setter vi først N som er gapet for å sortere matrisen A ved bruk av skallsortering. I neste trinn deler vi matrisen i underarrayer ved å bruke gapet. Så i neste trinn sorterer vi hver av underarrayene slik at vi på slutten av løkken får en sortert matrise.
La oss deretter vurdere et detaljert eksempel for bedre å forstå skallsorteringen ved hjelp av en billedlig fremstilling.
Illustrasjon
La oss illustrere Shell-sorteringen med et eksempel.
Tenk på følgende utvalg av 10 elementer.
Hvis vi gir et gap på 3, vil vi ha følgende underlister med hvert element som er 3 elementer fra hverandre. Vi sorterer deretter disse tre underlistene.
De sorterte underlistene og den resulterende listen som vi oppnår etter å ha kombinert de tre sorterte underlistene, vises nedenfor.
Ovenstående matrise som vi har oppnådd etter sammenslåing av de sorterte underarrayene, er nesten sortert. Nå kan vi utføre innsettingssortering på denne listen og sortere hele matrisen. Dette siste trinnet vises nedenfor for din referanse.
Etter å ha utført skallsortering og sammenslåing av de sorterte underlistene, krevde vi bare tre trekk for å fullstendig sortere listen. Dermed kan vi se at vi kan redusere antall trinn som kreves for å sortere matrisen betydelig.
Valget av trinn for å lage underlister er en unik funksjon av skallsortering.
C ++ Eksempel
La oss se implementeringen av skallsortering 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 Produksjon:
Array som skal sorteres:
45 23 53 43 18 24 8 95 101
Array after shell sort:
8 18 23 24 43 45 53 95 101
Vi har brukt den samme listen som vi brukte i illustrasjonen, og vi kan se at vi begynner med å lage to underlister og deretter redusere gapet ytterligere. Når underlister er opprettet i henhold til gapet spesifisert, sorterer vi hver av underlistene. Etter at alle underlistene er sortert, får vi den nesten sorterte listen. Nå kan denne listen sorteres ved hjelp av den grunnleggende sorteringssorteringen som tar svært få trekk.
La oss deretter implementere skallsortering ved hjelp av Java-språk.
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 Produksjon:
Array som skal sorteres:
45 23 53 43 18 24 8 95 101
Array after shell sort:
8 18 23 24 43 45 53 95 101
Vi har implementert den samme logikken for skallsortering i både C ++ og Java-programmer. Således som forklart ovenfor i Java-programmet, deler vi først matrisen i underarrayer og deretter sorterer dem for å oppnå en komplett sortert matrise.
Konklusjon
Skalsortering er den svært effektive algoritmen som forbedrer seg over innsettingssorteringen.
Mens innsettingssortering fungerer ved å øke elementene med 1, bruker skallsortering parameteren 'gap' for å dele opp matrisen i underarrayer der elementene er 'gap' fra hverandre. Deretter kan vi sortere den enkelte listen ved hjelp av innsettingssortering for å få den fullstendige sorterte matrisen.
Shell-sortering utfører raskere enn innsettingssortering og tar færre trekk for å sortere matrisen sammenlignet med innsettingssortering. Vår kommende veiledning vil utforske alt om heapsorteringsteknikk for sortering av datastrukturer.
=> Besøk her for å lære C ++ fra grunnen.
Anbefalt lesing
- Utvalgssortering i C ++ med eksempler
- MongoDB Sort () Metode med eksempler
- Unix sorteringskommando med syntaks, alternativer og eksempler
- Boblesortering i C ++ med eksempler
- Innsettingssortering i C ++ med eksempler
- Flett sortering i C ++ med eksempler
- Haugsortering i C ++ med eksempler
- Rask sortering i C ++ med eksempler