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.
- Code: Select all
// 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.
- Code: Select all
// 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.
