Recomendamos la lectura del siguiente post como requisito previo de este post.
K’th elemento más pequeño/más grande en array no ordenada | Serie 1
Dado un arreglo y un número k donde k es más pequeño que el tamaño del arreglo, necesitamos encontrar el k-ésimo elemento más pequeño en el arreglo dado. Se da que todos los elementos de la array son distintos.
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
Hemos discutido tres soluciones diferentes aquí .
En esta publicación se analiza el método 5, que es principalmente una extensión del método 4 (QuickSelect) analizado en la publicación anterior . La idea es elegir al azar un elemento pivote. Para implementar la partición aleatoria, usamos una función aleatoria, rand() para generar un índice entre l y r, intercambiamos el elemento en el índice generado aleatoriamente con el último elemento y finalmente llamamos al proceso de partición estándar que usa el último elemento como pivote.
A continuación se muestra una implementación de la selección rápida aleatoria anterior.
C++
// C++ implementation of randomized quickSelect
#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;
int randomPartition(int arr[], int l, int r);
// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method. ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around a random element and
// get position of pivot element in sorted array
int pos = randomPartition(arr, l, r);
// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallest(arr, l, pos-1, k);
// Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
}
// If k is more than the number of elements in the array
return INT_MAX;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Standard partition process of QuickSort(). It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]);
return i;
}
// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
int n = r-l+1;
int pivot = rand() % n;
swap(&arr[l + pivot], &arr[r]);
return partition(arr, l, r);
}
// Driver program to test above methods
int main()
{
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int n = sizeof(arr)/sizeof(arr[0]), k = 3;
cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
return 0;
}
Java
// Java program to find k'th smallest element in expected
// linear time
class KthSmallst
{
// This function returns k'th smallest element in arr[l..r]
// using QuickSort based method. ASSUMPTION: ALL ELEMENTS
// IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around a random element and
// get position of pivot element in sorted array
int pos = randomPartition(arr, l, r);
// If position is same as k
if (pos-l == k-1)
return arr[pos];
// If position is more, recur for left subarray
if (pos-l > k-1)
return kthSmallest(arr, l, pos-1, k);
// Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
}
// If k is more than number of elements in array
return Integer.MAX_VALUE;
}
// Utility method to swap arr[i] and arr[j]
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Standard partition process of QuickSort(). It considers
// the last element as pivot and moves all smaller element
// to left of it and greater elements to right. This function
// is used by randomPartition()
int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j < r; j++)
{
if (arr[j] <= x)
{
swap(arr, i, j);
i++;
}
}
swap(arr, i, r);
return i;
}
// Picks a random pivot element between l and r and
// partitions arr[l..r] arount the randomly picked
// element using partition()
int randomPartition(int arr[], int l, int r)
{
int n = r - l + 1;
int pivot = (int)(Math.random() * (n - 1));
swap(arr, l + pivot, r);
return partition(arr, l, r);
}
// Driver method to test above
public static void main(String args[])
{
KthSmallst ob = new KthSmallst();
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int n = arr.length,k = 3;
System.out.println("K'th smallest element is "+
ob.kthSmallest(arr, 0, n-1, k));
}
}
/*This code is contributed by Rajat Mishra*/
Python3
# Python3 implementation of randomized
# quickSelect
import random
# This function returns k'th smallest
# element in arr[l..r] using QuickSort
# based method. ASSUMPTION: ELEMENTS
# IN ARR[] ARE DISTINCT
def kthSmallest(arr, l, r, k):
# If k is smaller than number of
# elements in array
if (k > 0 and k <= r - l + 1):
# Partition the array around a random
# element and get position of pivot
# element in sorted array
pos = randomPartition(arr, l, r)
# If position is same as k
if (pos - l == k - 1):
return arr[pos]
if (pos - l > k - 1): # If position is more,
# recur for left subarray
return kthSmallest(arr, l, pos - 1, k)
# Else recur for right subarray
return kthSmallest(arr, pos + 1, r,
k - pos + l - 1)
# If k is more than the number of
# elements in the array
return 999999999999
def swap(arr, a, b):
temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
# Standard partition process of QuickSort().
# It considers the last element as pivot and
# moves all smaller element to left of it and
# greater elements to right. This function
# is used by randomPartition()
def partition(arr, l, r):
x = arr[r]
i = l
for j in range(l, r):
if (arr[j] <= x):
swap(arr, i, j)
i += 1
swap(arr, i, r)
return i
# Picks a random pivot element between l and r
# and partitions arr[l..r] around the randomly
# picked element using partition()
def randomPartition(arr, l, r):
n = r - l + 1
pivot = int(random.random() * n)
swap(arr, l + pivot, r)
return partition(arr, l, r)
# Driver Code
if __name__ == '__main__':
arr = [12, 3, 5, 7, 4, 19, 26]
n = len(arr)
k = 3
print("K'th smallest element is",
kthSmallest(arr, 0, n - 1, k))
# This code is contributed by PranchalK
C#
// C# program to find k'th smallest
// element in expected linear time
using System;
class GFG
{
// This function returns k'th smallest
// element in arr[l..r] using QuickSort
// based method. ASSUMPTION: ALL ELEMENTS
// IN ARR[] ARE DISTINCT
int kthSmallest(int []arr, int l, int r, int k)
{
// If k is smaller than number
// of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around a
// random element and get position
// of pivot element in sorted array
int pos = randomPartition(arr, l, r);
// If position is same as k
if (pos-l == k - 1)
return arr[pos];
// If position is more, recur
// for left subarray
if (pos - l > k - 1)
return kthSmallest(arr, l, pos - 1, k);
// Else recur for right subarray
return kthSmallest(arr, pos + 1, r,
k - pos + l - 1);
}
// If k is more than number of
// elements in array
return int.MaxValue;
}
// Utility method to swap arr[i] and arr[j]
void swap(int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Standard partition process of QuickSort().
// It considers the last element as pivot and
// moves all smaller element to left of it
// and greater elements to right. This function
// is used by randomPartition()
int partition(int []arr, int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
swap(arr, i, j);
i++;
}
}
swap(arr, i, r);
return i;
}
// Picks a random pivot element between
// l and r and partitions arr[l..r]
// around the randomly picked element
// using partition()
int randomPartition(int []arr, int l, int r)
{
int n = r - l + 1;
Random rnd = new Random();
int rand = rnd.Next(0, 1);
int pivot = (int)(rand * (n - 1));
swap(arr, l + pivot, r);
return partition(arr, l, r);
}
// Driver Code
public static void Main()
{
GFG ob = new GFG();
int []arr = {12, 3, 5, 7, 4, 19, 26};
int n = arr.Length,k = 3;
Console.Write("K'th smallest element is "+
ob.kthSmallest(arr, 0, n - 1, k));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// Php program to find k'th smallest
// element in expected linear time
// This function returns k'th smallest
// element in arr[l..r] using QuickSort based method.
// ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCT
function kthSmallest($arr, $l, $r, $k)
{
// If k is smaller than number of elements in array
if ($k > 0 && $k <= $r - $l + 1)
{
// Partition the array around a random element and
// get position of pivot element in sorted array
$pos = randomPartition($arr, $l, $r);
// If position is same as k
if ($pos-$l == $k-1)
return $arr[$pos];
// If position is more, recur for left subarray
if ($pos-$l > $k-1)
return kthSmallest($arr, $l, $pos-1, $k);
// Else recur for right subarray
return kthSmallest($arr, $pos+1, $r,
$k-$pos+$l-1);
}
// If k is more than the number of elements in the array
return PHP_INT_MAX;
}
function swap($a, $b)
{
$temp = $a;
$a = $b;
$b = $temp;
}
// Standard partition process of QuickSort().
// It considers the last element as pivot
// and moves all smaller element to left
// of it and greater elements to right.
// This function is used by randomPartition()
function partition($arr, $l, $r)
{
$x = $arr[$r];
$i = $l;
for ($j = $l; $j <= $r - 1; $j++)
{
if ($arr[$j] <= $x)
{
list($arr[$i], $arr[$j])=array($arr[$j],$arr[$i]);
//swap(&arr[i], &arr[j]);
$i++;
}
}
list($arr[$i], $arr[$r])=array($arr[$r],$arr[$i]);
//swap(&arr[i], &arr[r]);
return $i;
}
// Picks a random pivot element between
// l and r and partitions arr[l..r] around
// the randomly picked element using partition()
function randomPartition($arr, $l, $r)
{
$n = $r-$l+1;
$pivot = rand() % $n;
list($arr[$l + $pivot], $arr[$r]) =
array($arr[$r],$arr[$l + $pivot] );
//swap(&arr[l + pivot], &arr[r]);
return partition($arr, $l, $r);
}
// Driver program to test the above methods
$arr = array(12, 3, 5, 7, 4, 19, 260);
$n = sizeof($arr)/sizeof($arr[0]);
$k = 3;
echo "K'th smallest element is " ,
kthSmallest($arr, 0, $n-1, $k);
// This code is contributed by ajit.
?>
Javascript
<script>
// JavaScript program to find k'th smallest element in expected
// linear time
// This function returns k'th smallest element in arr[l..r]
// using QuickSort based method. ASSUMPTION: ALL ELEMENTS
// IN ARR[] ARE DISTINCT
function kthSmallest(arr,l,r,k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around a random element and
// get position of pivot element in sorted array
let pos = randomPartition(arr, l, r);
// If position is same as k
if (pos-l == k-1)
return arr[pos];
// If position is more, recur for left subarray
if (pos-l > k-1)
return kthSmallest(arr, l, pos-1, k);
// Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
}
// If k is more than number of elements in array
return Integer.MAX_VALUE;
}
// Utility method to swap arr[i] and arr[j]
function swap(arr,i,j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Standard partition process of QuickSort(). It considers
// the last element as pivot and moves all smaller element
// to left of it and greater elements to right. This function
// is used by randomPartition()
function partition(arr,l,r)
{
let x = arr[r], i = l;
for (let j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
swap(arr, i, j);
i++;
}
}
swap(arr, i, r);
return i;
}
// Picks a random pivot element between l and r and
// partitions arr[l..r] arount the randomly picked
// element using partition()
function randomPartition(arr,l,r)
{
let n = r-l+1;
let pivot = Math.floor((Math.random()) * (n-1));
swap(arr, l + pivot, r);
return partition(arr, l, r);
}
let arr=[12, 3, 5, 7, 4, 19, 26];
let n = arr.length,k = 3;
document.write("K'th smallest element is "+
kthSmallest(arr, 0, n-1, k));
// This code is contributed by rag2127
</script>
Producción
K'th smallest element is 5
Complejidad de tiempo:
La complejidad de tiempo en el peor de los casos de la solución anterior sigue siendo O(n 2 ). En el peor de los casos, la función aleatoria siempre puede elegir un elemento de esquina. La complejidad de tiempo esperada de QuickSelect aleatorio anterior es O (n), consulte el libro CLRS o la videoconferencia del MIT para obtener pruebas. La suposición en el análisis es que el generador de números aleatorios tiene la misma probabilidad de generar cualquier número en el rango de entrada.
Complejidad del espacio : O(1) ya que usa variables constantes
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA