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.
Sortowanie szybkie, sortowanie bąbelkowe... W takiej skali nie robi to większej różnicy, chyba że celujesz w bardzo wolne procesory.
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 ? ?
Porównaj złożoność sortowania przez wstawianie, a sortowania bąbelkowego - jak myślisz: da radę?
ok
Jeśli dane to liczby całkowite z jakiegoś małego przedziału, to możesz sortować przez zliczanie - prosto i szybko. Wiki
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.
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ć.
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>
.
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.