Wednesday, June 22, 2011

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

13 comments :

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

    Thanks

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

    ReplyDelete
  2. Nice coding, Have more- please welcome

    ReplyDelete
  3. Hi,
    Last 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

    ReplyDelete
  4. The blog was absolutely fantastic! Lots of great information and
    inspiration, 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!

    ReplyDelete
  5. The blog was absolutely fantastic! Lots of great information and
    inspiration, 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!

    ReplyDelete
  6. Concise and informational!!!

    ReplyDelete
  7. Good 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
    To minimize the worst case complexity, median of medians is used to choose the pivot.
    http://www.ics.uci.edu/~eppstein/161/960130.html

    ReplyDelete
  8. good and informative post. very nice and well organie. thanks for sharing.
    helpful for me....

    ReplyDelete
  9. the time complexity is not O(n).

    ReplyDelete
  10. how to implement it in c please help i m newcommer to programming

    ReplyDelete
  11. all this on the condition there is no multiple values...

    ReplyDelete
  12. i Think the time complexity is not O(n)

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top