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
|
using System;
using System.Collections.Generic;
using System.Linq;
namespace ALGA {
public class Quicksort {
public static void quicksort(ISortList list) {
quicksort(list, 0, list.Count - 1);
}
private static void quicksort(ISortList list, int leftIndex, int rightIndex) {
if (leftIndex >= rightIndex || leftIndex < 0) return;
int pivotIndex;
int middle = leftIndex + ((rightIndex - leftIndex) / 2);
// // Quicksort
// pivotIndex = leftIndex;
// pass unit tests
pivotIndex = middle;
// // Quicksort3
// List<Tuple<int, int>> picks = new List<Tuple<int, int>> {
// new Tuple<int, int>(leftIndex, list[leftIndex]),
// new Tuple<int, int>(middle, list[middle]),
// new Tuple<int, int>(rightIndex, list[rightIndex]),
// };
// picks.Sort((a, b) => a.Item2.CompareTo(b.Item2));
// pivotIndex = picks[1].Item1;
pivotIndex = partition(list, pivotIndex, leftIndex, rightIndex);
quicksort(list, leftIndex, pivotIndex - 1);
quicksort(list, pivotIndex + 1, rightIndex);
}
public static int partition(ISortList list, int pivotIndex, int leftIndex, int rightIndex) {
while (true) {
while (list.compare(leftIndex, pivotIndex) < 0) leftIndex++;
while (list.compare(pivotIndex, rightIndex) < 0) rightIndex--;
if (leftIndex >= rightIndex) break;
list.swap(leftIndex, rightIndex);
if (leftIndex == pivotIndex)
pivotIndex = rightIndex;
else if (rightIndex == pivotIndex)
pivotIndex = leftIndex;
}
return pivotIndex;
}
}
}
|