Sortowanie Shella

[Robakks]

Jak zmodyfikować sortowanie przez wstawianie aby otrzymać sortowanie Shella

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

Jak dobrać optymalny ciąg odstępów
Oszacować pesymistyczną złożoność z ciągiem Pratta

[Robakks]

Sortowanie przez wstawianie zmodyfikowałem w następujący sposób
Zamieniłem pierwszą nierówność z linii 7 na nierówność nieostrą co dało jedynkę ,
Zamieniłem wszystkie wystąpienia jedynki oprócz inkrementacji z linii 3
na wprowadzoną zmienną h będącą odstępem
Wprowadziłem zewnętrzną pętle w której realizowałem
sortowanie przez wstawianie z odstępem h
a następnie zmniejszałem odstęp

Jeśli chodzi o generowanie ciągu Pratta to
na stronie z ciągami całkowitymi http://oeis.org/A003586
mają pewien pomysł działający w czasie liniowym
Po wygenerowaniu tego ciągu można odwrócić w nim kolejność wyrazów
Odwrócenie kolejności wyrazów można także zrealizować w czasie liniowym
To czy ciąg powinien mieć wartownika zależy od tego jakiej pętli zewnętrznej chcemy użyć