# Nth Element

# Nth Element

Nth Element rearranges an array so that the element at index $k$ is exactly the element that would appear at that position in a fully sorted array.

All elements before index $k$ are less than or equal to it, and all elements after are greater than or equal to it. The order within those partitions is not sorted.

This is a partition based selection primitive widely used in standard libraries.

## Problem

Given an array $A$ and an index $k$, reorder the array such that:

* $A[k]$ is the k-th smallest element
* for all $i < k$, $A[i] \le A[k]$
* for all $i > k$, $A[i] \ge A[k]$

## Algorithm

Use a Quickselect style partition process until the pivot lands at index $k$.

```id="ne1"
nth_element(A, k):
    left = 0
    right = length(A) - 1

    while true:
        pivot_index = choose_pivot(A, left, right)
        pivot_index = partition(A, left, right, pivot_index)

        if pivot_index == k:
            return
        else if k < pivot_index:
            right = pivot_index - 1
        else:
            left = pivot_index + 1
```

## Key Property

After execution:

$$
A[0..k-1] \le A[k] \le A[k+1..n-1]
$$

The array is only partially ordered.

## Example

Let

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

and

$$
k = 2
$$

After applying Nth Element, one valid result is:

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

The element at index $2$ is $4$, which matches the sorted position. The left and right sides are partitioned but not sorted internally.

## Correctness

Each partition step places the pivot in its final sorted position. By restricting the search interval to the side containing index $k$, the algorithm ensures that eventually the pivot lands exactly at $k$.

The partition invariant guarantees correct ordering relative to the pivot.

## Complexity

| case    | time     |
| ------- | -------- |
| average | $O(n)$   |
| worst   | $O(n^2)$ |

With randomized pivot or introselect fallback:

$$
O(n)
$$

Space:

$$
O(1)
$$

## When to Use

Use Nth Element when:

* you need partitioning around a rank
* you want top-k elements without sorting
* you plan to sort only a prefix or suffix

It is the standard primitive behind efficient partial sorting.

## Implementation

```id="ne2"
import random

def nth_element(a, k):
    def partition(left, right, pivot_index):
        pivot = a[pivot_index]
        a[pivot_index], a[right] = a[right], a[pivot_index]
        store = left
        for i in range(left, right):
            if a[i] < pivot:
                a[store], a[i] = a[i], a[store]
                store += 1
        a[right], a[store] = a[store], a[right]
        return store

    left, right = 0, len(a) - 1

    while True:
        if left == right:
            return

        pivot_index = random.randint(left, right)
        pivot_index = partition(left, right, pivot_index)

        if pivot_index == k:
            return
        elif k < pivot_index:
            right = pivot_index - 1
        else:
            left = pivot_index + 1
```

```id="ne3"
import "math/rand"

func NthElement(a []int, k int) {
	left, right := 0, len(a)-1

	for {
		if left == right {
			return
		}

		pivotIndex := left + rand.Intn(right-left+1)
		pivotIndex = partition(a, left, right, pivotIndex)

		if pivotIndex == k {
			return
		} else if k < pivotIndex {
			right = pivotIndex - 1
		} else {
			left = pivotIndex + 1
		}
	}
}
```