Witam.
Przeszukalem juz chyba wszystkie dostepne strony w internecie i dalej nie moge wiele na ten temat znalezc. Chodzi mi o algorytm sortowania bibliotecznego
(angielska nazwa to library sort lub tez gapped insertion sort). Wiem mniej wiecej co to jest, wiem ze jest podobny do zwyklego algorytmu sortowania przez wstawianie.
Różni się tym że wstawia dodatkowo puste przestrzenie aby dodatkowo potem nie przesowac calej tablicy tak czesto. Dzieki temu jego zlozonosc jest nieco mniejsza niz
standardowego przez wstawianie. Nie moge jednak znalezc dokladnego opisu jak te miejsca wstawiac itp. Zadnego pseudokodu ani implementacji. Czy ktos ma cos na ten temat lub tez robil cos na ten temat. Dziekuje i pozdrawiam.
0
0
No ale o co chodzi? Jak to nie wiesz jak robić sobie puste miejsca? Normalnie, robisz tablicę większą niż jest potrzebna i pomiędzy elementami zostawiasz sobie trochę miejsc.
0
Ale czy jest z gory powiedziane ile tych miejsc? Podam przyklad. Mam tablice : 7,9,1,2,6,8
Niech x bedzie naszym pustym miejscem. Na poczatku mam :
7,x
W drugim kroku mam 9, wiec dostawiam na koniec i mam:
7,x,9,x
Potem mam 1, czyli musze calosc przesunac i mam:
1,x,7,x,9,x
Teraz mam 2 czyli wstawiam w puste miejsce:
1,2,7,x,9,x
Teraz mam 6 czyli znowu przesowam (i nie wiem czy dostawiam puste miejsce za 6)
1,2,6,7,x,9,x
I na koniec 8 w puste miejsce:
1,2,6,7,8,9,x
Czy dobrze czy zle? Czy wiecej miejsc zostawiac czy mniej? Nie wiem dokladnie jaki jest opis algorytmu.
0
No prawie dobrze to rozpisałeś, powinno to wyglądać tak:
Niech x bedzie naszym pustym miejscem. Na poczatku mam :
7,x
W drugim kroku mam 9, wiec dostawiam na koniec i mam: <na końcu się nie daje pustego miejsca, bo po co>
7,x,9
Potem mam 1, czyli musze calosc przesunac i mam:
1,x,7,x,9
Teraz mam 2 czyli wstawiam w puste miejsce: <tutaj zapomniałeś o pustym miejscu po 2>
1,2,x,7,x,9
Teraz mam 6 czyli znowu przesowam (i nie wiem czy dostawiam puste miejsce za 6) <tak, dostawiasz>
1,2,6,x,7,x,9
I na koniec 8 w puste miejsce: <tutaj już można pominąć puste miejsce, jako, że to jest ostatnia liczba do wstawienia.
1,2,6,x,7,8,9
I po tym wypisujesz liczby, pomijając puste miejsca.
0
Dzieki za odpowiedz, jednak dalej cos jest dla mnie niezrozumialem. Algorytm sortowania bibliotecznego opiera sie na algorytmie sortowania przez wstawianie. Dzieki tym pustym miejscom nie musimy za kazdym razem przesowac calosci w prawo. Wstawiajac za kazdym razem element i puste miejsce, za kazdym razem musimy przesowac calosc w prawo,
co w efekcie daje nam algorytm sortowania przez wstawianie. Czy cos zle rozumiem?
0
W sumie racja, ale z drugiej strony, skąd wiesz czy za dany element wstawisz jeszcze jedną rzecz czy 50? Przy 50, raptem o jeden raz mniej będziesz musiał przesuwać całą tablicę.
0
Witam,
Odkopuje temat.
Potrzebuję zrobić projekt który porównuje algorytmy sortowania pozycyjnego i bibliotecznego pod względem szybkości działania i zapotrzebowania na pamięć.
Pozycyjny już mam, a nigdzie nie mogę znaleźć kodu sortowania bibliotecznego.
Wolał bym mieć pewność, że mój kod jest poprawny i dlatego nie chciał bym go pisać samemu "tak jak mi się wydaje".
Chce po prostu żeby wyniki były wiarygodne.
Mógł by ktoś podać kod samego sortowania bibliotecznego?
Dzięki za pomoc.
0
Ponownie proszę o pomoc, chociaż jakiś pseudokod.
0
Ehh ponawiam prośbę o pomoc.
Może ktoś wytłumaczyć jak się zostawia te puste miejsca i w jaki sposób przesuwa się tablice kiedy wstawiam jakiś element?
To dla mnie bardzo ważne dlatego tak "jęczę". Wytłumaczyć to to 5 min roboty, a dla mnie kilka dni martwienia się i szperania w internecie.....