The k-th smallest number – Algorithms Practice Problem

Quick sort sorts both sides. If you only want one position, you only need one side.

What to build

A quickselect program that finds the k-th smallest number and counts its partition steps.

Requirements

Use Lomuto partition, with the last number of the range as the pivot and a strict < when comparing.
Keep a range lo .. hi. While lo < hi, partition it and add 1 to the count.
If the pivot lands at index k - 1, stop. Otherwise continue with the side that holds index k - 1.
Print the number and the count.

Input

The first line has n and k. The second line has the n numbers.

Output

One line: the k-th smallest number, then the number of partitions.

Constraints

1 ≤ k ≤ n ≤ 500.

Example

Input:

7 4
7 2 9 4 3 8 5

Output:

5 1

Why it works

Each partition places one number in its final position and throws away one side. With good pivots the ranges shrink as n + n/2 + n/4 and so on, which is O(n) on average, but sorted input can still cost O(n²).

Examples

Example 1 · Input

7 4
7 2 9 4 3 8 5

Expected output

5 1

Example 2 · Input

3 1
3 1 2

Expected output

1 1

Hints

Hint 1

After one partition, the pivot is at its final index `p`. If `p` is the index you want, you have finished.

Hint 2

Otherwise only one side can contain the answer, so continue with just that side.

Hint 3

Count a partition only when the range has at least two numbers. A range of one number is the answer.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>

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

int partition(int a[], int lo, int hi) {
    int pivot = a[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            swap(&a[i], &a[j]);
            i++;
        }
    }
    swap(&a[i], &a[hi]);
    return i;
}

int main(void) {
    int n, k, a[500];
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int lo = 0, hi = n - 1, partitions = 0, want = k - 1;
    while (lo < hi) {
        int p = partition(a, lo, hi);
        partitions++;
        if (p == want) break;
        if (p > want) hi = p - 1;
        else lo = p + 1;
    }
    printf("%d %d\n", a[want], partitions);
    return 0;
}

Lesson: Quick sort →