El algoritmo de Floyd-Rivest es un algoritmo de selección que se utiliza para encontrar el k -ésimo elemento más pequeño en una array de elementos distintos. Es similar al algoritmo QuickSelect pero tiene un mejor tiempo de ejecución en la práctica.
Al igual que QuickSelect, el algoritmo funciona con la idea de la partición. Después de particionar una array, el elemento de partición termina en la posición ordenada corregida. Si la array tiene todos los elementos distintos, recuperar el (k+1) el elemento más pequeño es lo mismo que recuperar el (k+1) el elemento después de ordenar. Debido a que una clasificación completa es costosa (requiere O (N log N) para calcular), el algoritmo Floyd-Rivest aprovecha la partición para lograr lo mismo en tiempo O (N) .
Algoritmo:
- Si el tamaño de la array S que se está considerando es lo suficientemente pequeño, el algoritmo QuickSelect se aplica directamente para obtener el K-ésimo elemento más pequeño. Este tamaño es una constante arbitraria del algoritmo, que los autores eligieron como 600 .
- De lo contrario, se eligen 2 pivotes: newLeftIndex y newRightIndex utilizando un muestreo aleatorio de modo que tengan la mayor probabilidad de contener el k-ésimo elemento más grande. Luego, la función se llama recursivamente con los límites izquierdo y derecho de la array ahora establecidos en newLeftIndex y newRightIndex.
- Al igual que QuickSelect, después de dividir el subarreglo, los límites izquierdo y derecho deben establecerse de modo que contengan el elemento K más grande.
Después de dividir la array alrededor de K, el elemento Kth está en su posición ordenada correcta. Entonces, los límites izquierdo y derecho se establecen de tal manera que el subarreglo que se considera contiene array[k]
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the above approach.
#include <iostream>
#include <math.h>
using namespace std;
// Function to return the
// sign of a number
int sign(double x)
{
if (x < 0)
return -1;
if (x > 0)
return 1;
return 0;
}
// Function to swap
// two numbers in an array.
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int select(int arr[], int left,
int right, int k)
{
while (right > left) {
if (right - left > 600) {
// Choosing a small subarray
// S based on sampling.
// 600, 0.5 and 0.5
// are arbitrary constants
int n = right - left + 1;
int i = k - left + 1;
double z = log(n);
double s = 0.5 * exp(2 * z / 3);
double sd = 0.5 * sqrt(z * s
* (n - s) / n)
* sign(i - n / 2);
int newLeft = max(left,
(int)(k - i * s / n + sd));
int newRight = min(right,
(int)(k + (n - i) * s / n
+ sd));
select(arr, newLeft, newRight, k);
}
// Partition the subarray S[left..right]
// with arr[k] as pivot
int t = arr[k];
int i = left;
int j = right;
swap(arr, left, k);
if (arr[right] > t) {
swap(arr, left, right);
}
while (i < j) {
swap(arr, i, j);
i++;
j--;
while (arr[i] < t)
i++;
while (arr[j] > t)
j--;
}
if (arr[left] == t)
swap(arr, left, j);
else {
j++;
swap(arr, right, j);
}
// Adjust the left and right pointers
// to select the subarray having k
if (j <= k)
left = j + 1;
if (k <= j)
right = j - 1;
}
return arr[k];
}
// Driver code
int main()
{
int arr[] = { 7, 3, 4, 0, 1, 6 };
int n = sizeof(arr) / sizeof(int);
// k-th smallest element.
// In this we get the 2nd smallest element
int k = 2;
int res = select(arr, 0, n - 1, k - 1);
cout << "The " << k << "-th smallest element is "
<< res << endl;
return 0;
}
Java
// Java implementation of the above approach.
class GFG {
// Function to return
// the sign of the number
int sign(double x)
{
if (x < 0)
return -1;
if (x > 0)
return 1;
return 0;
}
// Function to swap two numbers in an array
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to return kth smallest number
int select(int arr[], int left,
int right, int k)
{
while (right > left) {
if (right - left > 600) {
// Choosing a small subarray
// S based on sampling.
// 600, 0.5 and 0.5 are
// arbitrary constants
int n = right - left + 1;
int i = k - left + 1;
double z = Math.log(n);
double s = 0.5 * Math.exp(2 * z / 3);
double sd = 0.5 * Math.sqrt(z * s * (n - s) / n)
* sign(i - n / 2);
int newLeft = Math.max(left,
(int)(k - i * s / n
+ sd));
int newRight = Math.min(right,
(int)(k + (n - i) * s / n
+ sd));
select(arr, newLeft, newRight, k);
}
// Partition the subarray S[left..right]
// with arr[k] as pivot
int t = arr[k];
int i = left;
int j = right;
swap(arr, left, k);
if (arr[right] > t) {
swap(arr, left, right);
}
while (i < j) {
swap(arr, i, j);
i++;
j--;
while (arr[i] < t)
i++;
while (arr[j] > t)
j--;
}
if (arr[left] == t)
swap(arr, left, j);
else {
j++;
swap(arr, right, j);
}
// Adjust the left and right
// pointers to select the subarray having k
if (j <= k)
left = j + 1;
if (k <= j)
right = j - 1;
}
return arr[k];
}
// Driver code
public static void main(String[] args)
{
int[] arr = new int[] { 7, 3, 4, 0, 1, 6 };
// k-th smallest element.
// In this we get the 2nd smallest element
int k = 2;
FloydRivest f = new FloydRivest();
int res = f.select(arr, 0, arr.length - 1, k - 1);
System.out.println("The " + k
+ "-th smallest element is " + res);
}
}
Python3
# Python implementation of the above approach.
import math
import random
# Function to return the
# sign of the number
def sign(x):
if x>0:
return 1
elif x<0:
return -1
return 0
# Function to swap two
# numbers in an array
def swap(arr, i, j):
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
# Function to return kth smallest number
def select(arr: list, left: int,
right: int, k: int):
while right>left:
# Choosing a small subarray
# S based on sampling.
# 600, 0.5 and 0.5 are
# arbitrary constants
if right-left > 600:
n = right - left + 1
i = k - left + 1
z = math.log(n)
s = 0.5 * math.exp(2 * z / 3)
sd = 0.5 * math.sqrt(z * s * (n-s)/n) * sign(i-n / 2)
newLeft = int(max(left, k-i * s / n + sd))
newRight = int(min(right, k + (n - i) * s / n + sd))
select(arr, newLeft, newRight, k)
t = arr[k]
i = left
j = right
swap(arr, left, k)
if arr[right] > t:
swap(arr, left, right)
while i<j:
swap(arr, i, j)
i = i + 1
j = j-1
while arr[i]<t:
i = i + 1
while arr[j] >t:
j = j-1
if arr[left] == t:
swap(arr, left, j)
else:
j = j + 1
swap(arr, right, j)
# Updating the left and right indices
# depending on position of k-th element
if j<= k:
left = j + 1
if k<= j:
right = j-1
return arr[k]
arr = [7, 3, 4, 0, 1, 6]
# k-th smallest element.
# In this the 2nd smallest element is returned.
k = 2
res = select(arr, 0, len(arr)-1, k-1)
print('The {}-th smallest element is {}'.format(k, res))
C#
// C# implementation of the above approach.
using System;
class GFG
{
// Function to return
// the sign of the number
static int sign(double x)
{
if (x < 0)
return -1;
if (x > 0)
return 1;
return 0;
}
// Function to swap two numbers in an array
static void swap(int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to return kth smallest number
static int select(int []arr, int left,
int right, int k)
{
int i;
while (right > left)
{
if (right - left > 600)
{
// Choosing a small subarray
// S based on sampling.
// 600, 0.5 and 0.5 are
// arbitrary constants
int n = right - left + 1;
i = k - left + 1;
double z = Math.Log(n);
double s = 0.5 * Math.Exp(2 * z / 3);
double sd = 0.5 * Math.Sqrt(z * s * (n - s) / n)
* sign(i - n / 2);
int newLeft = Math.Max(left,
(int)(k - i * s / n
+ sd));
int newRight = Math.Min(right,
(int)(k + (n - i) * s / n
+ sd));
select(arr, newLeft, newRight, k);
}
// Partition the subarray S[left..right]
// with arr[k] as pivot
int t = arr[k];
i = left;
int j = right;
swap(arr, left, k);
if (arr[right] > t)
{
swap(arr, left, right);
}
while (i < j)
{
swap(arr, i, j);
i++;
j--;
while (arr[i] < t)
i++;
while (arr[j] > t)
j--;
}
if (arr[left] == t)
swap(arr, left, j);
else
{
j++;
swap(arr, right, j);
}
// Adjust the left and right
// pointers to select the subarray having k
if (j <= k)
left = j + 1;
if (k <= j)
right = j - 1;
}
return arr[k];
}
// Driver code
public static void Main()
{
int[] arr = { 7, 3, 4, 0, 1, 6 };
// k-th smallest element.
// In this we get the 2nd smallest element
int k = 2;
int res = select(arr, 0, arr.Length - 1, k - 1);
Console.WriteLine("The " + k + "-th smallest element is " + res);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the above approach.
// Function to return
// the sign of the number
function sign(x)
{
if (x < 0)
return -1;
if (x > 0)
return 1;
return 0;
}
// Function to swap two numbers in an array
function swap(arr, i, j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to return kth smallest number
function select(arr, left, right, k)
{
let i;
while (right > left)
{
if (right - left > 600)
{
// Choosing a small subarray
// S based on sampling.
// 600, 0.5 and 0.5 are
// arbitrary constants
let n = right - left + 1;
i = k - left + 1;
let z = Math.log(n);
let s = 0.5 * Math.exp(2 * z / 3);
let sd = 0.5 * Math.sqrt(z * s * (n - s) / n)
* sign(i - n / 2);
let newLeft = Math.max(left, (k - i * s / n + sd));
let newRight = Math.min(right, (k + (n - i) * s / n
+ sd));
select(arr, newLeft, newRight, k);
}
// Partition the subarray S[left..right]
// with arr[k] as pivot
let t = arr[k];
i = left;
let j = right;
swap(arr, left, k);
if (arr[right] > t)
{
swap(arr, left, right);
}
while (i < j)
{
swap(arr, i, j);
i++;
j--;
while (arr[i] < t)
i++;
while (arr[j] > t)
j--;
}
if (arr[left] == t)
swap(arr, left, j);
else
{
j++;
swap(arr, right, j);
}
// Adjust the left and right
// pointers to select the subarray having k
if (j <= k)
left = j + 1;
if (k <= j)
right = j - 1;
}
return arr[k];
}
let arr = [ 7, 3, 4, 0, 1, 6 ];
// k-th smallest element.
// In this we get the 2nd smallest element
let k = 2;
let res = select(arr, 0, arr.length - 1, k - 1);
document.write("The " + k + "-th smallest element is " + res);
</script>
Producción:
The 2-th smallest element is 1
Complejidad del tiempo : O(N)