Przepisać kod sortowania przez wstawianie tak aby otrzymać sortowanie Shella
Pseudokod z CLRS
Insertion-Sort(A) for j := 2 to length[A] do key := A[j] (* Wstaw A[j] w posortowany ciąg A[1..j - 1] *) i := j - 1 while i > 0 and A[i] > key do A[i + 1] := A[i] i := i - 1 A[i + 1] := key
Dla tablic indeksowanych od zera jak w C
void sortowanie_przez_wstawianie(int *tab,int n) { for(int i=1;i<n;i++) { int j=i; int bufor=tab[j]; while((j>0)&&(tab[j-1]>bufor)) { tab[j]=tab[j-1]; j--; } tab[j]=bufor; } }
Ciągi takie jak Hibbarda czy Knutha stosunkowo łatwo wygenerować a ich wyrazów nie trzeba przechowywać w tablicy
Jeśli chodzi o ciąg zaproponowany przez Pratta to
trochę o nim jest na stronie https://oeis.org/A003586
Tutaj spostrzeżenie Roberta Wilsona pozwoli przesiać liczby z przedziału
ale to jest zbyt wolny sposób
Hai He i Gilbert Trau dają sposób który mógłby być wykorzystany
Jeśli chodzi o ciąg Pratta to problemem może być obliczenie bądź oszacowanie liczby elementów w tym ciągu
(musimy wiedzieć ile pamięci zaallokować na tablicę dla ciągu)
Sposób przedstawiony na tej stronce wymaga sporo operacji zmiennoprzecinkowych
Jak oszacować złożoność czasową sortowania Shella dla danego ciągu odstępów ?
Czy macie własny ciąg odstępów dla sortowania Shella