# Partial Sort Selection

# Partial Sort Selection

Partial Sort Selection finds the k-th smallest element by sorting only the first $k + 1$ smallest elements, rather than the entire array.

This method is simple and often practical when you also need the smallest $k$ elements in sorted order.

## Problem

Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$, return the k-th smallest element.

## Algorithm

Rearrange the array so that the smallest $k + 1$ elements occupy the first part, and sort only that prefix.

```id="ps1"
partial_sort_selection(A, k):
    build max heap H from first k + 1 elements

    for i from k + 1 to n - 1:
        if A[i] < max(H):
            replace max(H) with A[i]

    sort H

    return H[k]
```

This produces the smallest $k + 1$ elements in sorted order.

## Alternative Form

Using selection + sort:

```id="ps2"
partial_sort_selection(A, k):
    quickselect to partition around k
    sort A[0..k]
    return A[k]
```

## Example

Let

$$
A = [7, 2, 9, 4, 3]
$$

and

$$
k = 2
$$

The smallest three elements are:

$$
[2, 3, 4]
$$

After sorting this prefix, the k-th element is:

$$
4
$$

## Correctness

After the heap phase, the structure contains the smallest $k + 1$ elements of the array. Sorting this subset produces the correct order. The element at index $k$ within this subset is the k-th smallest element globally.

## Complexity

| method           | time                     |
| ---------------- | ------------------------ |
| heap based       | $O(n \log k + k \log k)$ |
| selection + sort | $O(n + k \log k)$        |

Space:

$$
O(k)
$$

## When to Use

Use Partial Sort Selection when:

* you need both the k-th element and the smallest $k$ elements
* $k$ is much smaller than $n$
* sorted output for the prefix is required

If only the k-th element is needed, Quickselect is usually faster.

## Implementation

```id="ps3"
import heapq

def partial_sort_selection(a, k):
    heap = [-x for x in a[:k+1]]
    heapq.heapify(heap)

    for x in a[k+1:]:
        if x < -heap[0]:
            heapq.heapreplace(heap, -x)

    result = sorted([-x for x in heap])
    return result[k]
```

```id="ps4"
func PartialSortSelection(a []int, k int) int {
	h := &MaxHeap{}
	heap.Init(h)

	for i := 0; i < k+1; i++ {
		heap.Push(h, a[i])
	}

	for i := k + 1; i < len(a); i++ {
		if a[i] < (*h)[0] {
			heap.Pop(h)
			heap.Push(h, a[i])
		}
	}

	tmp := make([]int, h.Len())
	copy(tmp, *h)
	sortInts(tmp)

	return tmp[k]
}
```