###
**What is Quick Select Algorithm? How to implement in C++?**

- The QuickSelect algorithm quickly finds the k-th smallest element of an unsorted array of n elements.
- It is an
*O*(*n*), worst-case linear time, selection algorithm. A typical selection by sorting method would need atleast O(*n* log *n*) time.
- This algorithm is identical to quick sort but it does only a partial sort, since we already know which partition our desired element lies as the pivot is in final sorted position.

###
Quick select implementation in C++

```
#include <iostream>
using namespace std;
// A simple print function
void print(int *input)
{
for ( int i = 0; i < 5; i++ )
cout << input[i] << " ";
cout << endl;
}
int partition(int* input, int p, int r)
{
int pivot = input[r];
while ( p < r )
{
while ( input[p] < pivot )
p++;
while ( input[r] > pivot )
r--;
if ( input[p] == input[r] )
p++;
else if ( p < r ) {
int tmp = input[p];
input[p] = input[r];
input[r] = tmp;
}
}
return r;
}
int quick_select(int* input, int p, int r, int k)
{
if ( p == r ) return input[p];
int j = partition(input, p, r);
int length = j - p + 1;
if ( length == k ) return input[j];
else if ( k < length ) return quick_select(input, p, j - 1, k);
else return quick_select(input, j + 1, r, k - length);
}
int main()
{
int A1[] = { 100, 400, 300, 500, 200 };
cout << "1st order element " << quick_select(A1, 0, 4, 1) << endl;
int A2[] = { 100, 400, 300, 500, 200 };
cout << "2nd order element " << quick_select(A2, 0, 4, 2) << endl;
int A3[] = { 100, 400, 300, 500, 200 };
cout << "3rd order element " << quick_select(A3, 0, 4, 3) << endl;
int A4[] = { 100, 400, 300, 500, 200 };
cout << "4th order element " << quick_select(A4, 0, 4, 4) << endl;
int A5[] = { 100, 400, 300, 500, 200 };
cout << "5th order element " << quick_select(A5, 0, 4, 5) << endl;
}
```

OUTPUT:-

1st order element 100
2nd order element 200
3rd order element 300
4th order element 400
5th order element 500

Wow! very nice information. i was searching article like this.

ReplyDeleteThanks

http://mlmdevelopers.com/products/mlm-software/mlm-software-beta/features.html

Nice coding, Have more- please welcome

ReplyDeleteHi,

ReplyDeleteLast many days I am searching some good article and I am very glad to find your article. This is very essential and informative information for me. I would like to say your post is superb and relevant my topics.

Thanks

The blog was absolutely fantastic! Lots of great information and

ReplyDeleteinspiration, both of which we all need!b Keep 'em coming... you all do

such a great job at such Concepts... can't tell you how much I, for

one appreciate all you do!

The blog was absolutely fantastic! Lots of great information and

ReplyDeleteinspiration, both of which we all need!b Keep 'em coming... you all do

such a great job at such Concepts... can't tell you how much I, for

one appreciate all you do!

Thanks!

ReplyDeleteConcise and informational!!!

ReplyDeleteGood One. But I think if you choose the pivot from the last element of the array, it would not be a linearized algorithm. Instead I think you should do a randomized partition where you choose a random pivot and track where it ends up after you partition and then do recursion. Even by using Randomized method, the worst case is O(n2). http://pine.cs.yale.edu/pinewiki/QuickSelect

ReplyDeleteTo minimize the worst case complexity, median of medians is used to choose the pivot.

http://www.ics.uci.edu/~eppstein/161/960130.html

good and informative post. very nice and well organie. thanks for sharing.

ReplyDeletehelpful for me....

the time complexity is not O(n).

ReplyDeletehow to implement it in c please help i m newcommer to programming

ReplyDeleteall this on the condition there is no multiple values...

ReplyDeletei Think the time complexity is not O(n)

ReplyDelete