Sortowanie Shella

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Robakks
Czasem tu bywam
Czasem tu bywam
Posty: 126
Rejestracja: 30 wrz 2012, 20:36
Podziękowania: 2 razy
Otrzymane podziękowania: 10 razy
Płeć:

Sortowanie Shella

Post autor: Robakks » 18 mar 2018, 05:20

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
Czasem tu bywam
Czasem tu bywam
Posty: 126
Rejestracja: 30 wrz 2012, 20:36
Podziękowania: 2 razy
Otrzymane podziękowania: 10 razy
Płeć:

Re: Sortowanie Shella

Post autor: Robakks » 19 mar 2018, 15:15

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ć