Strona główna » Algorytmy » Sortowanie » Sortowanie Shella
 

Sortowanie Shella

https://mattomatti.com/fs22

Wstęp

Sortowanie Shella to algorytm sortowania, który jest uogólnieniem sortowania przez wstawianie. W tym sortowaniu dane są sortowane szybciej dzięki zastosowania odstępu pomiędzy zamienianymi miejscami.

Algorytm

Algorytm sortowania Shella to taki algorytm sortowania, który na początku ustala pewną przerwę p pomiędzy elementami, które mają pozostać posortowane. Następnie w pętli dla każdego kolejnego elementu co p-ty element jest zamieniany jeśli nie spełniają warunku posortowania. Na koniec iteracji przerwa p jest zmniejszana według pewnej reguły. Działanie algorytmu kończy się, gdy następna wyliczona przerwa jest mniejsza od 1.

Istnieje wiele różnych sposobów wyboru kolejnych wyrazów z sortowanej tablicy. Każdy z nich charakteryzuje się inną złożonością obliczeń. Przyjmijmy za n długość sortowanej tablicy. Oto przykłady niektórych z nich:

Wyraz początkowyNastępnyZłożonośćAutor
p = ⌊n/2⌋p' = ⌊p/2⌋O(n2) dla n = 2mD. Shell
p = 2k - 1p' = (p - 1)/2O(n3/2)Hibbard
p = (3k - 1)/2 ≤ ⌈n/3⌉p' = (p - 1)/3O(n3/2)D. Knuth

Przykład

Do posortowania jest tablica L:= {5, 1, 4, 2, 3}. Wybieramy oryginalne sortowanie zaproponowane przez Shella, więc pierwsza przerwa p = ⌊n/2⌋ = ⌊5/2⌋ = 2. Rozpocznamy sortowanie od elementu o indeksie 1 i przerwie p = 2.

Przerwa pTablicaKomentarz
2{5, 1, 4, 2, 3}zamiana 5 i 4
2{4, 1, 5, 2, 3}5 jest na pozycji, więc zostawiamy
2{4, 1, 5, 2, 3}3 nie na pozycji, więc cofamy tak długo, aż co p-ty wyraz posortowany
1{3, 1, 4, 2, 5}koniec tablicy, zmiana rozmiaru przerwy
1{3, 1, 4, 2, 5}zamiana 1 i 3
1{1, 3, 4, 2, 5}3 jest większe od 1, więc zostawiamy
1{1, 3, 4, 2, 5}4 większe od 3, więc zostawiamy
1{1, 3, 4, 2, 5}2 mniejsze od 4, więc cofamy tak długo, aż przed 2 będzie mniejszy element
1{1, 2, 3, 4, 5}wartość 5 jest większa od 4 zostawiamy
0{1, 2, 3, 4, 5}tablica została posortowana

Implementacja

Oto przykładowy kod funkcji sortującej zgodnie z metodą wyboru wielkości przerw według Shella.

C++
C#
  1. void sortuj(int* tab, int n) {
  2.   int przerwa = n / 2;
  3.   while(przerwa >= 1) {
  4.     for (int i = przerwa; i < n; i += 1) {
  5.       int temp = tab[i];
  6.       int j;
  7.       for (j = i; j >= przerwa && tab[j - przerwa] > temp; j -= przerwa)
  8.         tab[j] = tab[j - przerwa];
  9.       tab[j] = temp;
  10.     }
  11.     przerwa /= 2;
  12.   }
  13. }

(2.) Określ rozmiar przerwy początkowy, a następnie (3.) dopóki jest to możliwe to: (4.) dla każdego co p-tego elementu: (5. - 9.) przesuwaj go do tyłu tak długo, aż powstanie ciąg posortowany ( z co p-tego elementu). Na koniec (10.) iteracji zaktualizuj rozmiar przerwy.

Testowanie funkcji

Poniżej znajduje się fragment kodu, który wczytuje od użytkownika tablicę elementów, sortuje ją i wypisuje.

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "Podaj ilosc elementow: ";
  4.   cin >> n;
  5.   cout << "Podaj " << n << " elementow:\n";
  6.   int* lista = new int[n];
  7.   for (int i = 0; i < n; i++)
  8.     cin >> lista[i];
  9.   sortuj(lista, n);
  10.   cout << "Posortowana lista to:\n";
  11.   for (int i = 0; i < n; i++)
  12.     cout << lista[i] << " ";
  13.   delete lista;
  14.   system("pause");
  15.   return 0;
  16. }

Zadania

Zadanie 1

Napisz algorytm sortowania danych na podstawie algorytmu Shella tak, aby dane były uporządkowane malejąco. Za metodę wyboru kolejnej przerwy przyjmij metodą autorstwa D. Knutha. Przetestuj działanie napisanego kodu.