ZłoŜ ono ci obliczeniowe algorytmów sortowania ś
Algorytm
l. porówna l. przestawie ń
ń
2
n − n
2
n
prosty wybór
+ (
3 n − ) 1
2
4
2
n − n
2
n + 3 n − 4
proste wstawianie
−1
2
2
2
n − n
prosta zamiana (b belkowe)
(
5
,
1
2
n − n) ą
2
stogowe
≈ c ⋅ nlog n
2
szybkie
≈ c ⋅ nlog n
2
Czasy wykonania algorytmów sortowania odwrotnie
uporz dkowane
losowe
ą
uporz dkowane
ą
algorytm
klucze
klucze
klucze
klucze
klucze
klucze
+dane
+dane
+dane
prosty wybór
489
547
509
607
695
1430
proste wstawianie
12
46
366
1129
704
2150
b belkowe
540
610
1026
3212
1492
5599
ą
mieszane
5
5
961
3071
1619
5757
stogowe
116
264
110
246
104
227
szybkie
31
55
60
137
37
75
Sortowanie przez wybór z zamian ą
44 55 12 42 94 18 06 67
06
06 55 12 42 94 18 44 67
12
06 12 55 42 94 18 44 67
18
06 12 18 42 94 55 44 67
42
06 12 18 42 94 55 44 67
44
06 12 18 42 94 55 94 67
55
06 12 18 42 94 55 94 67
67
06 12 18 42 94 55 67 94
Sortowanie przez wstawianie z zamian ą
…………………...
12
44 55 12 42 94 18 06 67
42
12 44 55 42 94 18 06 67
94
12 42 44 55 94 18 06 67
18
12 42 44 55 94 18 06 67
06
12 18 42 44 55 94 06 67
67
06 12 18 42 44 55 94 67
06 12 18 42 4 44 55 67 94
Sortowanie b belkowe (D-G) ą
Sortowanie b belkowe (G-D) ą
Sortowanie drzewiaste
Sortowanie stogowe
44
55
12
42
94
18
06
67
06
18
12
42
94
55
44
67
06
12
18
42
94
55
44
67
06
12
18
42
44
55
94
67
06
12
18
42
44
55
67
94
06
12
18
42
44
55
67
94