Witajcie !
Przychodze do was z problemem/pytaniem - mianowicie mam zadanie aby wybrać najlepszy algorytm do posortowania (rosnąco/niemalejąco) prawie posortowanej tablicy (z liczbami całkowitymi). Prawie posortowana tablica to znaczy: pierwsza połowa tablicy jest posortowana rosnąco, natomiast druga połowa tablicy jest posortowana malejąco.
Myślałem ,żeby zastosować quicksorta - piwot na środkowy element (założyłem,że powinna to być +/-mediana wszystkich wartości - czyli przypadek optymistyczny dla quicksorta) więc zaimplementowałem sortowanie szybkie i przy okazji postanowiłem sprawdzić czas sortowania dla 20000 elementów uporzadkowanych według przedstawionego wyżej schematu. Wyszło ,że jest to ~0.016sec. .Postanowiłem dla sprawdzenia zaimplementować do tego problemu również mergesort'a ,bo też chodził mi po głowie (w sumie niewiem dlaczego go odrzuciłem) ale co sie okazało - czas sortowania tej samej tablicy przez mergesorta wynosi 0.0sec . Czyli na "logike" lepszy(tzn. bardziej optymalny) do tego przypadku będzie mergesort ?
- Rejestracja:ponad 5 lat
- Ostatnio:3 miesiące
- Postów:17
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
0.016sec
Taką masz pewnie rozdzielczość zegara i albo dostaniesz 0 albo to 0.016. Testujesz ZA MAŁO DANYCH. Weź tego nageneruj kilka GB i dopiero wtedy sortuj. Inaczej to testujesz najwyżej jak działa twoje CPU cache.
Czyli na "logike" lepszy(tzn. bardziej optymalny) do tego przypadku będzie mergesort ?
o_O Ani jeden ani drugi!
pierwsza połowa tablicy jest posortowana rosnąco, natomiast druga połowa tablicy jest posortowana malejąco.
To można wykonać w czasie liniowym przecież! Analogicznie do tego jak działa merge w merge sorcie. Przecież łączysz dwie posortowane tablice (to że jedna malejąco a druga rosnąco, nie ma znaczenia, możesz przeglądać jedną z nich od tyłu)! Algorytm jest trywialny, bo wystarczy że porównujesz ze sobą tylko "pierwszy element" z każdej z tablic i przenosisz ten mniejszy do tablicy wynikowej i powtarzasz to aż nie przeniesiesz wszystkich.
- Rejestracja:około 8 lat
- Ostatnio:minuta
- Postów:4884
Najlepszy wybór to Timsort :
The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently.
Timsort was designed to take advantage of runs of consecutive ordered elements that already exist in most real-world data, natural runs.
In the worst case, Timsort takes
O(n\log n)comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm
Jest w bibliotece w Pythonie, Javie i C++.
- Rejestracja:prawie 20 lat
- Ostatnio:około 13 godzin
Ja jeszcze dodam, że wspomniany Timsort wykrywa zarówno podciągi rosnące jak i malejące: https://en.wikipedia.org/wiki/Timsort#Descending_runs więc powinien bardzo dobrze sprawdzać się w przypadku ciągów bitonicznych, o których mowa w pierwszym poście.
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
Timsort miałby sens jakby w wejściowej tablicy takich podciągów posortowanych było k, na losowych pozycjach, a nie jak są tylko dwa o znanej pozycji i znanej monotoniczności :) Nadal uważam że w tym konkretnym przypadku najlepiej zrobić jedno merge
- Rejestracja:ponad 5 lat
- Ostatnio:3 miesiące
- Postów:17
Właśnie posłuchałem Shaloma i rzeczywiście - na zdrową logikę przeciez po sortować coś co już jest posortowane XD
Więc zastosowałem tylko jedno merge , z tym ,że mam pewien problem. Z jakiś powodów (coś z indeksami w tablicach ? ) pomija mi wartość największą ,a poza tym scala ładnie (Tworze dwie podtablice z już posortowanych elementów - następnie porównuje pierwszy element pierwszej tablicy z ostatnim elementem z drugiej tablicy - mniejszą wartość wprowadzam do tablicy "finalnej" a następnie usuwam już wstawiony element z podtablicy do której ten element należał. ) Czy ktoś widzi, gdzie jest błąd w tym kodzie i mógłby pomóc :D ?
void merge(int *array, int l, int r) {
int m = (l+r)/2;
int i, j, k, nl=0, nr=0;
//rozmiary podtablic - nl lewa podtablica nr - prawa podtablica
nl = m; nr = r-m;
int larr[nl], rarr[nr];
//wypelnianie kazdej z podtablic wartosciami
for(i = 0; i<nl; i++)
{
larr[i] = array[l+i];
}
for(j = 0; j<nr; j++)
{
rarr[j] = array[m+j];
}
i = 0; j = nr; k = 0;
//Zlaczanie tymczasowych tablic w jedna
while(i <= nl && j>=0) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
}else{
array[k] = rarr[j];
j--;
}
k++;
}
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
Pierwsza rzecz do sprawdzenia -> int m = (l+r)/2; zastanów się nad przypadkiem kiedy w tablicy jest parzysta a kiedy nieparzysta liczb elementów!
- Rejestracja:ponad 5 lat
- Ostatnio:3 miesiące
- Postów:17
Pominalem ta informacje , przepraszam , moj blad. W poleceniu jest zalozenie ze ilosc elementow w twblicy wejsciowej jest zawsze parzysta . Z tego wynika ze ten zapis jest poprawny , wiec tutaj bledu nie ma , sprawdzalwm tez Od razu jak utworzyly sie lewe i prawe tablice dla malego zestawu danych wejsciowych i wszystko bylo ok , problem jest z tablica wynikowa :/
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
while(i <= nl && j>=0) { ten warunek jest zły. Co jak ci się jedna tablica skończy szybciej niż druga? Nie przepiszesz brakującego elementu, konkretnie ostatniego. Już bym prędzej zrobił warunek że k<dlugosc_calej
- Rejestracja:ponad 8 lat
- Ostatnio:około 2 godziny
- Lokalizacja:U krasnoludów - pod górą
- Postów:4706
Po co sortować? - wystarczy napisać iterator, który najpierw leci od dołu, potem od góry do połowy i mamy zrobione zadanie w czasie 0 :-)
EDIT: bzdura - nie przeczytałem dokładnie o co chodzi
nie mówiąc o tym, że to tablica ludzie oczekują dostępu swobodnego
coś ostatnio za dużo chyba haskellowałem
- Rejestracja:ponad 5 lat
- Ostatnio:3 miesiące
- Postów:17
Udało się !
Bardzo dziękuje Shalom - zrobiłem to według Twoich rad - działa bardzo dobrze, wystarczyło przyjrzeć się rozmiarą każdej z podtablic i sposobowi wstawiania do nich elementow (wyznaczanie środka ,rzeczywiście powodowało kłopoty ) no i też długość tablicy , po zmianie na rzeczywistą pomogła i pokazała inne błedy.
Także bardzo dziękuje jeszcze raz wszystkim za pomoc ! :)
przyjrzeć się rozmiarą - rozmiarOM
Shalom1,3,5,7,6,4,2,0