Quick Select

Nasıl düşünülür

Quick select, yalnızca bir yarıya rekürse eden quicksort’tur. Pivot seç, diziyi pivottan küçükler sola, büyükler sağa olacak şekilde bölüm. Pivot sıralı konumu p’ye yerleşir. p === k ise bittin. p < k ise sağa, p > k ise sola rekürse et. Her adım diziyi kabaca yarıya indirir → O(n) ortalama, O(n log n) tam sıralamadan çok ucuz.

Düşman worst case O(n²)’dir: kötü pivot (ör. sıralı girdide hep ilk eleman) diziyi her adımda bir eleman küçültür. Rastgele pivot bunu üstel olarak olasıksız yapar. K, N’ye göre küçükse heap (O(n log k)) quick select’i geçebilir, ama K N’nin bir kısmıysa veya tek sıralı istatistik gerekiyorsa quick select kazanır.

Şablon şekilleri

Şekil	Temel hamle	Örnek
k. en küçük	Partisyon, k’yı içeren yarıya rekürse	LC 215, LC 378
Top K	K. sıraya quick select, sol partisyonu dilimle	LC 347, LC 973
Akış top K	Heap (quick select değil), kökte seç	LC 703
Medyan	n/2’ye quick select (veya çift n için iki select)	,

Karmaşıklık temeli

O(n) ortalama zaman, O(n²) worst case (rastgele pivot ile azaltılır). O(1) ekstra alan (yerinde). Rekürsyon derinliği ortalama O(log n). Akış top-K veya çok küçük K için O(n log k)’lik heap tercih edilir.

Şablondan probleme

1. k’yı netleştir: 0-indexed mi 1-indexed mi? En küçük mü en büyük mü (karşılaştırmayı çevir)?
2. Pivot stratejisi seç, rastgele güvenli varsayılan.
3. [< pivot | pivot | > pivot] partisyonu yap, pivot indeksini k ile karşılaştır.
4. Yalnızca k’yı içeren tarafa rekürse et; bulunca dön.
5. Top-K için K. elemana quick select sonra dilimle, veya K küçükse heap kullan.

/** Quick select template: kth smallest (0-indexed) via randomized partition. */

export function quickSelect(nums: number[], k: number): number {
  return select(nums, 0, nums.length - 1, k);
}

function select(nums: number[], lo: number, hi: number, k: number): number {
  if (lo === hi) return nums[lo]!;
  const pivotIdx = partition(nums, lo, hi);
  if (k === pivotIdx) return nums[k]!;
  if (k < pivotIdx) return select(nums, lo, pivotIdx - 1, k);
  return select(nums, pivotIdx + 1, hi, k);
}

function partition(nums: number[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j]! < pivot) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

/** Quick select template: kth smallest (0-indexed) via randomized partition. */

export function quickSelect(nums: number[], k: number): number {
  return select(nums, 0, nums.length - 1, k);
}

function select(nums: number[], lo: number, hi: number, k: number): number {
  if (lo === hi) return nums[lo]!;
  const pivotIdx = partition(nums, lo, hi);
  if (k === pivotIdx) return nums[k]!;
  if (k < pivotIdx) return select(nums, lo, pivotIdx - 1, k);
  return select(nums, pivotIdx + 1, hi, k);
}

function partition(nums: number[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j]! < pivot) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}