logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

Jak napisać program ShellSort z InsertSort dla różnych ciągów w C++?

nomad 17 Lip 2004 12:19 2635 1
REKLAMA
  • #1 747597
    nomad
    Poziom 10  
    Posty: 3
    Witam,
    Musze napisac program ktory bedzie realizowal sortowanie ShellSort z wykorzystaniem InsertSort dla roznych ciagow przyrostow.

    Prosze o pomoc w znalezieniu zrodel lub jakis materialow. Moze jest ktos kto takowe juz posiada lub poprostu wie jak taki program napisac Kazda sugestia mile widziana.

    Pozdrawiam
    Nomad
  • REKLAMA
  • #2 1007300
    denethor
    Poziom 11  
    Posty: 23
    Na tej stronce jest sporo o sortowaniu shella, ale do dzielenia ciągu na mniejsze części jest brana stała G równa n/2 czyli połowie długości ciągu.

    Podobno algorytm działa najefektywniej jeśli zaczyna się od
    G= (16n / pi)^1/3
    (może przy okazji ktoś przypomni jak się nazywał gostek, który wymyślił ten wzór?:) ), a kończy na G=1.

    Ale słyszałem też o innej wersji (a może to część jednej i tej samej? nie wiem, wszystko mi się poplątało :) i chciałem prosić żeby ktoś to wyprostował, bo na necie ciężko coś znaleźć), taką, że na końcu: G(1)=1
    wcześniejsze to: G(i) = 3*G(i-1) + 1
    jeszcze wcześniejsze to: G(i+1) = 3*G(i) + 1
    i tak dalej, aż dojdziemy do: G(t) takiego, że: G(t+2) >= n

    Więc jak to rzeczywiście powinno być?
    I jak generować to G w trakcie sortowania??
REKLAMA