Quickselect es un algoritmo de selección para encontrar el k-ésimo elemento más pequeño en una lista desordenada. Está relacionado con el algoritmo de clasificación de clasificación rápida .
Ejemplos:
Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7
Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10
El algoritmo QuickSelect se basa en QuickSort . La diferencia es que, en lugar de repetirse para ambos lados (después de encontrar el pivote), se repite solo para la parte que contiene el k-ésimo elemento más pequeño. La lógica es simple, si el índice del elemento particionado es mayor que k, recurrimos a la parte izquierda. Si el índice es igual que k, hemos encontrado el k-ésimo elemento más pequeño y regresamos. Si el índice es menor que k, recurrimos a la parte derecha. Esto reduce la complejidad esperada de O(n log n) a O(n), con el peor caso de O(n^2).
function quickSelect(list, left, right, k)
if left = right
return list[left]
Select a pivotIndex between left and right
pivotIndex := partition(list, left, right,
pivotIndex)
if k = pivotIndex
return list[k]
else if k < pivotIndex
right := pivotIndex - 1
else
left := pivotIndex + 1
Hemos discutido una implementación recursiva de QuickSelect . En esta publicación, vamos a discutir la implementación iterativa simple.
C++
// CPP program for iterative implementation of QuickSelect
#include <bits/stdc++.h>
using namespace std;
// Standard Lomuto partition function
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
// Implementation of QuickSelect
int kthSmallest(int a[], int left, int right, int k)
{
while (left <= right) {
// Partition a[left..right] around a pivot
// and find the position of the pivot
int pivotIndex = partition(a, left, right);
// If pivot itself is the k-th smallest element
if (pivotIndex == k - 1)
return a[pivotIndex];
// If there are more than k-1 elements on
// left of pivot, then k-th smallest must be
// on left side.
else if (pivotIndex > k - 1)
right = pivotIndex - 1;
// Else k-th smallest is on right side.
else
left = pivotIndex + 1;
}
return -1;
}
// Driver program to test above methods
int main()
{
int arr[] = { 10, 4, 5, 8, 11, 6, 26 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout << "K-th smallest element is "
<< kthSmallest(arr, 0, n - 1, k);
return 0;
}
Java
// Java program for iterative implementation
// of QuickSelect
class GFG
{
// Standard Lomuto partition function
static int partition(int arr[],
int low, int high)
{
int temp;
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
if (arr[j] <= pivot)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
// Implementation of QuickSelect
static int kthSmallest(int a[], int left,
int right, int k)
{
while (left <= right)
{
// Partition a[left..right] around a pivot
// and find the position of the pivot
int pivotIndex = partition(a, left, right);
// If pivot itself is the k-th smallest element
if (pivotIndex == k - 1)
return a[pivotIndex];
// If there are more than k-1 elements on
// left of pivot, then k-th smallest must be
// on left side.
else if (pivotIndex > k - 1)
right = pivotIndex - 1;
// Else k-th smallest is on right side.
else
left = pivotIndex + 1;
}
return -1;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 10, 4, 5, 8, 11, 6, 26 };
int n = arr.length;
int k = 5;
System.out.println("K-th smallest element is " +
kthSmallest(arr, 0, n - 1, k));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program for iterative implementation
# of QuickSelect
# Standard Lomuto partition function
def partition(arr, low, high) :
pivot = arr[high]
i = (low - 1)
for j in range(low, high) :
if arr[j] <= pivot :
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return (i + 1)
# Implementation of QuickSelect
def kthSmallest(a, left, right, k) :
while left <= right :
# Partition a[left..right] around a pivot
# and find the position of the pivot
pivotIndex = partition(a, left, right)
# If pivot itself is the k-th smallest element
if pivotIndex == k - 1 :
return a[pivotIndex]
# If there are more than k-1 elements on
# left of pivot, then k-th smallest must be
# on left side.
elif pivotIndex > k - 1 :
right = pivotIndex - 1
# Else k-th smallest is on right side.
else :
left = pivotIndex + 1
return -1
# Driver Code
arr = [ 10, 4, 5, 8, 11, 6, 26 ]
n = len(arr)
k = 5
print("K-th smallest element is",
kthSmallest(arr, 0, n - 1, k))
# This code is contributed by
# divyamohan123
C#
// C# program for iterative implementation
// of QuickSelect
using System;
class GFG
{
// Standard Lomuto partition function
static int partition(int []arr,
int low, int high)
{
int temp;
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
if (arr[j] <= pivot)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
// Implementation of QuickSelect
static int kthSmallest(int []a, int left,
int right, int k)
{
while (left <= right)
{
// Partition a[left..right] around a pivot
// and find the position of the pivot
int pivotIndex = partition(a, left, right);
// If pivot itself is the k-th smallest element
if (pivotIndex == k - 1)
return a[pivotIndex];
// If there are more than k-1 elements on
// left of pivot, then k-th smallest must be
// on left side.
else if (pivotIndex > k - 1)
right = pivotIndex - 1;
// Else k-th smallest is on right side.
else
left = pivotIndex + 1;
}
return -1;
}
// Driver Code
public static void Main (String[] args)
{
int []arr = { 10, 4, 5, 8, 11, 6, 26 };
int n = arr.Length;
int k = 5;
Console.WriteLine("K-th smallest element is " +
kthSmallest(arr, 0, n - 1, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for iterative implementation of QuickSelect
// Standard Lomuto partition function
function partition(arr, low, high)
{
let temp;
let pivot = arr[high];
let i = (low - 1);
for (let j = low; j <= high - 1; j++)
{
if (arr[j] <= pivot)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
// Implementation of QuickSelect
function kthSmallest(a, left, right, k)
{
while (left <= right)
{
// Partition a[left..right] around a pivot
// and find the position of the pivot
let pivotIndex = partition(a, left, right);
// If pivot itself is the k-th smallest element
if (pivotIndex == k - 1)
return a[pivotIndex];
// If there are more than k-1 elements on
// left of pivot, then k-th smallest must be
// on left side.
else if (pivotIndex > k - 1)
right = pivotIndex - 1;
// Else k-th smallest is on right side.
else
left = pivotIndex + 1;
}
return -1;
}
let arr = [ 10, 4, 5, 8, 11, 6, 26 ];
let n = arr.length;
let k = 5;
document.write("K-th smallest element is " + kthSmallest(arr, 0, n - 1, k));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
K-th smallest element is 10
Complejidad del tiempo : O(n 2 )
Espacio Auxiliar : O(1)