Sortowania Mariusz: 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 zmodyfikować ten kod sortowania przez wstawianie aby otrzymać sortowanie Shella https://matematykaszkolna.pl/forum/333816.html Tutaj jc twierdzi że Spojrzałem. Kiedy kończy Ci się pętla w Przesiewaniu? Wydaje się, że dopiero, gdy dojdziesz do krawędzi. A często powinna skończyć się wcześniej. Jednak czy aby na pewno dojdzie z tym przesiewaniem do krawędzi ? Aby kod działał wystarczy dopisać jedną instrukcję ale aby kod był nieco bardziej czytelny proponuję wprowadzić zmienną logiczną tzw flagę Swoją drogą podobna funkcja przesiewająca jest u Wirtha w jego książce o algorytmach i strukturach danych

Mariusz: Jak wygenerowalibyście ciąg Pratta ? Metoda sita oparta na spostrzeżeniu Roberta G. Wilsona z https://oeis.org jest zbyt wolna ponieważ ma złożoność O(n²) a aby ten ciąg był użyteczny do sortowania powinien mieć złożoność O(n)

sata: Oj Mariuszu czego tu nie rozumiesz? while(zzz) { for(j = n − zzz − 1; j >= 0; j−−) { x = bufor[j]; i = j + zzz; while((i < n) && (x > bufor[i])) { bufor[i − zzz] = bufor[i]; i += zzz; } bufor[i − zzz] = x; } zzz /= 3; } zzz− ciąg odstepów co i jak przekazesz to juz twoja broszka C++ oferuje dużo mozliwości

heheszek: sposobow implementacji sa miljony...

Mariusz: Ja trochę inaczej zmodyfikowałem ten kod Z grubsza rzecz biorąc zamieniłem jedynki na krok h i dopisałem zewnętrzną pętle void sortowanie__ przez__ wstawianie(int *tab,int n) { int h=1; while(h <= n) { h *= 3; h++; } while(h > 0) { //Tutaj jedynki przy inkrementacji iteratora nie zmieniłem na h for(int i=h;i<n;i++) { int j=i; int bufor=tab[j]; //Tutaj zamieniłem nierówność ostrą na nieostrą aby otrzymać jedynke while((j>=h)&&(tab[j−h]>bufor)) { tab[j]=tab[j−h]; j −= h; } tab[j]=bufor; } h /= 3; } } Jak widać nie wszystkie jedynki zamieniłem na h jak twierdzi Sedgewick w swej książce "One way to implement Shellsort would be, for each h , to use insertion sort independently on each of the h subfiles (Sentinels would not be used because there would have to be h of them,for largest value of h used.) But it turns out to be much easier then that: If we replace every occurrence of "1" by "h" (and "2" by "h + 1") in insertion sort, the resulting program h−sorts the file and leads to a compact Shellsort implementation" Jeśli chodzi o ciągi takie jak ten Knutha to nie trzeba ich wyrazów przechowywać w tablicy Na tej stronce z ciągami całkowitymi jest propozycja wygenerowania ciągu Pratta ale wyrazy tego ciągu trzeba zapamiętać w tablicy i dobrze by było obliczyć bądź oszacować liczbę wyrazów tego ciągu aby zaallokować odpowiednią ilość pamięci na tablicę Jak dla danego ciągu odstępów oszacować złożoność czasową Masz jakiś swój ciąg odstępów który dałby szybszy algorytm niż po zastosowaniu ciągu Pratta ? Wikipedie twierdzą że ciąg Pratta daje złożoność O(nlog²(n))