Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Sortowanie , usuwanie rekurencji , ciągi odstępów dla sortowania Shella

Mariusz LM 01 Kwi 2018 21:58 438 1
  • #1 01 Kwi 2018 21:58
    Mariusz LM
    Poziom 1  

    W sortowaniu stogowym Cormen i reszta podają pseudokod procedury przywracającej kopiec z użyciem rekurencji.
    Jak zapisać równoważną procedurę w sposób iteracyjny?

    Kod: delphi
    Zaloguj się, aby zobaczyć kod


    Sortowanie przez podział z użyciem stosu mogłoby wyglądać tak:
    Kod: delphi
    Zaloguj się, aby zobaczyć kod


    Kod: delphi
    Zaloguj się, aby zobaczyć kod


    Kod: delphi
    Zaloguj się, aby zobaczyć kod


    Jak zmieni się iteracyjny odpowiednik, gdy dopiszemy do procedury rekurencyjnej wywołanie kolejnej procedury?

    Rekurencyjna procedura Quicksort:
    Kod: delphi
    Zaloguj się, aby zobaczyć kod


    Jak będzie wyglądać procedura iteracyjna, gdy do procedury rekurencyjnej dopiszemy jeszcze jedną procedurę?
    Kod: delphi
    Zaloguj się, aby zobaczyć kod


    Cormen i reszta podają następujący kod sortowania przez wstawianie:
    Kod: delphi
    Zaloguj się, aby zobaczyć kod


    Jak zmodyfikować ten pseudokod, aby realizował sortowanie Shella?

    Ciągi Hibbarda i Knutha dość łatwo wygenerować, a ich wyrazów nie trzeba przechowywać w tablicy.
    Jeśli chodzi o ciąg Pratta, to jak oszacować liczbę jego wyrazów?
    Liczba wyrazów tego ciągu jest przydatna do tego, aby wiedzieć ile pamięci zaallokować na tablicę dla tego ciągu.
    Trochę o tym ciągu mają na stronie z ciągami całkowitymi.

    Jak oszacować złożoność obliczeniową dla danego ciągu odstępów?
    Czy macie własny ciąg odstępów dla sortowania Shella?

    (*Próbowałem dawać wcięcia jak w książce CLRS ale po wysłaniu mi nie ich nie zapisało*)

    Moderowany przez Marek_Skalski:

    Proszę w przyszłości używać znaczników syntax. Tym razem poprawiłem.

    0 1
  • #2 19 Kwi 2018 23:21
    trol.six
    Poziom 30  

    Kiedyś napisałem/przepisałem znaleziony w sieci algorytm sortowania shella, wykorzystujący ciąg, którego ponoć Donald Knuth jest autorem. Wylicza on wartość ciągu maksymalną, czyli największy odstęp, następne kolejne mniejsze w pętli.
    Oto przykład w C:

    Kod: c
    Zaloguj się, aby zobaczyć kod

    Natomiast zerkając na wikipedię można zobaczyć inne ciągi ale generowane są one od wartości 1 w górę. Więc wygodnie jest je stablicować, inaczej trzeba będzie liczyć za każdym razem z jakąś zmienną pomocniczą.

    Przykład w C wykorzystujący prosty wzór na kolejna wartość ciągu:

    Kod: c
    Zaloguj się, aby zobaczyć kod


    Z praktyki moge powiedzieć, że zaczyna sortować szybciej niż poprzedni kod, jeśli mamy danych więcej niż ok 500000.

    0