-
Notifications
You must be signed in to change notification settings - Fork 0
/
QuickSort.ts
36 lines (29 loc) · 906 Bytes
/
QuickSort.ts
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
import { SortingInterface } from "../SortingInterface.js";
export class QuickSort implements SortingInterface {
static swap (x: number, y: number): Array<number> {
return [y, x];
}
Partition (A: Array<number>, p: number, r: number): number {
const x = A[r];
let i = p - 1;
for (let j = p; j <= r-1 ; j++) {
if (A[j] <= x) {
i++;
[A[i], A[j]] = QuickSort.swap(A[i], A[j]);
}
}
[A[i+1], A[r]] = QuickSort.swap(A[i+1], A[r]);
return i+1;
}
QuickSort (A: Array<number>, p: number, r: number) {
if (p < r) {
const q = this.Partition(A, p, r);
this.QuickSort(A, p, q-1);
this.QuickSort(A, q+1, r);
}
}
Sort (A: Array<number>): Array<number> {
this.QuickSort(A, 0, A.length - 1);
return A;
}
}