Skip to content

Instantly share code, notes, and snippets.

@Scientits
Last active April 25, 2018 14:35
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Scientits/a06845748f78621da577f6f6aaf4cc00 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
/*this function: last element as pivot then places all smaller elements to the left, the others to the right*/
int partitioN(int a[], int low, int high){
int pivot = a[high]; // this is pivot
int i = (low - 1); // index of smaller elements
for(int j = low; j <= high - 1; j++){
if(a[j] <= pivot){
i++; // index of low++
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[high]);
return (i + 1);
}
void quick_sort(int a[], int low, int high){
if(low < high){
int p_index = partitioN(a, low, high);
quick_sort(a, low, p_index - 1);
quick_sort(a, p_index + 1, high);
}
}
void prinT(int a[], int n){
int i;
for(int i = 0; i < n; i ++){
cout << a[i] << " ";
}cout << endl;
}
int main() {
int n;
cin >> n;
int a[100];
for(int i = 0; i < n; i++){
cin >> a[i];
}
quick_sort(a, 0, n - 1);
prinT(a,n);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment