Razvrstitev lupine

V tej vadnici boste izvedeli, kako deluje razvrščanje lupine. Prav tako boste našli delovne primere razvrščanja lupine v jezikih C, C ++, Java in Python.

Razvrščanje po lupini je algoritem, ki najprej razvršča elemente daleč drug od drugega in zaporedno zmanjšuje interval med elementi, ki jih je treba razvrstiti. To je splošna različica vstavljanja.

Pri razvrščanju lupine so elementi v določenem intervalu razvrščeni. Interval med elementi se postopoma zmanjšuje glede na uporabljeno zaporedje. Uspešnost razvrščanja lupine je odvisna od vrste zaporedja, uporabljenega za dano vhodno matriko.

Nekatera uporabljena optimalna zaporedja so:

  • Prvotno zaporedje školjke: N/2 , N/4 ,… , 1
  • Knuthovi prirastki: 1, 4, 13,… , (3k - 1) / 2
  • Prirastki Sedgewicka: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibbardovi prirastki: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Prirastek Papernov & Stasevich: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Kako deluje sortiranje lupine?

  1. Recimo, da moramo razvrstiti naslednjo matriko. Začetno polje
  2. (N/2, N/4,… 1Kot intervale v našem algoritmu uporabljamo izvirno zaporedje lupine ).
    Če je velikost matrike v prvi zanki, N = 8se elementi, ki ležijo v intervalu N/2 = 4, primerjajo in zamenjajo, če niso v redu.
    1. 0. element se primerja s 4. elementom.
    2. Če je 0. element večji od četrtega, se četrti element najprej shrani v tempspremenljivko in 0thelement (tj. Večji element) shrani v 4thpoložaj, element, shranjen v, temppa v 0thpoložaj. Prerazporedite elemente v intervalu n / 2
      Ta postopek se nadaljuje za vse preostale elemente. Prerazporedite vse elemente v intervalu n / 2
  3. V drugi zanki se vzame interval N/4 = 8/4 = 2in elementi, ki ležijo v teh intervalih, se spet razvrstijo. Prerazporedite elemente v intervalu n / 4
    V tem trenutku se lahko zmedete. Primerjajo se vsi elementi v matriki, ki ležijo v trenutnem intervalu.
    Primerjajo se elementi na 4. in 2ndpoložaju. Primerjajo se tudi elementi na 2. in 0thpoložaju. Primerjajo se vsi elementi v matriki, ki ležijo v trenutnem intervalu.
  4. Enak postopek se nadaljuje za preostale elemente. Prerazporedite vse elemente v intervalu n / 4
  5. Nazadnje, ko je interval, so N/8 = 8/8 =1elementi matrike, ki ležijo v intervalu 1, razvrščeni. Matrika je zdaj popolnoma razvrščena. Prerazporedite elemente v intervalu n / 8

Algoritem razvrščanja lupine

 shellSort (matrika, velikost) za interval i <- velikost / 2n do 1 za vsak interval "i" v matriki razvrsti vse elemente v intervalu "i" na koncu shellSort

Primeri Python, Java in C / C ++

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

Kompleksnost

Razvrščanje lupine je nestabilen algoritem za razvrščanje, ker ta algoritem ne preučuje elementov, ki ležijo med intervali.

Zapletenost časa

  • Najslabša zapletenost : manjša ali enaka najslabši zapletenosti za razvrščanje lupine je vedno manjša ali enaka . Po Poonen izreka, v najslabšem primeru kompleksnost za lupine vrste je ali ali ali nekaj vmes.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Najboljša zapletenost : O(n*log n)
    Ko je polje že razvrščeno, je skupno število primerjav za vsak interval (ali prirastek) enako velikosti polja.
  • Povprečna zapletenost primera : O(n*log n)
    približno je .O(n1.25)

Zapletenost je odvisna od izbranega intervala. Zgornje zapletenosti se razlikujejo za različna izbrana zaporedja prirastkov. Najboljše zaporedje prirastkov ni znano.

Zapletenost vesolja:

Prostorska zapletenost za razvrščanje lupine je O(1).

Aplikacije za razvrščanje lupine

Razvrščanje lupine se uporablja, kadar:

  • klicanje sklada je zgoraj. Knjižnica uClibc uporablja to vrsto.
  • rekurzija preseže mejo. bzip2 kompresor ga uporablja.
  • Razvrščanje vstavkov ne deluje dobro, če so elementi od blizu oddaljeni. Razvrščanje lupine pomaga zmanjšati razdaljo med bližnjimi elementi. Tako bo izvedeno manj zamenjav.

Zanimive Članki...