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".


>> Jeśli sortowalibyśmy listę, problem w ogóle znika.
> Lista musi być na tyle duża, że nie możemy jej skopiować do struktury o
> dostępie swobodnym, ale jest to naciągane, bo przy złożoności n^2
> prawdopodobnie taniej będzie przenieść listę na pamięć zewnętrzną,
> zwolnić, wczytać do tablicy, posortować jakimś q/heap sortem, zapisać na
> pamięć zewnętrzną, zwolnić, wczytać do listy ;)

Zaalokować pamięć, i to wszytko dla 50 intów:)


>> A czasem o wyborze może zadecydować stabilność sortowania.
>
> Jeżeli dobrze widzę to i insertion i selection może być stabilny.

Insertion jest od razu. Jak prosto poprawić selection, nie wiem.
Już w pierwszym ruchu zamieniami maksymalny element (możemy
go wybrać tak, aby wśród kilku równych był to ten właściwy),
ale element pierwszy ląduje w losowym miejscy, zupełnie
zaburzając porządek względem innych elementów o tej samej wartości.

Ok, wiem jak prosto poprawić... ale to wymaga dodatkowej
tablicy długości n:(

>>
>> Tak więc ja bym nie był tak pewny odpowiedzi:)
>>
>> A poważnie, z tą pamięcią to ciekawy problem.
>> Jeśli już mamy całość w cache (nie rozważamy
>> przecież na serio sortowania dużych tablic)
>> ale jednocześnie porównanie jest tanie (inty).
>
>> Ż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.
Daje to kilka, w optymistycznym przypadku (gdy porównania są
tanie) kilkanaście procent przyspieszenia.


>>
>> 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?


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.

W kolejności,
n-dlugość tablicy, liczba powtórzeń, wynik dla insert, wynik dla select
Wyniki w ms. Tabelka na końcu.

Wychodzi, że insert jest jednak szybszy. I jego przewaga rośnie

Wykres czasu pojedynczego powtórzenia (nasz wynik/liczba powtórzeń)
na log log
http://w303.wrzuta.pl/obraz/8asI9fMQioF/loglog_czas

Proporcja czasu selectsorca do insertsorta dla rożnych n.
http://w303.wrzuta.pl/obraz/apPnxl5jsfn/zysk
Proporcja liniiowo, n logarytmicznie.

Tabelka na końcu.

Trochę mnie to dziwi. Błędu w implementacji nie widzę.
czyżby znów cache i liniowy spacer po pamięci?

Korzyść jest większa niż *2 wynikające z samej
ilości porównań. Posortowałem też ciag posortowany
odwrotnie. Insert zwalnia, bo wykorzystuje pesymistyczną
liczbę porównań, select nieco przyszpiesza
(if (tabl[i]<tabl[min]) min=i; się nie wykonuje)
ale nadal insert jest ciut szybsze.


pzdr
bartekltg


Tabelka wyników dla tablicy losowej.
n, liczba powtórzeń, wynik dla insert, wynik dla select

2 24999999 185 289
3 11111110 176 226
4 6249999 157 193
5 3999999 142 181
6 2777777 138 185
7 2040816 130 192
8 1562499 119 198
9 1234567 110 198
10 999999 102 195
11 826446 95 190
12 694444 90 184
13 591715 84 179
14 510204 80 174
15 444444 77 170
16 390624 75 166
17 346020 71 162
18 308641 68 158
19 277008 66 154
20 249999 64 152
22 206611 61 146
24 173611 58 140
26 147928 55 137
28 127550 53 132
30 111111 51 129
32 97656 49 126
34 86505 47 123
36 77160 46 121
38 69252 45 118
40 62499 44 116
43 54083 42 114
46 47258 41 111
49 41649 40 109
52 36982 39 107
55 33057 39 104
58 29726 38 104
61 26874 37 101
65 23668 36 99
69 21003 35 98
73 18765 34 97
77 16866 34 95
81 15241 34 94
86 13520 33 92
91 12075 33 91
96 10850 32 90
101 9802 31 89
107 8734 31 88
113 7831 31 88
119 7061 30 85
125 6399 30 85
132 5739 30 84
139 5175 30 83
146 4691 29 83
154 4216 29 81
162 3810 29 81
171 3419 28 79
180 3086 27 79
190 2770 28 78
200 2499 28 77
211 2246 27 77
222 2029 27 76
234 1826 27 76
246 1652 27 75
259 1490 26 75
272 1351 26 75
286 1222 26 74