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
|
#include "QuickSorter.h"
/* Python
def swap(l, i, k):
v = l[i]
l[i] = l[k]
l[k] = v
print(str(l))
def partition(l, start, end):
print("PARTITION {} [{}:{}]".format(l, start, end))
p_value = l[end]
p_index = end-1
for i in range(start, end):
while(i < p_index and l[i] >= p_value):
swap(l, i, p_index)
p_index -= 1
while(i >= p_index and l[i] < p_value):
swap(l, i, p_index)
p_index += 1
swap(l, p_index, end)
print("DONE {}|[{}]|{}:{}".format(l[start:p_index], l[p_index], l[p_index+1:end+1], p_value))
return p_index
def qsort(l, i, k):
if i < k:
p = partition(l, i, k)
qsort(l,i,p-1)
qsort(l,p+1,k)
if __name__ == "__main__":
import random as r
x = [int(r.random()*12) for i in range(12)]
print(x)
qsort(x, 0, len(x)-1)
print(x)
*/
static void swap(std::vector<int>& list, int i, int k) {
int v = list[i];
list[i] = list[k];
list[k] = v;
}
static int partition(std::vector<int>& list, int i, int k) {
int pivot_value = list[k];
int pivot_index = k - 1;
for(int index = i; index < k; index++) {
while((index < pivot_index) && (list[index] >= pivot_value)) {
swap(list, index, pivot_index);
pivot_index--;
}
while((index >= pivot_index) && (list[index] < pivot_value)) {
swap(list, index, pivot_index);
pivot_index++;
}
}
swap(list, pivot_index, k);
return pivot_index;
}
static void quicksort(std::vector<int>& list, int i, int k) {
if(i < k) {
int p = partition(list, i, k);
quicksort(list, i, p-1);
quicksort(list, p+1, k);
}
}
QuickSorter::QuickSorter() {
this->name = std::string("quicksort");
}
QuickSorter::~QuickSorter() {
}
void QuickSorter::sort(std::vector<int>& list) const {
quicksort(list, 0, list.size()-1);
}
|
