121
*/
122
export function quickSelect<T>(nth: number, data: T[], compare: Compare<T>): T {
124
>
nth = nth | 0;
125
>
126
>
if (nth >= data.length) {
127
throw new TypeError('invalid index');
128
}
130
>
const pivotValue = data[Math.floor(data.length * Math.random())];
131
>
const lower: T[] = [];
132
>
const higher: T[] = [];
133
>
const pivots: T[] = [];
134
>
135
>
for (const value of data) {
136
>
const val = compare(value, pivotValue);
137
>
if (val < 0) {
138
>
lower.push(value);
139
>
} else if (val > 0) {
140
>
higher.push(value);
141
>
} else {
142
>
pivots.push(value);
143
>
}
144
>
}
145
>
146
>
if (nth < lower.length) {
147
>
return quickSelect(nth, lower, compare);
148
>
} else if (nth < lower.length + pivots.length) {
149
>
return pivots[0];
150
>
} else {
151
>
return quickSelect(nth - (lower.length + pivots.length), higher, compare);
152
>
}
153
>
}
154
155
export function groupBy<T>(data: ReadonlyArray<T>, compare: (a: T, b: T) => number): T[][] {