This repository has been archived by the owner on Nov 21, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 2
/
index.js
125 lines (113 loc) · 2.59 KB
/
index.js
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/*
* Intro sort ported from Java to Javascript
*
* original Copyright Ralph Unden,
* http://ralphunden.net/content/tutorials/a-guide-to-introsort/?q=a-guide-to-introsort
* Modifications: Bernhard Pfahringer
* changes include: local insertion sort, no global array
*
* Javascript port: Arnor Heidar Sigurdsson <[email protected]>
*/
module.exports = sort;
var size_threshold = 16;
function sort(a) {
// you could modify it to accept a range if you want to split it up into
// multiple parts
introsort_loop(a, 0, a.length, 2 * floor_lg(a.length));
}
/*
* Quicksort algorithm modified for Introsort
*/
function introsort_loop (a, lo, hi, depth_limit) {
while (hi-lo > size_threshold) {
if (depth_limit === 0) {
heapsort(a, lo, hi);
return;
}
depth_limit=depth_limit-1;
var p = partition(a, lo, hi, medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1));
introsort_loop(a, p, hi, depth_limit);
hi = p;
}
insertionsort(a, lo, hi);
}
function partition(a, lo, hi, x) {
var i=lo, j=hi;
while (true) {
while (a[i] < x) i++;
j=j-1;
while (x < a[j]) j=j-1;
if (i >= j) return i;
exchange(a,i,j);
i++;
}
}
function medianof3(a, lo, mid, hi) {
if (a[mid] < a[lo]) {
if (a[hi] < a[mid]) {
return a[mid];
} else {
return (a[hi] < a[lo]) ? a[hi] : a[lo];
}
} else {
if (a[hi] < a[mid]) {
return (a[hi] < a[lo]) ? a[lo] : a[hi];
} else {
return a[mid];
}
}
}
/*
* Heapsort algorithm
*/
function heapsort(a, lo, hi) {
var n = hi-lo, i;
for (i= n / 2; i >= 1; i--) {
downheap(a,i,n,lo);
}
for (i = n; i > 1; i--) {
exchange(a,lo,lo+i-1);
downheap(a,1,i-1,lo);
}
}
function downheap(a, i, n, lo) {
var d = a[lo+i-1];
var child;
while (i<=n/2) {
child = 2*i;
if (child < n && a[lo+child-1] < a[lo+child]) {
child++;
}
if (d >= a[lo+child-1]) break;
a[lo+i-1] = a[lo+child-1];
i = child;
}
a[lo+i-1] = d;
}
/*
* Insertion sort algorithm
*/
function insertionsort(a, lo, hi) {
var i,j;
var t;
for (i=lo; i < hi; i++) {
j=i;
t = a[i];
while(j!=lo && t < a[j-1]) {
a[j] = a[j-1];
j--;
}
a[j] = t;
}
}
/*
* Common methods for all algorithms
*/
function exchange(a, i, j) {
var t=a[i];
a[i]=a[j];
a[j]=t;
}
function floor_lg(a) {
return (Math.floor(Math.log(a)/Math.log(2))) << 0;
}