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 ?
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.
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++.
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.
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
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++;
}
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!
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 :/
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
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
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 ! :)