Kest Sorteeri

Selles õpetuses saate teada, kuidas kestade sortimine töötab. Samuti leiate toimivad näited kestade sortimisest C, C ++, Java ja Python.

Kestus sortimine on algoritm, mis sorteerib elemendid kõigepealt üksteisest kaugel ja vähendab järjestatud elementide vahelist intervalli. See on üldistatud versioon sisestamise sortimisest.

Shell sortimisel sorteeritakse kindla intervalliga elemendid. Elementide vahe väheneb kasutatava järjestuse põhjal järk-järgult. Shelli sorteerimise jõudlus sõltub antud sisendi massiivi jaoks kasutatud järjestuse tüübist.

Mõned kasutatud optimaalsed järjestused on:

  • Shelli algne järjestus: N/2 , N/4 ,… , 1
  • Knuthi sammud: 1, 4, 13,… , (3k - 1) / 2
  • Sedgewicki sammud: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibbardi sammud: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernovi ja Stasevitši juurdekasv: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Kuidas Shell Sort töötab?

  1. Oletame, et peame sorteerima järgmise massiivi. Esialgne massiiv
  2. Kasutame (N/2, N/4,… 1oma algoritmis intervallidena kesta algset järjestust ).
    Esimeses tsüklis, kui massiivi suurus on N = 8siis, N/2 = 4võrreldakse ja vahetatakse nende intervalliga lebavaid elemente, kui need pole korras.
    1. 0. elementi võrreldakse 4. elemendiga.
    2. Kui 0. element on suurem kui neljas, siis salvestatakse 4. element kõigepealt tempmuutujasse ja 0thelement (st suurem element) salvestatakse 4thpositsiooni ning element, kuhu salvestatakse, tempon selles 0thasendis. Elementide ümberkorraldamine n / 2 intervalliga
      See protsess jätkub kõigi ülejäänud elementide puhul. Järjestage kõik elemendid n / 2 intervalliga
  3. Teises silmus N/4 = 8/4 = 2võetakse intervall ja jällegi sorteeritakse nende vahedega lebavad elemendid. Elementide ümberkorraldamine n / 4 intervalliga
    Võite selles hetkes segadusse sattuda. Võrreldakse kõiki massiivi elemente, mis asuvad praeguse intervalliga. Võrreldakse
    4. ja elemendi elemente 2nd. 0thSamuti võrreldakse 2. ja elemendi elemente . Võrreldakse kõiki massiivi elemente, mis asuvad praeguse intervalliga.
  4. Sama protsess toimub ka ülejäänud elementide puhul. Järjestage kõik elemendid n / 4 intervalliga
  5. Lõpuks, kui intervall on, N/8 = 8/8 =1sorteeritakse massiivi elemendid, mis asuvad intervalliga 1. Massiiv on nüüd täielikult sorteeritud. Järjestage elemendid n / 8 intervalliga

Shelli sorteerimise algoritm

 shellSort (massiiv, suurus) intervalli i jaoks <- size / 2n kuni 1 iga massiivi "i" intervalli jaoks sorteerib kõik elemendid intervalliga "i" lõpu shellSort

Pythoni, Java ja C / C ++ näited

Python Java C C ++ 
# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 
// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 
// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); )

Keerukus

Kestasorteerimine on ebastabiilne sorteerimisalgoritm, kuna see algoritm ei uuri intervallide vahel asuvaid elemente.

Aja keerukus

  • Halvima juhtumi keerukus : halvem juhtumi keerukus kestade sortimisel on alati väiksem või võrdne . Vastavalt Poonen teoreem, halvimal juhul keerukust kest omamoodi on või või või midagi vahepealset.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Parima juhtumi keerukus : O(n*log n)
    kui massiiv on juba sorteeritud, võrdub iga intervalli (või juurdekasvu) võrdluste koguarv massiivi suurusega.
  • Keskmine juhtumi keerukus : O(n*log n)
    see on umbes .O(n1.25)

Keerukus sõltub valitud intervallist. Eespool toodud keerukus erineb valitud juurdekasvujärjestuste puhul. Parim juurdekasvu järjestus pole teada.

Ruumi keerukus:

Shelli sortimise ruumi keerukus on O(1).

Shelli rakenduste sortimine

Kestusorte kasutatakse juhul, kui:

  • virna kutsumine on üleliigne. uClibci teek kasutab seda sorti.
  • rekursioon ületab piiri. bzip2 kompressor kasutab seda.
  • Sisestussorteerimine ei toimi hästi, kui lähedased elemendid on üksteisest kaugel. Kestus sortimine aitab vähendada lähedaste elementide vahelist kaugust. Seega on vahetuste arv vähem teostatav.

Huvitavad Artiklid...