Jakie sortowanie? ( C ) .

Odpowiedz Nowy wątek
2018-04-14 16:16
0

Witam mam zrobić algorytm sortujący dostosowany do małej ilości danych tzn. 35 i mniej, dane się powtarzają.
Moje pytania: Jakiego użyć algorytmu do powyższego przykładu ? A jakiego gdyby danych było więcej ?
Z racji tego, że dopiero zaczynam bardzo proszę o pomoc. Język C.

Pozostało 580 znaków

2018-04-14 16:20
0

Sortowanie szybkie, sortowanie bąbelkowe... W takiej skali nie robi to większej różnicy, chyba że celujesz w bardzo wolne procesory.


Pozostało 580 znaków

2018-04-14 16:33
0
Patryk27 napisał(a):

Sortowanie szybkie, sortowanie bąbelkowe... W takiej skali nie robi to większej różnicy, chyba że celujesz w bardzo wolne procesory.

A gdybym użył InsertionSort, spełni te wymagania ? ?

Pozostało 580 znaków

2018-04-14 17:33
0

Porównaj złożoność sortowania przez wstawianie, a sortowania bąbelkowego - jak myślisz: da radę?


Myślę, że właśnie w przypadku małych danych analiza złożoności nie ma absolutnie żadnego znaczenia. - enedil 2018-04-14 18:56
Zależy o jak szybkim procesorze mówimy :-) - Patryk27 2018-04-14 20:36
Nie zależy. Analiza złożoności mówi jak problem się skaluje, a nie jak zachowuje się dla malutkich danych. Za pomocą wielkiego O nie odpowiesz niestety na pytanie "co się dzieje dla małych danych". - enedil 2018-04-14 21:30

Pozostało 580 znaków

2018-04-14 19:40
0

ok

Pozostało 580 znaków

2018-04-14 20:54
Wesoły Wąż
1

Jeśli dane to liczby całkowite z jakiegoś małego przedziału, to możesz sortować przez zliczanie - prosto i szybko. Wiki

Pozostało 580 znaków

2018-04-17 21:26
Trzeźwy Kret
1
Prezes napisał(a):

Witam mam zrobić algorytm sortujący dostosowany do małej ilości danych tzn. 35 i mniej, dane się powtarzają.
Moje pytania: Jakiego użyć algorytmu do powyższego przykładu ? A jakiego gdyby danych było więcej ?

Przy 35 wartościach jakikolwiek algorytm, a gdyby danych było więcej quicksort lub coś opartego na nim.

Pozostało 580 znaków

2018-04-21 09:55

To zależy co to za dane.
Jak sortujesz bajty to polecam sortowanie przez zliczanie.
Jak to są łańcuchy o długości kilku megabajtów to quick sort.

Jeśli chodzi o procesor to o który chodzi ma znaczenie jeśli to jest procesor bez cache.
Przy cache złożoność ma minimalne znaczenie.
Bez cache warto się wysilić.

Pozostało 580 znaków

2018-04-21 10:41
1

Jak to się mówi "If doubt, use brute force" czyli sortowanie bąbelkowe i zobacz czy wystarczy. To zakładając, że masz sam implementować. Jeśli nie to możesz użyć funkcji qsort z <stdlib.h>.

edytowany 2x, ostatnio: elwis, 2018-04-23 08:51
Pokaż pozostałe 5 komentarzy
Nie żeby cokolwiek, ale ciężko wierzyć w dokładny sens tego co mówisz, jeśli If doubt, use brute force, jako zdanie gramatycznie błędne, nie ma żadnego znaczenia - enedil 2018-04-23 18:27
Jest mniej więcej tak poprawne jak twój powyższy komentarz. W angielskim nie wolno używać równoważników zdania? Wiem, że bardziej typowo byłoby "If in doubt", ale bez przesady. Purysta z ciebie. Get a life. - elwis 2018-04-23 22:24
Dokładnie: "When in doubt, use brute force", tak to powiedział Ken Thompson. Taka wielka różnica? Rly? - elwis 2018-04-23 22:53
Ja tylko wspomniałem, że niestety co innego możesz mieć na myśli, a co innego może mieć na myśli autor cytatu, który wykorzystujesz. (czyli możesz wiedzieć lepiej co masz na myśli, ale niestety myśl czym innym, a słowa czym innym). Komentarz dot. angielskiego był zwyczajną uszczypliwością. - enedil 2018-04-23 23:21
I sugerujesz, że tak jest? No proszę cię. Po prostu się czepiasz. - elwis 2018-04-24 09:44

Pozostało 580 znaków

2018-04-22 08:44
0

Zawsze możesz użyć armaty na muchę, czyli hybrid introsort i zapomnieć o warunkach (czy danych jest dużo czy mało, jaki jest ich charakter, czy są wstępnie posortowane) - i tak będzie dobrze.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0