-
Notifications
You must be signed in to change notification settings - Fork 10
/
03_quick_sort.cpp
133 lines (103 loc) · 3.13 KB
/
03_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
127
128
129
130
131
132
133
/*
Topic - Quick Sort
- It is a inplace algorithm
- Divide & Conquer
- NlogN on avg case
- N^2 on worst case (can be fixed using randomised quick sort )
*/
#include <iostream>
using namespace std;
// Partition function: Divide the array in 2 parts using pivot element i.e elements<=pivot & elements >pivot
int partition(int *arr, int start, int end)
{
// Inplace (can't take extra array)
int i = start-1; // pointer for maintaning region smaller than pivot
int j = start; // pointer for maintaning region larger than pivot
int pivot = end; // pivot is the last array element
// divide the array in smaller & larger region on the bases of pivot element
while(j<end)
{
if(arr[j] <= arr[pivot])
{
i++;
swap(arr[j], arr[i]);
}
j++;
}
// place the pivot element at its correct position
swap(arr[i+1], arr[pivot]);
// return the pivot index
return i+1;
}
// quick Sort
void quick_sort(int *arr, int start, int end)
{
// base case: for 0 & 1 element
if (start >= end)
{
return;
}
// rec case
int p_idx = partition(arr, start, end);
// left subarray
quick_sort(arr, start, p_idx-1);
// right subarray
quick_sort(arr, p_idx+1, end);
return;
}
// function to drive code
int main()
{
int size;
cout << "Enter array size: ";
cin >> size;
int arr[size];
cout << "Enter Elements: ";
for (int i = 0; i < size; i++)
{
cin >> arr[i];
}
// sort array
quick_sort(arr, 0, size - 1);
cout << "After Quick Sort: ";
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
/*
OUTPUT:
Enter array size: 7
Enter Elements: 2 7 8 6 1 5 4
After Quick Sort: 1 2 4 5 6 7 8
Steps:
1. Choose pivot. (it can be the first element or the last element)
2. Partation Step: Place the pivot element at its correct position.
i.e divide the array element on the bases of elements <=pivot & >pivot
Divide ---|-----> <=Pivot
|-----> >Pivot
3. Recursively sort the divided smaller parts
quickSort(arr, start, pivot-1)
quickSort(arr, pivot+1, end)
Explaination:
when, n=7, arr[] = {2,7,8,6,1,5,4}
Now, partition(arr, 0, 6)
when i=-1, j=0 |2|7|8|6|1|5|4|
pivot = 6 i j pivot
i=0, j=1 |2|7|8|6|1|5|4| as a[j]<a[pivot], swap(arr[j], arr[i])
i j pivot
i=0, j=2 |2|7|8|6|1|5|4|
i j pivot
i=0, j=3 |2|7|8|6|1|5|4|
i j pivot
i=0, j=4 |2|7|8|6|1|5|4| as a[j]<a[pivot], swap(arr[j], arr[i])
i j pivot
i=1, j=5 |2|1|8|6|7|5|4|
i j pivot
As, j=6, exit loop
i=1, j=6 |2|1|4|6|7|5|8| swap(arr[i+1], arr[pivot])
pivot=2 i pivot j
Now, return pivot index (i.e i+1)
*/