#include <bits/stdc++.h>
using namespace std;
// using Lomuto partition scheme
int Partition(int a[], int start, int end)
{
// Pick rightmost element as pivot from the array
int pivot = a[end];
// elements less than pivot will be pushed to the left of pIndex
// elements more than pivot will be pushed to the right of pIndex
// equal elements can go either way
int pIndex = start;
// each time we finds an element less than or equal to pivot, pIndex
// is incremented and that element would be placed before the pivot.
for (int i = start; i < end; i++)
{
if (a[i] <= pivot)
{
swap(a[i], a[pIndex]);
pIndex++;
}
}
// swap pIndex with Pivot
swap (a[pIndex], a[end]);
// return pIndex (index of pivot element)
return pIndex;
}
// using randomized partition
int RandomizedPartition(int a[], int start, int end)
{
// choose a random index between [start, end]
int pivotIndex = rand() % (end - start + 1) + start;
// swap the end element with element present at random index
swap(a[pivotIndex], a[end]);
// call partition procedure
return Partition(a, start, end);
}
// Quicksort routine
void QuickSort(int a[] ,int start, int end)
{
// base condition
if(start >= end)
return;
// rearrange the elements across pivot
int pivot = RandomizedPartition(a, start, end);
// recurse on sub-array containing elements that are less than pivot
QuickSort(a, start, pivot - 1);
// recurse on sub-array containing elements that are more than pivot
QuickSort(a, pivot + 1, end);
}
int main()
{
int a[] = { 9, -3, 5, 2, 6, 8, -6, 1, 3 };
int n = sizeof(a)/sizeof(a[0]);
QuickSort(a, 0, n - 1);
// print the sorted array
for (int i = 0 ; i < n; i++)
cout << a[i] << " ";
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyB1c2luZyBMb211dG8gcGFydGl0aW9uIHNjaGVtZQppbnQgUGFydGl0aW9uKGludCBhW10sIGludCBzdGFydCwgaW50IGVuZCkKewoJLy8gUGljayByaWdodG1vc3QgZWxlbWVudCBhcyBwaXZvdCBmcm9tIHRoZSBhcnJheQoJaW50IHBpdm90ID0gYVtlbmRdOwoKCS8vIGVsZW1lbnRzIGxlc3MgdGhhbiBwaXZvdCB3aWxsIGJlIHB1c2hlZCB0byB0aGUgbGVmdCBvZiBwSW5kZXgKCS8vIGVsZW1lbnRzIG1vcmUgdGhhbiBwaXZvdCB3aWxsIGJlIHB1c2hlZCB0byB0aGUgcmlnaHQgb2YgcEluZGV4CgkvLyBlcXVhbCBlbGVtZW50cyBjYW4gZ28gZWl0aGVyIHdheQoJaW50IHBJbmRleCA9IHN0YXJ0OwkKCQoJLy8gZWFjaCB0aW1lIHdlIGZpbmRzIGFuIGVsZW1lbnQgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIHBpdm90LCBwSW5kZXgKCS8vIGlzIGluY3JlbWVudGVkIGFuZCB0aGF0IGVsZW1lbnQgd291bGQgYmUgcGxhY2VkIGJlZm9yZSB0aGUgcGl2b3QuIAoJZm9yIChpbnQgaSA9IHN0YXJ0OyBpIDwgZW5kOyBpKyspCgl7CgkJaWYgKGFbaV0gPD0gcGl2b3QpCgkJewoJCQlzd2FwKGFbaV0sIGFbcEluZGV4XSk7CgkJCXBJbmRleCsrOwoJCX0KCX0KCS8vIHN3YXAgcEluZGV4IHdpdGggUGl2b3QKCXN3YXAgKGFbcEluZGV4XSwgYVtlbmRdKTsKCQoJLy8gcmV0dXJuIHBJbmRleCAoaW5kZXggb2YgcGl2b3QgZWxlbWVudCkKCXJldHVybiBwSW5kZXg7Cn0KCgovLyB1c2luZyByYW5kb21pemVkIHBhcnRpdGlvbgppbnQgUmFuZG9taXplZFBhcnRpdGlvbihpbnQgYVtdLCBpbnQgc3RhcnQsIGludCBlbmQpCnsKCS8vIGNob29zZSBhIHJhbmRvbSBpbmRleCBiZXR3ZWVuIFtzdGFydCwgZW5kXQoJaW50IHBpdm90SW5kZXggPSByYW5kKCkgJSAoZW5kIC0gc3RhcnQgKyAxKSArIHN0YXJ0OwoJCgkvLyBzd2FwIHRoZSBlbmQgZWxlbWVudCB3aXRoIGVsZW1lbnQgcHJlc2VudCBhdCByYW5kb20gaW5kZXgKCXN3YXAoYVtwaXZvdEluZGV4XSwgYVtlbmRdKTsKCQoJLy8gY2FsbCBwYXJ0aXRpb24gcHJvY2VkdXJlCglyZXR1cm4gUGFydGl0aW9uKGEsIHN0YXJ0LCBlbmQpOwp9CgovLyBRdWlja3NvcnQgcm91dGluZQp2b2lkIFF1aWNrU29ydChpbnQgYVtdICxpbnQgc3RhcnQsIGludCBlbmQpCnsKCS8vIGJhc2UgY29uZGl0aW9uCglpZihzdGFydCA+PSBlbmQpCgkJcmV0dXJuOwoKCS8vIHJlYXJyYW5nZSB0aGUgZWxlbWVudHMgYWNyb3NzIHBpdm90CglpbnQgcGl2b3QgPSBSYW5kb21pemVkUGFydGl0aW9uKGEsIHN0YXJ0LCBlbmQpOwoKCS8vIHJlY3Vyc2Ugb24gc3ViLWFycmF5IGNvbnRhaW5pbmcgZWxlbWVudHMgdGhhdCBhcmUgbGVzcyB0aGFuIHBpdm90CglRdWlja1NvcnQoYSwgc3RhcnQsIHBpdm90IC0gMSk7CgoJLy8gcmVjdXJzZSBvbiBzdWItYXJyYXkgY29udGFpbmluZyBlbGVtZW50cyB0aGF0IGFyZSBtb3JlIHRoYW4gcGl2b3QKCVF1aWNrU29ydChhLCBwaXZvdCArIDEsIGVuZCk7Cn0KCmludCBtYWluKCkKewoJaW50IGFbXSA9IHsgOSwgLTMsIDUsIDIsIDYsIDgsIC02LCAxLCAzIH07CglpbnQgbiA9IHNpemVvZihhKS9zaXplb2YoYVswXSk7CgkKCVF1aWNrU29ydChhLCAwLCBuIC0gMSk7CgoJLy8gcHJpbnQgdGhlIHNvcnRlZCBhcnJheQoJZm9yIChpbnQgaSA9IDAgOyBpIDwgbjsgaSsrKQoJCWNvdXQgPDwgYVtpXSA8PCAiICI7Cn0=