1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
-----------------
Sorting Tests
-----------------
Vectors of length 15, using uniform random doubles (0,1):
Introsort:
A (before sort): [1.000 0.163 0.283 0.947 0.232 0.485 0.957 0.744 0.540 0.740 0.760 0.659 0.316 0.804 0.520]
A (after sort): [0.163 0.232 0.283 0.316 0.485 0.520 0.540 0.659 0.740 0.744 0.760 0.804 0.947 0.957 1.000]
Quicksort:
A (before sort): [0.169 0.476 0.392 0.222 0.213 0.030 0.334 0.194 0.944 0.580 0.898 0.666 0.499 0.561 0.182]
A (after sort): [0.030 0.169 0.182 0.194 0.213 0.222 0.334 0.392 0.476 0.499 0.561 0.580 0.666 0.898 0.944]
Heapsort:
A (before sort): [0.297 0.117 0.063 0.648 0.725 0.637 0.714 0.100 0.699 0.108 0.129 0.502 0.208 0.289 0.083]
A (after sort): [0.063 0.083 0.100 0.108 0.117 0.129 0.208 0.289 0.297 0.502 0.637 0.648 0.699 0.714 0.725]
Insertion Sort:
A (before sort): [0.128 0.547 0.082 0.292 0.892 0.227 0.432 0.141 0.400 0.687 0.171 0.441 0.045 0.311 0.506]
A (after sort): [0.045 0.082 0.128 0.141 0.171 0.227 0.292 0.311 0.400 0.432 0.441 0.506 0.547 0.687 0.892]
Introsort (index):
A: [0.182 0.511 0.741 0.366 0.161 0.460 0.628 0.678 0.698 0.479 0.090 0.339 0.095 0.437 0.475]
I: [10 12 4 0 11 3 13 5 14 9 1 6 7 8 2]
A(I): [0.090 0.095 0.161 0.182 0.339 0.366 0.437 0.460 0.475 0.479 0.511 0.628 0.678 0.698 0.741]
Quicksort (index):
A: [0.419 0.778 0.625 0.980 0.370 0.831 0.141 0.744 0.830 0.391 0.622 0.347 0.046 0.613 0.567]
I: [12 6 11 4 9 0 14 13 10 2 7 1 8 5 3]
A(I): [0.046 0.141 0.347 0.370 0.391 0.419 0.567 0.613 0.622 0.625 0.744 0.778 0.830 0.831 0.980]
Heapsort (index):
A: [0.499 0.724 0.145 0.042 0.311 0.122 0.242 0.381 0.440 0.600 0.645 0.433 0.556 0.717 0.642]
I: [3 5 2 6 4 7 11 8 0 12 9 14 10 13 1]
A(I): [0.042 0.122 0.145 0.242 0.311 0.381 0.433 0.440 0.499 0.556 0.600 0.642 0.645 0.717 0.724]
Insertion sort (index):
A: [0.686 0.096 0.123 0.057 0.820 0.126 0.316 0.181 0.142 0.664 0.685 0.191 0.436 0.964 0.868]
I: [3 1 2 5 8 7 11 6 12 9 10 0 4 14 13]
A(I): [0.057 0.096 0.123 0.126 0.142 0.181 0.191 0.316 0.436 0.664 0.685 0.686 0.820 0.868 0.964]
Vectors of length 20000, using uniform random doubles (0,1):
Introsort: Successful!
Quicksort: Successful!
Heapsort: Successful!
Introsort (index): Successful!
Quicksort (index): Successful!
Heapsort (index): Successful!
Vectors of length 15, using uniform random integers (0,10):
Introsort:
B (before sort): [4 8 6 7 4 8 3 1 1 4 4 6 1 3 2]
B (after sort): [1 1 1 2 3 3 4 4 4 4 6 6 7 8 8]
Quicksort:
B (before sort): [2 7 2 8 2 1 0 10 7 6 3 9 7 7 3]
B (after sort): [0 1 2 2 2 3 3 6 7 7 7 7 8 9 10]
Heapsort:
B (before sort): [6 4 4 6 10 10 2 6 3 8 2 3 6 4 7]
B (after sort): [2 2 3 3 4 4 4 6 6 6 6 7 8 10 10]
Insertion sort:
B (before sort): [2 5 10 7 1 6 6 0 9 5 5 7 1 2 1]
B (after sort): [0 1 1 1 2 2 5 5 5 6 6 7 7 9 10]
Introsort (index):
B: [0 3 0 3 8 8 8 3 9 3 2 8 4 8 7]
I: [0 2 10 1 3 7 9 12 14 4 5 6 11 13 8]
B(I): [0 0 2 3 3 3 3 4 7 8 8 8 8 8 9]
Quicksort (index):
B: [1 3 4 4 9 5 10 9 6 8 4 6 3 3 2]
I: [0 14 1 13 12 3 2 10 5 11 8 9 7 4 6]
B(I): [1 2 3 3 3 4 4 4 5 6 6 8 9 9 10]
Heapsort (index):
B: [8 6 9 1 4 0 6 6 3 6 6 6 0 5 1]
I: [12 5 14 3 8 4 13 6 11 10 9 7 1 0 2]
B(I): [0 0 1 1 3 4 5 6 6 6 6 6 6 8 9]
Insertion sort (index):
B: [6 8 1 9 3 1 4 9 10 0 4 0 4 10 8]
I: [9 11 2 5 4 6 10 12 0 1 14 3 7 8 13]
B(I): [0 0 1 1 3 4 4 4 6 8 8 9 9 10 10]
Vectors of length 20000, using uniform random integers (0,10):
Introsort: Successful!
Quicksort: Successful!
Heapsort: Successful!
Introsort (index): Successful!
Quicksort (index): Successful!
Heapsort (index): Successful!
|
