Sortowanie powłoki

W tym samouczku dowiesz się, jak działa sortowanie powłoki. Znajdziesz również działające przykłady sortowania powłoki w językach C, C ++, Java i Python.

Sortowanie powłoki to algorytm, który najpierw sortuje elementy daleko od siebie i sukcesywnie zmniejsza odstępy między sortowanymi elementami. Jest to uogólniona wersja sortowania przez wstawianie.

W przypadku sortowania powłoki sortowane są elementy w określonych odstępach czasu. Odstęp między elementami jest stopniowo zmniejszany w zależności od zastosowanej kolejności. Wydajność sortowania powłoki zależy od typu sekwencji użytej dla danej tablicy wejściowej.

Oto niektóre z optymalnych sekwencji:

• Oryginalna sekwencja Shell: N/2 , N/4 ,… , 1
• Przyrosty Knutha: 1, 4, 13,… , (3k - 1) / 2
• Przyrosty Sedgewicka: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
• Przyrosty Hibbarda: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• Przyrost 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… .

Jak działa sortowanie powłoki?

1. Załóżmy, że musimy posortować następującą tablicę. Tablica początkowa
2. Używamy oryginalnej sekwencji powłoki (N/2, N/4,… 1) jako interwałów w naszym algorytmie.
   W pierwszej pętli, jeśli rozmiar tablicy wynosi N = 8wtedy, elementy leżące w przedziale N/2 = 4są porównywane i zamieniane, jeśli nie są w kolejności.
   1. Element zerowy jest porównywany z elementem czwartym.
   2. Jeśli zerowy element jest większy od czwartego, to czwarty element jest najpierw zapisywany w tempzmiennej, a 0thelement (tj. Większy element) jest zapisywany w 4thpozycji, a element przechowywany w tempjest zapisywany w 0thpozycji. Przestaw elementy w odstępach n / 2
      Ten proces jest kontynuowany dla wszystkich pozostałych elementów. Przestaw wszystkie elementy w odstępach n / 2
3. W drugiej pętli N/4 = 8/4 = 2pobierany jest przedział i ponownie sortowane są elementy leżące w tych przedziałach. Zmień rozmieszczenie elementów w odstępach n / 4
   W tym momencie możesz się pomylić. Porównywane są wszystkie elementy tablicy leżące w bieżącym interwale. Porównywane są
   elementy na 4. i 2ndpozycji. 0thPorównywane są również elementy na 2. i pozycji. Porównywane są wszystkie elementy tablicy leżące w bieżącym interwale.
4. Ten sam proces dotyczy pozostałych elementów. Przestaw wszystkie elementy w odstępach n / 4
5. Wreszcie, gdy przedział jest N/8 = 8/8 =1równy, sortowane są elementy tablicy leżące w przedziale 1. Tablica jest teraz całkowicie posortowana. Przestaw elementy w odstępach n / 8

Algorytm sortowania powłoki

 shellSort (tablica, rozmiar) dla interwału i <- size / 2n aż do 1 dla każdego interwału "i" w tablicy sortuj wszystkie elementy w przedziale "i" koniec shellSort

Przykłady w Pythonie, Javie i 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); ) 

Złożoność

Sortowanie przez powłokę jest niestabilnym algorytmem sortowania, ponieważ algorytm ten nie bada elementów leżących pomiędzy interwałami.

Złożoność czasowa

• Złożoność najgorszego przypadku : mniejsza lub równa Złożoność najgorszego przypadku dla sortowania powłokowego jest zawsze mniejsza lub równa . Według Poonen twierdzenia, w najgorszym przypadku złożoność jest dla Sortowanie Shella lub lub lub coś pomiędzy.O(n2)
O(n2)
Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
• Złożoność najlepszego przypadku : O(n*log n)
  gdy tablica jest już posortowana, całkowita liczba porównań dla każdego przedziału (lub przyrostu) jest równa rozmiarowi tablicy.
• Średnia złożoność przypadku : O(n*log n)
  to około .O(n1.25)

Złożoność zależy od wybranego interwału. Powyższe złożoności różnią się dla różnych wybranych sekwencji przyrostowych. Najlepsza sekwencja przyrostu jest nieznana.

Złożoność przestrzeni:

Złożoność przestrzeni dla sortowania powłoki wynosi O(1).

Aplikacje sortowania powłoki

Sortowanie powłoki jest używane, gdy:

• wywołanie stosu jest na górze. Biblioteka uClibc używa tego rodzaju.
• rekurencja przekracza limit. Używa go kompresor bzip2.
• Sortowanie przez wstawianie nie działa dobrze, gdy elementy bliskie są daleko od siebie. Sortowanie skorupowe pomaga zmniejszyć odległość między bliskimi elementami. W związku z tym liczba zamian do wykonania będzie mniejsza.