On 13.10.2012 14:14, bartekltg wrote:
> W dniu 2012-10-13 11:39, Michoo pisze:
>
>>> Insertionsort jest w oczywisty sposób szybszy w sensie
>>> oczekiwanej liczby porównań (w select wyszukujemy maks
>>> wśród tablic długości n, n-1, n-2...4,3,2, w insert
>>> wkładamy zadany element w tablice długości 1,2..n-1,
>>> a średnio włożymy w połowę długości.
>>
>> Zgadza się.
>>
>>>
>>> Jeśli więc porównanie jest znacznie kosztowniejsze od
>>> przesunięcia, wolimy mieć dwa razy mniej porównań,
>>> nawet kosztem dodatkowych ~n^2 przesunięć.
>>
>> Widziałem nawet takie rozważanie gdzie wyszukiwanie w części
>> posortowanej było robione przeszukiwaniem binarnym, a wstawianie było w
>> czasie stałym - dostajemy złożoność insertion sort n*log(n) ;)
>
> Hehe.
> Złożoność oczywiście pozostaje, ale jakieś tam korzyści
> w działaniu mogą się pojawić.
> Ale mam coś lepszego. Autor pewnej bardzo popularnej książki
> do "c++ i szablonów" buduje wyszukiwanie binarne latając
> po kontenerze ++owaniem iteratora. Komentuje to "++ jest szybkie".
Nie trafiłem - można prosić o tytuł? (Ja za to spotkałem profesora z
ciekawą definicją "native code". ;) )

>>> Żeby nie był to problem czysto akademicki,
>>> niech to będzie 'końcówka qsorta'. Wtedy wywoływany
>>> obszar i tak już najpewniej jest pod ręką.
>>
>> Ale w takiej sytuacji jest heapsort działający zawsze w n*log(n) ;)
>
> Mylisz sytuację.
> Nie chodzi o problem qsorta z niektórymi danymi,
> tylko o to, że gdy, w czasie zrównoważonego działania,
> dochodzimy do rekursywnego wywołania qsorta dla odpowiednio
> małych obszarów, odpala się jakiś mały zwarty n^2.
Z tego co kojarzę standardowym jest użycie heapsorta albo mergesorta
zależnie, czy zależy nam na stabilności. Po co używać coś o złożoności
n^2 skoro ma się rozwiązania n*log(n)?


>>>
>>> Heh, możnaby jakimś studentom zadać;)
>>
>> Wygrzebałem stare sprawozdanie na "algorytmy i struktury danych".
>> Najszybszym algorytmem dla losowych danych był wtedy heapsort napisany w
>> assemblerze (ale miałem na jego optymalizację dobre 3 godziny podczas
>> jazdy pociągiem). Największym zaskoczeniem był Shell:
>> http://grota.be/~michoo/smieci/algo_sort.png
>
> Ładnie.
>
> A co do shella. Już ciąg Pratta miał O(N log^2N)
> To asymptotycznie niedużo więcej niż 'normalne'
> algorytmy. A są lepsze ciągi:
> http://en.wikipedia.org/wiki/Shellsort#Computational
_complexity
>
> Hmm. Piszą, że się nawet w specjalnych zastosowaniach tego używa.
>
> q_med to qsort z medianą z ilu wartości? Wszystkich z przedziału?
z 3 losowych
>
>
> Ale wróćmy do selectsort i insertsort.
>
> Napisałem palce obie wersje(specjalnie dla fira, prawie c):
>
> void insertsort(int * tabl,int first, int last)
> {
> for (int j = first+1;j<=last;j++) //pierwszy nieposortowany
> {
> int i=j;
> int temp = tabl[j];
> while ((i>first) && temp<tabl[i-1])
> {
> tabl[i]=tabl[i-1];
> i--;
> }
> tabl[i]=temp;
> }//for
> }
>
>
>
> void selectsort(int * tabl,int first, int last)
> {
> for (int j=first; j<last; j++)
> {
> int min = j;
> for (int i=j+1;i<=last;i++)
> {
> if (tabl[i]<tabl[min]) min=i;
> }
> int temp = tabl[min];
> tabl[min]=tabl[j];
> tabl[j]=temp;
> }//for
> }
>
>
> I dość brutalną metodę testowania. Długi, losowe identyczne tablice,
> wkładane po kawałkach w obie procedury.
> Robimy ileś powtórzeń dla tablic długości n.
> Za każdym raazem tablica całkowicie losowa.
>
>
> Wyniki.. cóż, mnie zaskoczyły. Sprawdziłem nawet zamieniajac
> w procedurze testowej funkcje miejscami.
A ja jak źle spojrzałem na wykres - insertion u nie też był odrobinę
szybszy.
http://grota.be/~michoo/smieci/sort2.png

>
> Trochę mnie to dziwi. Błędu w implementacji nie widzę.
> czyżby znów cache i liniowy spacer po pamięci?
Średnio wychodzi trochę mniej operacji. Selection ma zawsze 1/2n^2 a
insertion tyle pesymistycznie a średnio połowę. Btw właśnie tak mi
wyszło, że insertion można przedstawić jako "bąbelki od drugiej strony".


Co ciekawe mój selection był minimalnie szybszy od Twojego, mimo dużego
podobieństwa:
void selection(int n,T* data)
{
for(int i=0,p=0;i<n;++i,p=i){
for(int j=i+1;j<n;++j)
if(data[j]<data[p])
p=j;
std::swap(data[i],data[p]);
}
}



--
Pozdrawiam
Michoo