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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
/* $Header$
*
* Copyright © 2002 Keith Packard and Bart Massey.
* All Rights Reserved. See the file COPYING in this directory
* for licensing information.
*/
autoload PRNG;
namespace Sort {
/*
* Quicksort with random pivot
*/
public void qsort (&poly[*] a, bool(poly, poly) gt)
{
void quicksort (int p, int r) {
if (p < r) {
/* swap two array elements */
void exchange (int i, int j) {
poly t = a[i]; a[i] = a[j]; a[j] = t;
}
/* partition the array into two pieces and return the pivot */
int partition (int p, int r) {
/* select a random element to pivot */
int pivot = p + PRNG::randint(p-r);
exchange (pivot, r);
poly x = a[r];
int i = p;
for (int j = p; j < r; j++)
{
if (gt (x, a[j]))
{
exchange (i, j);
i++;
}
}
exchange (i, r);
return i;
}
int q = partition (p, r);
quicksort (p, q-1);
quicksort (q+1, r);
}
}
quicksort (0, dim(a)-1);
}
/*
* Mergesort
*/
public void mergesort (&poly[*] a, bool(poly, poly) gt)
{
void msort (int p, int r) {
if (p < r)
{
/* merge two sorted lists together */
void merge (int p, int q, int r)
{
/* temporary storage for left half of array */
int n1 = q - p + 1;
poly[n1] L;
for (int i = 0; i < n1; i++)
L[i] = a[p+i];
/* temporary storage for right half of array */
int n2 = r - q;
poly[n2] R;
for (int i = 0; i < n2; i++)
R[i] = a[q+i+1];
/* merge two halves back into main array */
int i = 0, j = 0, k = p;
while (i < n1 && j < n2)
a[k++] = gt (L[i], R[j]) ? R[j++] : L[i++];
while (i < n1)
a[k++] = L[i++];
while (j < n2)
a[k++] = R[j++];
}
int q = (p + r) // 2;
msort (p, q);
msort (q+1, r);
merge (p, q, r);
}
}
msort (0, dim(a)-1);
}
protected int[*] randomints (int n, int max) =
(int[n]) { [i] = PRNG::randint(max) };
}
|
