2
\$\begingroup\$

I wrote a quick-select filter in C on Wednesday. (The code is below.)

It is a filter in the UNIX tradition:

  • It reads from standard input k, the rank of the integer to select, n, the number of elements, and then n integers.

  • It outputs the kth highest integer.

(A perhaps better design would take k as an argument—but a bigger gripe of mine is having to give n! Bonus points if an answer can show me how to avoid reading n from stdin or as an argument. I would read until EOF, but then I would have to deal with a growing array, I think.)

For the unfamiliar, quickselect can find the kth highest integer in O(n) time. The naïve selection algorithm sorts in place and then accesses element k, for O(n lg n) runtime. Quickselect does not sort large lists and achieves linear performance.

kth_largest.c

/*d. ben knoble 2019.10.02*/

/*
 * PROGRAM
 *
 * k_largest
 *
 * Finds the kth largest element of an array in O(n) time.
 *
 * Reads from standard input
 *
 * - k: which element to find
 * - n: number of elements
 * - n elements
 *
 * Outputs kth largest element to standard out.
 *
 * IMPLEMENTATION
 *
 * see kth_largest function
 */

#include <assert.h>
#include <err.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int compare_longs(const void *a, const void *b) {
    long x = *(long *)a;
    long y = *(long *)b;
    if (x < y)
        return -1;
    else if (x > y)
        return 1;
    return 0;
}

void sort(long *a, size_t n) {
    qsort(a, n, sizeof(long), compare_longs);
}

size_t med_index(size_t i) {
    return (size_t)(floor(i/2));
}

void swap(long *a, long *b) {
    long t = *a;
    *a = *b;
    *b = t;
}

size_t partition(long pivot, long *array, size_t n_elts) {
    // find the pivot
    size_t pos = -1;
    for (size_t i = 0; i < n_elts; ++i) {
        if (array[i] == pivot) {
            pos = i;
            break;
        }
    }
    assert(pos >= 0);
    swap(&array[pos], &array[n_elts-1]);
    // now pivot is at the end of the array

    size_t i = 0;
    for (size_t j = 0; j < n_elts; ++j) {
        if (array[j] < pivot) {
            swap(&array[j], &array[i]);
            ++i;
        }
    }
    swap(&array[i], &array[n_elts-1]);

    return i;
}

long kth_largest(size_t k, long *array, size_t n_elts) {
    size_t n_sublists = n_elts/5;
    long *medians = malloc(n_sublists * sizeof(long));
    if (medians == NULL) { err(1, NULL); }

    // sort sublists of 5 elements
    for (size_t i = 0; i < n_sublists; ++i) {
        size_t start = i*5;
        size_t left = n_elts - start < 5 ? n_elts - start : 5;
        sort(&array[start], left);
        if (left == 5)
            medians[i] = array[start + 3];
        else
            medians[i] = array[start + med_index(left)];
    }

    // determine pivot (possibly recursively)
    long pivot;
    if (n_sublists < 5)
        pivot = medians[med_index(n_sublists)];
    else
        pivot = kth_largest(med_index(n_sublists), medians, n_sublists);

    // partition
    size_t rank = partition(pivot, array, n_elts);
    if (k < rank)
        return kth_largest(k, array, rank-1);
    else if (k > rank)
        return kth_largest(rank - k, &array[rank+1], n_elts-(rank+1));
    // else k == rank
    return pivot;
}

int main(int argc, char **argv) {
    size_t k;
    size_t n_elts;
    scanf("%zd", &k);
    scanf("%zd", &n_elts);
    long *array = malloc(n_elts * sizeof(long));
    if (array == NULL) { err(1, NULL); }
    for (size_t i = 0; i < n_elts; ++i)
        scanf("%ld", &array[i]);

    printf("%ld\n", kth_largest(k, array, n_elts));
}
\$\endgroup\$
  • \$\begingroup\$ Aside: I've just realized I didn't actually free any of the memory I used 😳 \$\endgroup\$ – D. Ben Knoble Oct 4 at 18:35
2
\$\begingroup\$

Major stuff

Consider const

Design: kth_largest() has a side effect of re-arranging array. this is surprising and not part of "Finds the kth largest element of an array in O(n) time." I'd expect code to do the job without the side effect

// long kth_largest(size_t k, long *array, size_t n_elts) {
long kth_largest(size_t k, const long *array, size_t n_elts) {

Small size error

Code may call err(1, NULL); when n_elts < 5 as malloc(0) can return NULL. I'd expect code to work for sizes 1 to 4 also.

Doubtful O() claim

"Finds the kth largest element of an array in O(n) time." Perhaps when n >>> k, but not in general. I'd expect O(n*k). So perhaps

Finds the kth largest element of an array in O(n) time when k <<< n
otherwise O(n*k)

No error check

Do not trust user input follows the rules nor allocations always succeed.

long *array = malloc(n_elts * sizeof(long));
if (array == NULL) {
  Handle_Error();
}


for (size_t i = 0; i < n_elts; ++i) {
  // scanf("%ld", &array[i]);
  if (scanf("%ld", &array[i]) != 1) {
    Handle_Error();
  }
}

Minor stuff

object vs type

Rather than size to the type, size ot the object. Easier to code right, review and maintain.

// qsort(a, n, sizeof(long), compare_longs);
qsort(a, n, sizeof *a, compare_longs);

// long *medians = malloc(n_sublists * sizeof(long));
long *medians = malloc(sizeof *medians * n_sublists);

No need for floating point math

i/2 will already have "floor" the quotient before the floor(). Absolutely no need for floor() and with its potential loss if precision for large i.

// return (size_t)(floor(i/2));
return i/2;

size_t is an unsigned type
Enable all warnings

pos >= 0 is always true below. A well enabled compilers would have warned.

size_t pos = -1;
...
assert(pos >= 0);

Match specifier and type

"%zd" does not match a size_t. "%zu" does. Also implies useful warnings were not enabled. Save time - enable warnings. See also How to use “zd” specifier with printf()?/

// scanf("%zd", &k);
// scanf("%zd", &n_elts);
scanf("%zu", &k);
scanf("%zu", &n_elts);

Read until EOF

"I would read until EOF, but then I would have to deal with a growing array, I think." --> Yes, good idea. Confident this is up to D. Ben Knoble abilities, so will not post code.

Design idea: pass the k as an argv[] and the array via stdin.

\$\endgroup\$
  • \$\begingroup\$ Great feedback. Going to take this into consideration soon (I hope). One follow-up: my copy of the CLRS algorithm textbook gives a proof of this as being O(n) (section 9.3: Selection in worst-case linear time) \$\endgroup\$ – D. Ben Knoble Oct 8 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.