How would you this random-select quicksort to get multiple elements?

QuestionableCodingPractices 0
Viewed 57

I'm currently new to algorithms, and I had come across a way to get the K-th smallest element in an array using a random select from quicksort. However, there was an exercise that someone proposed to make it so it returned the K-th smallest elementS, for example:
Right now, if I ran this array with my random-select looking for the 3rd smallest element(k = 3):
int a[6] = { 1,3,4,2,5,6 }
random_select(a, 0, 5, 3);
would output "3"
but I am looking for 1 2 3 , or up to the K-th smallest element.

Here is the code currently:

int random_select(int a[], int p, int r, int i) {

    if (p == r) {
        return a[p];
    }
    int q = partition_random(a, p, r);
    int k = q - p + 1;
    if (i == k) { //this is our element
        return a[q];
    }

    else if (i < k) { //on the left side
        return random_select(a, p, q - 1, i);
    }
    else { // right side
        return random_select(a, q + 1, r, i - k);
    }
}
quicksort random c algorithm
1 Answers

Why use a bulldozer to sweep crumbs off the table?

If you want the lowest 'n' values of an array, simply traverse the array looking for those values.

Below are two versions, one in array sequence, and one in sorted order of qualifying values.

KISS!

int cmp( const void *a, const void *b ) { return *(int*)a - *(int*)b; }

int main() {
    size_t i = 0, n = 0;
    int a[] = { 1,3,4,2,5,6 };
    const int sz = sizeof a/sizeof a[0];

    printf( "Simple selection <= 3\n" );
    for( i = 0; i < sz; i++ )
        if( a[i] <= 3 )
            printf( "%d ", a[ i ] );
    puts( "" );

    int srt[ sz ];
    for( i = 0; i < sz; i++ )
        if( a[i] <= 3 )
            srt[ n++ ] = a[ i ];
    qsort( srt, n, sizeof srt[0], cmp );
    printf( "Sorted selection <= 3\n" );
    for( i = 0; i < n; i++ )
        printf( "%d ", srt[ i ] );
    puts( "" );


    return 0;
}

Output

Simple selection <= 3
1 3 2
Sorted selection <= 3
1 2 3

EDIT: So much for KISS. To be "general", maybe more like this

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// "helper" function
void show( int a[], size_t ssz ) {
    for( size_t si = 0; si < ssz; si++ )
        printf( "%d ", a[ si ] );
    puts( "" );
}

// for "qsort()"
int cmp( const void *a, const void *b ) { return *(int*)a - *(int*)b; }

// general purpose "sniffer" for 'K' lowest values
// no check of "lowest 10 values of 5 element array"
void func( int a[], size_t sz, size_t K ) {
    int select[ 100 ]; // should be [K], but no VLA's for my old compiler
    size_t ai = 0, si = 0, sii = 0, Mx = 0;

    // Start with first 'K' elements as default
    for( si = 0; si < K; si++ )
        select[ si ] = a[ si ];

    // compare further elements against what's been selected
    for( ai = K; ai < sz; ai++ )
        for( si = 0; si < K; si++ )
            if( a[ ai ] < select[ si ] ) {
                // higher than one...find highest to replace
                for( Mx = si, sii = Mx + 1; sii < K; sii++ ) {
                    if( select[ Mx ] < select[ sii ] )
                        Mx = sii;
                }
                select[ Mx ] = a[ ai ];
                break;
            }

    // now some output
    printf( "%20s: K(%d) :: ", "In sequence", K );
    show( select, K );

    printf( "%20s: K(%d) :: ", "Sorted", K );
    qsort( select, K, sizeof select[0], cmp );
    show( select, K );
}

int main() { // a handful of tests
    {
        int a[] = { -15839, 113, 69849, 40, 0, 938 };
        func( a, sizeof a/sizeof a[0], 3 );
        func( a, sizeof a/sizeof a[0], 4 );
    }
    puts("");
    {
        int a[] = { 9, 8, 7, 6, 5, 4 };
        func( a, sizeof a/sizeof a[0], 3 );
        func( a, sizeof a/sizeof a[0], 4 );
    }

    return 0;
}

Output

         In sequence: K(3) :: -15839 0 40
              Sorted: K(3) :: -15839 0 40
         In sequence: K(4) :: -15839 113 0 40
              Sorted: K(4) :: -15839 0 40 113

         In sequence: K(3) :: 6 5 4
              Sorted: K(3) :: 4 5 6
         In sequence: K(4) :: 5 4 7 6
              Sorted: K(4) :: 4 5 6 7

Could be a tiny bit more general and complicated using indices instead of anchoring func() as dealing only with int arrays... This exercise is left for the reader...

Fe2O30
Related