En este artículo, discutiremos cómo implementar QuickSort usando pivoteo aleatorio. En QuickSort, primero particionamos la array en su lugar de modo que todos los elementos a la izquierda del elemento pivote sean más pequeños, mientras que todos los elementos a la derecha del pivote sean más grandes que el pivote. Luego llamamos recursivamente al mismo procedimiento para los subarreglos izquierdo y derecho.
A diferencia de merge sort , no necesitamos fusionar las dos arrays ordenadas. Por lo tanto, Quicksort requiere menos espacio auxiliar que Merge Sort, por lo que a menudo se prefiere a Merge Sort. Usando un pivote generado aleatoriamente, podemos mejorar aún más la complejidad del tiempo de QuickSort.
Hemos discutido dos métodos populares para particionar las arrays : el esquema de partición de Hoare vs Lomuto
. Se recomienda que el lector haya leído ese artículo o sepa cómo implementar QuickSort usando cualquiera de los dos esquemas de partición.
Algoritmo para pivoteo aleatorio usando Lomuto Partitioning
partition(arr[], lo, hi)
pivot = arr[hi]
i = lo // place for swapping
for j := lo to hi – 1 do
if arr[j] <= pivot then
swap arr[i] with arr[j]
i = i + 1
swap arr[i] with arr[hi]
return i
partition_r(arr[], lo, hi)
r = Random Number from lo to hi
Swap arr[r] and arr[hi]
return partition(arr, lo, hi)
quicksort(arr[], lo, hi)
if lo < hi
p = partition_r(arr, lo, hi)
quicksort(arr, lo , p-1)
quicksort(arr, p+1, hi)
Implementación usando Lomuto Partitioning:
C++
// C++ implementation QuickSort
// using Lomuto's partition Scheme.
#include <cstdlib>
#include <time.h>
#include <iostream>
using namespace std;
// This function takes last element
// as pivot, places
// the pivot element at its correct
// position in sorted array, and
// places all smaller (smaller than pivot)
// to left of pivot and all greater
// elements to right of pivot
int partition(int arr[], int low, int high)
{
// pivot
int pivot = arr[high];
// Index of smaller element
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
// If current element is smaller
// than or equal to pivot
if (arr[j] <= pivot) {
// increment index of
// smaller element
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
// Generates Random Pivot, swaps pivot with
// end element and calls the partition function
int partition_r(int arr[], int low, int high)
{
// Generate a random number in between
// low .. high
srand(time(NULL));
int random = low + rand() % (high - low);
// Swap A[random] with A[high]
swap(arr[random], arr[high]);
return partition(arr, low, high);
}
/* The main function that implements
QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high) {
/* pi is partitioning index,
arr[p] is now
at right place */
int pi = partition_r(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout<<arr[i]<<" ";
}
// Driver Code
int main()
{
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Java
// Java program to illustrate
// Randomised Quick Sort
import java.util.*;
class RandomizedQsort
{
// This Function helps in calculating
// random numbers between low(inclusive)
// and high(inclusive)
static void random(int arr[],int low,int high)
{
Random rand= new Random();
int pivot = rand.nextInt(high-low)+low;
int temp1=arr[pivot];
arr[pivot]=arr[high];
arr[high]=temp1;
}
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
static int partition(int arr[], int low, int high)
{
// pivot is chosen randomly
random(arr,low,high);
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j = low; j < high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] < pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver Code
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
sort(arr, 0, n-1);
System.out.println("Sorted array");
printArray(arr);
}
}
// This code is contributed by Ritika Gupta.
Python3
# Python implementation QuickSort using # Lomuto's partition Scheme. import random ''' The function which implements QuickSort. arr :- array to be sorted. start :- starting index of the array. stop :- ending index of the array. ''' def quicksort(arr, start , stop): if(start < stop): # pivotindex is the index where # the pivot lies in the array pivotindex = partitionrand(arr,\ start, stop) # At this stage the array is # partially sorted around the pivot. # Separately sorting the # left half of the array and the # right half of the array. quicksort(arr , start , pivotindex-1) quicksort(arr, pivotindex + 1, stop) # This function generates random pivot, # swaps the first element with the pivot # and calls the partition function. def partitionrand(arr , start, stop): # Generating a random number between the # starting index of the array and the # ending index of the array. randpivot = random.randrange(start, stop) # Swapping the starting element of # the array and the pivot arr[start], arr[randpivot] = \ arr[randpivot], arr[start] return partition(arr, start, stop) ''' This function takes the first element as pivot, places the pivot element at the correct position in the sorted array. All the elements are re-arranged according to the pivot, the elements smaller than the pivot is places on the left and the elements greater than the pivot is placed to the right of pivot. ''' def partition(arr,start,stop): pivot = start # pivot # a variable to memorize where the i = start + 1 # partition in the array starts from. for j in range(start + 1, stop + 1): # if the current element is smaller # or equal to pivot, shift it to the # left side of the partition. if arr[j] <= arr[pivot]: arr[i] , arr[j] = arr[j] , arr[i] i = i + 1 arr[pivot] , arr[i - 1] =\ arr[i - 1] , arr[pivot] pivot = i - 1 return (pivot) # Driver Code if __name__ == "__main__": array = [10, 7, 8, 9, 1, 5] quicksort(array, 0, len(array) - 1) print(array) # This code is contributed by soumyasaurav
C#
// C# program to illustrate
// Randomised Quick sort
using System;
class RandomizedQsort
{
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
static int partition(int[] arr, int low, int high)
{
// pivot is chosen randomly
random(arr, low, high);
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j = low; j < high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] < pivot)
{
i++;
// swap arr[i] and arr[j]
int tempp = arr[i];
arr[i] = arr[j];
arr[j] = tempp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int tempp2 = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = tempp2;
return i + 1;
}
// This Function helps in calculating
// random numbers between low(inclusive)
// and high(inclusive)
static int random(int[] arr, int low, int high)
{
Random rand = new Random();
int pivot = rand.Next() % (high - low) + low;
int tempp1 = arr[pivot];
arr[pivot] = arr[high];
arr[high] = tempp1;
return partition(arr, low, high);
}
/* The main function that implements Quicksort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static void sort(int[] arr, int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver Code
static public void Main ()
{
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.Length;
sort(arr, 0, n-1);
Console.WriteLine("sorted array");
printArray(arr);
}
}
// This code is contributed by shubhamsingh10
C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int partition(int arr[], int low, int high)
{
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (1) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j)
return j;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int partition_r(int arr[], int low, int high)
{
srand(time(0));
int random = low + rand() % (high - low);
int temp = arr[random];
arr[random] = arr[low];
arr[low] = temp;
return partition(arr, low, high);
}
void quickSort(int arr[], int low, int high)
{
if (low < high) {
int pi = partition_r(arr, low, high);
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Producción
Sorted array: 1 5 7 8 9 10
Algoritmo para pivoteo aleatorio usando particionamiento de Hoare
partition(arr[], lo, hi)
pivot = arr[lo]
i = lo - 1 // Initialize left index
j = hi + 1 // Initialize right index
while(True)
// Find a value in left side greater than pivot
do
i = i + 1
while arr[i] < pivot
// Find a value in right side smaller than pivot
do
j = j - 1
while arr[j] > pivot
if i >= j then
return j
else
swap arr[i] with arr[j]
end while
partition_r(arr[], lo, hi)
r = Random number from lo to hi
Swap arr[r] and arr[lo]
return partition(arr, lo, hi)
quicksort(arr[], lo, hi)
if lo < hi
p = partition_r(arr, lo, hi)
quicksort(arr, lo, p)
quicksort(arr, p+1, hi)
Implementación usando el Particionamiento de Hoare:
C++
// C++ implementation of QuickSort
// using Hoare's partition scheme
#include <cstdlib>
#include <iostream>
using namespace std;
// This function takes last element as
// pivot, places the pivot element at
// its correct position in sorted
// array, and places all smaller
// (smaller than pivot) to left of pivot
// and all greater elements to right
int partition(int arr[], int low, int high)
{
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
// Find leftmost element greater than
// or equal to pivot
do {
i++;
} while (arr[i] < pivot);
// Find rightmost element smaller than
// or equal to pivot
do {
j--;
} while (arr[j] > pivot);
// If two pointers met
if (i >= j)
return j;
swap(arr[i], arr[j]);
}
}
// Generates Random Pivot, swaps pivot with
// end element and calls the partition function
// In Hoare partition the low element is selected
// as first pivot
int partition_r(int arr[], int low, int high)
{
// Generate a random number in between
// low .. high
srand(time(NULL));
int random = low + rand() % (high - low);
// Swap A[random] with A[high]
swap(arr[random], arr[low]);
return partition(arr, low, high);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
void quickSort(int arr[], int low, int high)
{
if (low < high) {
// pi is partitioning index,
// arr[p] is now at right place
int pi = partition_r(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver Code
int main()
{
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Java
/*
JAVA implementation of Randomize QuickSort
using Hoare's Partition
*/
import java.util.*;
class GFG
{
// swap function
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/*
// partition function
This function takes array, low and high index,
swaps low with random index between low and high
then places all elements less than pivot in the left
of pivot and all elements greater than pivot to the
right of pivot
*/
static int partition(int[] arr, int low, int high)
{
// rIndex gives the random index between low and
// high (both inclusive)
int rIndex = (low) + (int)(Math.random() * (high - low + 1));
swap(arr, low, rIndex); // swap low with random index
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
// increase i while elements are less than pivot
do {
i++;
} while (arr[i] < pivot);
// decrease j while elements are greater than pivot
do {
j--;
} while (arr[j] > pivot);
if (i >= j) // when both pointers meet
// that means elements are at their
// correct place for now
return j;
swap(arr, i, j);
// swap i and j, since both are not at their
// correct index
}
}
// recursive quick sort function
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
// find partition index
int p = partition(arr, low, high);
// sort before and after the pivot
quickSort(arr, low, p);
quickSort(arr, p + 1, high);
}
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array : ");
System.out.print(Arrays.toString(arr));
}
}
// This code is contributed by Anubhav Singh (singhanubhav)
Python3
# Python implementation QuickSort using # Hoare's partition Scheme. import random ''' The function which implements randomised QuickSort, using Haore's partition scheme. arr :- array to be sorted. start :- starting index of the array. stop :- ending index of the array. ''' def quicksort(arr, start, stop): if(start < stop): # pivotindex is the index where # the pivot lies in the array pivotindex = partitionrand(arr,\ start, stop) # At this stage the array is # partially sorted around the pivot. # separately sorting the left half of # the array and the right # half of the array. quicksort(arr , start , pivotindex) quicksort(arr, pivotindex + 1, stop) # This function generates random pivot, # swaps the first element with the pivot # and calls the partition function. def partitionrand(arr , start, stop): # Generating a random number between # the starting index of the array and # the ending index of the array. randpivot = random.randrange(start, stop) # Swapping the starting element of # the array and the pivot arr[start], arr[randpivot] =\ arr[randpivot], arr[start] return partition(arr, start, stop) ''' This function takes the first element as pivot, places the pivot element at the correct position in the sorted array. All the elements are re-arranged according to the pivot, the elements smaller than the pivot is places on the left and the elements greater than the pivot is placed to the right of pivot. ''' def partition(arr,start,stop): pivot = start # pivot i = start - 1 j = stop + 1 while True: while True: i = i + 1 if arr[i] >= arr[pivot]: break while True: j = j - 1 if arr[j] <= arr[pivot]: break if i >= j: return j arr[i] , arr[j] = arr[j] , arr[i] # Driver Code if __name__ == "__main__": array = [10, 7, 8, 9, 1, 5] quicksort(array, 0, len(array) - 1) print(array) # This code is contributed by soumyasaurav
Producción
Sorted array: 1 5 7 8 9 10
Análisis de ordenación rápida aleatoria
notas
- Usando pivote aleatorio, mejoramos la complejidad de tiempo promedio o esperada a O (N log N). La complejidad del peor de los casos sigue siendo O (N^2).
Publicación traducida automáticamente
Artículo escrito por Sayan Mahapatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA