-
Notifications
You must be signed in to change notification settings - Fork 4
/
quick_sort(divide&conquer).cpp
executable file
·116 lines (101 loc) · 2.39 KB
/
quick_sort(divide&conquer).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
//Code
#include<iostream>
#include<time.h>
using namespace std;
class quick_sort
{
private:
int n,z;
int A[20];
public:
void swap(int* a, int* b);
void accept();
void display(int arr[]);
void quicksort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
};
void quick_sort::swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
void quick_sort::accept()
{
cout<<"\nEnter the number of elements : ";
cin>>n;
cout<<"\nEnter the elements : \n";
for(z=0;z<n;z++)
cin>>A[z];
cout<<"\nUnsorted elements are : \n";
display(A);
time_t x, y;
time(&x);
quicksort(A,0,n-1);
time(&y);
double time_taken = double(y-x);
cout<<"\nTime take by function : "<<fixed<<time_taken;
cout<<"\nSorted elements are : \n";
display(A);
}
void quick_sort::display(int arr[])
{
for(z=0;z<n;z++)
cout<<A[z]<<"\t";
cout<<endl;
}
void quick_sort::quicksort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int quick_sort::partition(int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
int main()
{
quick_sort q;
q.accept();
return 0;
}
/*OUTPUT
safir@safir-Predator-PH315-51:~/Desktop/DAA codes$ g++ quick.cpp
safir@safir-Predator-PH315-51:~/Desktop/DAA codes$ ./a.out
Enter the number of elements : 5
Enter the elements :
4
2
7
9
8
Unsorted elements are :
4 2 7 9 8
Sorted elements are :
2 4 7 8 9
*/