Quickselect vs Countingselect

[Sasstraliss]

Quickselect, based on quicksort, and counting select, based on counting sort.

Each is capable of finding the kth smallest element in an unsorted/sorted list/array.


This is some example code for a QuickSelect algorithm. This doesn't include the partition function.

// return the kth smallest item
int quickSelect(int items[], int first, int last, int k) {
    int pivot = partition(items, first, last);
    if (k < pivot-first) {
        return quickSelect(items, first, pivot, k);
    } else if (k > pivot) {
        return quickSelect(items, pivot+1, last, k-pivot);
    } else {
        return items[k];
    }
}

Counting select, based on the counting sort algorithm, looks something like this.

// return the kth smallest item
int countingSelect(int items[], int first, int last, int k) {
    int counts[cap];
    for (int c = 0; c < cap; c++) {
        counts[c] = 0;
    }
    for (int i = first; i < last; i++) {
        counts[items[i]] += 1;
    }
    int c = 0;
    while (k >= 0) {
        k -= counts[c++];
    }
    return c-1;
}

I wish to write a set of guidelines to decide which of the two algorithms is most appropriate for specific situations or data sets. I need to think of situations, and than implement guidelines as to which algorithm is the better choice.

For this, I need a little help distinguishing which algorithm has specific strengths in certain areas/data sets and varieties, etc.

Thanks in advance.