Korpuso rūšiavimas

Šioje pamokoje sužinosite, kaip veikia „shell“ rūšiavimas. Be to, rasite darbinių apvalkalų rūšiavimo pavyzdžių C, C ++, Java ir Python.

Korpuso rūšiavimas yra algoritmas, kuris pirmiausia rūšiuoja elementus toli vienas nuo kito ir nuosekliai sumažina intervalą tarp rūšiuojamų elementų. Tai apibendrinta įterpimo rūšiavimo versija.

Korpuso rūšiavimo elementai yra rūšiuojami tam tikru intervalu. Intervalas tarp elementų palaipsniui mažinamas, atsižvelgiant į naudojamą seką. Korpuso rūšiavimo našumas priklauso nuo tam tikros įvesties masyvo naudojamos sekos tipo.

Keletas optimalių naudojamų sekų yra:

  • Originali „Shell“ seka: N/2 , N/4 ,… , 1
  • Knuto žingsniai: 1, 4, 13,… , (3k - 1) / 2
  • Sedgewicko žingsniai: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibbardo žingsniai: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernovo ir Stasevičiaus prieaugis: 1, 3, 5, 9, 17, 33, 65,…
  • Prattas: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Kaip veikia „Shell Sort“?

  1. Tarkime, turime surūšiuoti šį masyvą. Pradinis masyvas
  2. (N/2, N/4,… 1Algoritme mes naudojame pirminę apvalkalo seką ) kaip intervalus.
    Pirmoje kilpoje, jei masyvo dydis yra N = 8tada, elementai, esantys tarpais, N/2 = 4yra lyginami ir keičiami, jei jie nėra tvarkingi.
    1. 0 elementas lyginamas su 4 elementu.
    2. Jei 0-asis elementas yra didesnis nei 4-asis, tada 4-asis elementas pirmiausia saugomas tempkintamajame ir 0thelementas (ty didesnis elementas) saugomas 4thpozicijoje, o elementas, kuriame saugomas, tempyra 0thpadėtyje. Pertvarkykite elementus n / 2 intervalu.
      Šis procesas tęsiamas visiems likusiems elementams. Pertvarkykite visus elementus 2/2 intervalais
  3. Antroje kilpoje N/4 = 8/4 = 2imamas intervalas ir vėl rūšiuojami šiais intervalais gulintys elementai. Pertvarkykite elementus n / 4 intervalais
    . Šiuo metu galite supainioti. Palyginami visi masyvo elementai, esantys ties dabartiniu intervalu. Palyginami
    elementai 4 vietoje ir 2ndpadėtis. Taip 0thpat lyginami 2-os ir pozicijos elementai . Palyginami visi masyvo elementai, esantys ties dabartiniu intervalu.
  4. Tas pats procesas vyksta ir likusiems elementams. Pertvarkykite visus elementus n / 4 intervalais
  5. Galiausiai, kai intervalas yra N/8 = 8/8 =1tada, rūšiuojami masyvo elementai, esantys 1 intervalu. Masyvas dabar yra visiškai surūšiuotas. Pertvarkykite elementus 8/8 intervalais

„Shell“ rūšiavimo algoritmas

 „shellSort“ (masyvas, dydis) i intervalui <- dydis / 2n iki 1 kiekvienam masyvo „i“ intervalui rūšiuoti visus elementus intervale „i“ pabaigos shellSort

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

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

Sudėtingumas

Korpuso rūšiavimas yra nestabilus rūšiavimo algoritmas, nes šis algoritmas netiria elementų, esančių tarp intervalų.

Laiko kompleksiškumas

  • Blogiausio atvejo sudėtingumas : blogesnio atvejo sudėtingumas apvalkalo rūšiavimui visada yra mažesnis arba lygus . Pasak Poonen teorema, blogiausiu atveju sudėtingumo lukštais rūšiuoti yra arba arba ar kažkas tarp jų.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Geriausio atvejo sudėtingumas : O(n*log n)
    Kai masyvas jau surūšiuotas, bendras kiekvieno intervalo (arba prieaugio) palyginimų skaičius yra lygus masyvo dydžiui.
  • Vidutinis atvejų sudėtingumas : O(n*log n)
    jis yra maždaug .O(n1.25)

Sudėtingumas priklauso nuo pasirinkto intervalo. Minėti sudėtingumai skiriasi atsižvelgiant į pasirinktas atskiras prieaugio sekas. Geriausia prieaugio seka nežinoma.

Erdvės sudėtingumas:

Korpuso rūšiavimo erdvės sudėtingumas yra O(1).

„Shell“ rūšiavimo programos

Korpuso rūšiavimas naudojamas, kai:

  • kviesti kaminą yra virš galvos. „uClibc“ biblioteka naudoja šią rūšį.
  • rekursija viršija ribą. „bzip2“ kompresorius jį naudoja.
  • Įterpimo rūšiavimas nėra gerai, kai artimi elementai yra toli vienas nuo kito. Korpuso rūšiavimas padeda sumažinti atstumą tarp artimų elementų. Taigi bus mažiau atliktinų keitimų.

Įdomios straipsniai...