[Algorytmy][C] Sortowanie Shella

[Mariusz M]

Przepisać kod sortowania przez wstawianie tak aby realizował sortowanie Shella

Pseudokod z książki Cormena

Kod: Zaznacz cały

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

Wersja dla tablic indeksowanych od zera jak w C

Kod: Zaznacz cały

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 Hibbarda czy Knutha dość łatwo wygenerować i nie trzeba ich trzymać w tablicy

Wygenerować ciąg Pratta którego wyrazy są postaci \(\displaystyle{ 2^{p}3^{q} \qquad p,q \in \mathbb{N}}\)
bez marnowania pamięci
(tablicę na wyrazy ciągu Pratta należy zaallokować tak aby pomieściła tyle wyrazów ciągu ile potrzebujemy Jeżeli mamy do dyspozycji tylko pętlę while jak w Pythonie to do ciągu Pratta dołączamy jeszcze zero jako wartownika)

Trochę o ciągu Pratta mają tutaj

Kod: Zaznacz cały

https://oeis.org/A003586

Spostrzeżenie Roberta G Wilsona pozwoli przesiać liczby z przedziału \(\displaystyle{ 1 \ldots n}\)
ale sposób ten jest zbyt wolny
Hai He i Gilbert Traub pokazali sposób generowania tego ciągu który może być przydatny
Robert G Wilson podał też sposób liczenia wyrazów tego ciągu
ale wymaga on dużo operacji zmiennoprzecinkowych

Jak obliczyć złożoność czasową dla sortowania Shella mając dany ciąg odstępów

Czy macie jakieś własne ciągi dla sortowania Shella ?

Samo przepisanie kodu sortowania przez wstawianie na sortowanie Shella
nie jest aż takie trudne , ot takie odprężające zadanie
Ciekawsze są pytania związane z ciągami odstępów dla sortowania Shella
Niektóre z tych pytań są nadal otwarte tak jak pytanie o optymalny ciąg odstępów