2DW2gWYPnoaQ9P5XGtmCng changeset

Changeset323261616138 (b)
ParentNone (a)
ab
0+#include <iostream>
0+#include <vector>
0+
0+using namespace std;
0+
0+void swap(int &a, int &b)
0+{
0+     int temp;
0+     a = b;
0+     b = temp;
0+}
0+
0+int split_array(vector<int>& array, int pivot, int start_index, int end_index)
0+{
0+     int left_boundary = start_index;
0+     int right_boundary = end_index;
0+
0+     while (left_boundary < right_boundary) {
0+          while (pivot < array[right_boundary] && right_boundary > left_boundary) {
0+               right_boundary--;
0+          }
0+
0+          swap(array[left_boundary], array[right_boundary]);
0+
0+          while (pivot >= array[left_boundary] && left_boundary < right_boundary) {
0+               left_boundary++;
0+          }
0+
0+          swap(array[right_boundary], array[left_boundary]);
0+     }
0+
0+     return left_boundary;
0+}
0+
0+void quicksort(vector<int>& array, int start_index, int end_index)
0+{
0+     int pivot = array[start_index];
0+     int split_point;
0+     
0+     if (end_index > start_index) {
0+          split_point = split_array(array, pivot, start_index, end_index);
0+          array[split_point] = pivot;
0+          quicksort(array, start_index, split_point-1);
0+          quicksort(array, split_point+1, end_index);
0+     }
0+}
...
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
--- Revision None
+++ Revision 323261616138
@@ -0,0 +1,46 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+void swap(int &a, int &b)
+{
+     int temp;
+     a = b;
+     b = temp;
+}
+
+int split_array(vector<int>& array, int pivot, int start_index, int end_index)
+{
+     int left_boundary = start_index;
+     int right_boundary = end_index;
+
+     while (left_boundary < right_boundary) {
+	  while (pivot < array[right_boundary] && right_boundary > left_boundary) {
+	       right_boundary--;
+	  }
+
+	  swap(array[left_boundary], array[right_boundary]);
+
+	  while (pivot >= array[left_boundary] && left_boundary < right_boundary) {
+	       left_boundary++;
+	  }
+
+	  swap(array[right_boundary], array[left_boundary]);
+     }
+
+     return left_boundary;
+}
+
+void quicksort(vector<int>& array, int start_index, int end_index)
+{
+     int pivot = array[start_index];
+     int split_point;
+     
+     if (end_index > start_index) {
+	  split_point = split_array(array, pivot, start_index, end_index);
+	  array[split_point] = pivot;
+	  quicksort(array, start_index, split_point-1);
+	  quicksort(array, split_point+1, end_index);
+     }
+}