Čaulas kārtošana

Šajā apmācībā jūs uzzināsiet, kā darbojas čaulas kārtošana. Jūs atradīsit arī čaulu kārtošanas piemērus C, C ++, Java un Python.

Apvalka kārtošana ir algoritms, kas vispirms kārto elementus tālu viens no otra un secīgi samazina intervālu starp kārtoamajiem elementiem. Tā ir vispārināta ievietošanas veida versija.

Čaulas kārtošanā elementi ar noteiktu intervālu tiek sakārtoti. Intervāls starp elementiem tiek pakāpeniski samazināts, pamatojoties uz izmantoto secību. Čaulas kārtošanas veiktspēja ir atkarīga no secības veida, kas tiek izmantota attiecīgajam ievades masīvam.

Dažas no optimālākajām izmantotajām sekvencēm ir:

  • Shell sākotnējā secība: N/2 , N/4 ,… , 1
  • Knuta solis: 1, 4, 13,… , (3k - 1) / 2
  • Sedžvika pakāpieni: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibarda solis: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernova un Staseviča pieaugums: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Kā darbojas čaulas kārtošana?

  1. Pieņemsim, ka mums ir jāšķiro šāds masīvs. Sākotnējais masīvs
  2. (N/2, N/4,… 1Algoritmā kā intervālus izmantojam čaulas sākotnējo secību ).
    Pirmajā cilpā, ja masīva lielums ir N = 8tad, elementi, kas atrodas intervālā, N/2 = 4tiek salīdzināti un samainīti, ja tie nav kārtībā.
    1. 0. elements tiek salīdzināts ar 4. elementu.
    2. Ja 0. elements ir lielāks par ceturto, tad 4. elements vispirms tiek saglabāts tempmainīgajā lielumā un 0thelements (ti, lielāks elements) tiek saglabāts 4thpozīcijā, un elements, kas glabājas, temptiek saglabāts 0thpozīcijā. Pārkārtojiet elementus ar n / 2 intervālu
      Šis process turpinās visiem pārējiem elementiem. Pārkārtojiet visus elementus ar n / 2 intervālu
  3. Otrajā cilpā N/4 = 8/4 = 2tiek ņemts intervāls un atkal tiek sakārtoti šajos intervālos gulošie elementi. Pārkārtojiet elementus ar n / 4 intervālu
    Šajā brīdī jūs varat sajaukt. Visi masīva elementi, kas atrodas pašreizējā intervālā, tiek salīdzināti.
    Tiek salīdzināti 4. un 2ndpozīcijas elementi . Tiek 0thsalīdzināti arī elementi 2. un pozīcijā. Visi masīva elementi, kas atrodas pašreizējā intervālā, tiek salīdzināti.
  4. Tas pats process notiek arī attiecībā uz atlikušajiem elementiem. Pārkārtojiet visus elementus ar n / 4 intervālu
  5. Visbeidzot, kad intervāls ir, N/8 = 8/8 =1tiek sakārtoti masīva elementi, kas atrodas intervālā 1. Masīvs tagad ir pilnībā sakārtots. Pārkārtojiet elementus ar n / 8 intervālu

Korpusa kārtošanas algoritms

 shellSort (masīvs, izmērs) intervālam i <- size / 2n līdz 1 katram intervālam "i" masīvā kārtot visus elementus intervālā "i" beigu shellSort

Python, Java un C / C ++ piemēri

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); )

Sarežģītība

Korpusa kārtošana ir nestabils šķirošanas algoritms, jo šis algoritms nepārbauda elementus, kas atrodas starp intervāliem.

Laika sarežģītība

  • Sliktākā gadījuma sarežģītība : mazāka vai vienāda ar sliktākā gadījuma sarežģītību čaulas kārtošanai vienmēr ir mazāka vai vienāda ar . Saskaņā ar Poonena teorēmu sliktākajā gadījumā čaulas veida sarežģītība ir vai vai vai kaut kas pa vidu .O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Labākā gadījuma sarežģītība : O(n*log n)
    kad masīvs jau ir sakārtots, kopējais salīdzinājumu skaits katram intervālam (vai pieaugumam) ir vienāds ar masīva lielumu.
  • Vidējā lietu sarežģītība : O(n*log n)
    tā ir aptuveni .O(n1.25)

Sarežģītība ir atkarīga no izvēlētā intervāla. Iepriekš minētās sarežģītības atšķiras dažādām izvēlētām pieauguma secībām. Labākā pieauguma secība nav zināma.

Kosmosa sarežģītība:

Telpu sarežģītība čaulas kārtošanai ir O(1).

Shell kārtot lietojumprogrammas

Apvalka kārtošana tiek izmantota, ja:

  • kaudzes izsaukšana ir virs galvas. uClibc bibliotēka izmanto šo veidu.
  • rekursija pārsniedz robežu. bzip2 kompresors to izmanto.
  • Ievietošanas kārtošana nedarbojas labi, ja tuvie elementi atrodas tālu viens no otra. Korpusa kārtošana palīdz samazināt attālumu starp tuvajiem elementiem. Tādējādi būs mazāks veicamo maiņu skaits.

Interesanti raksti...