/usr/share/nickle/sort.5c is in nickle 2.79-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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) };
}
|