-
Notifications
You must be signed in to change notification settings - Fork 7
/
quick_sort.cpp
126 lines (113 loc) · 2.94 KB
/
quick_sort.cpp
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*
author: @vikasc
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <fstream>
using namespace std;
const int MAX = 10e5;
typedef long long int lint;
lint first_comparison = 0;
lint last_comparison = 0;
lint mid_comparison = 0;
int partition_first(int *A, int start, int end) {
int i = start + 1;
int piv = A[start]; // taking 1st element as pivot
for (int j = start + 1; j <= end; ++j) {
if (A[j] < piv) {
first_comparison += 1;
swap(A[i], A[j]);
++i;
}
}
swap(A[start], A[i - 1]);
return i - 1; // return pivot_position
}
void quick_sort_first(int *A, int start, int end) {
if (start < end) {
int piv = partition_first(A, start, end);
quick_sort_first(A, start, piv - 1);
quick_sort_first(A, piv + 1, end);
}
}
int partition_last(int *A, int start, int end) {
int i = start;
int piv = A[end]; // taking last element as pivot
for (int j = start; j < end; ++j) {
if (A[j] <= piv) {
last_comparison += 1;
swap(A[j], A[i]);
++i;
}
}
swap(A[i], piv);
return i;
}
void quick_sort_last(int *A, int start, int end) {
if (start < end) {
int piv = partition_last(A, start, end);
quick_sort_last(A, start, piv - 1);
quick_sort_last(A, piv + 1, end);
}
}
void quick_sort_mid(int *A, int start, int end) {
if (start < end) {
int pivot = A[(start + end) / 2];
int i = start, j = end;
while (i <= j) {
while (A[i] < pivot) {
mid_comparison += 1;
i += 1;
}
while (A[j] > pivot) {
mid_comparison += 1;
j -= 1;
}
if (i <= j) {
swap(A[i], A[j]);
i += 1;
j -= 1;
}
}
quick_sort_mid(A, start, j);
quick_sort_mid(A, i, end);
}
}
int main() {
int size = 0, N, A[MAX];
fstream myfile("IntegerArray.txt"); // read integer text file.
while (myfile >> N) {
A[size] = N;
size += 1;
}
quick_sort_first(A, 0, N - 1);
// for (int i = 0; i < N; ++i) {
// cout << A[i] << " ";
// }
// cout << endl;
cout << "first_comparison : " << first_comparison << endl;
quick_sort_last(A, 0, N - 1);
// for (int i = 0; i < N; ++i) {
// cout << A[i] << " ";
// }
// cout << endl;
cout << "last_comparison : " << last_comparison << endl;
quick_sort_mid(A, 0, N - 1);
// for (int i = 0; i < N; ++i) {
// cout << A[i] << " ";
// }
// cout << endl;
cout << "mid_comparison : " << mid_comparison << endl;
// for (int i = 0; i < N; ++i) {
// cout << A[i] << " ";
// }
// cout << endl;
return 0;
}