Como sabemos, la ordenación rápida de un solo pivote toma un pivote de uno de los extremos de la array y divide la array, de modo que todos los elementos que quedan en el pivote son menores o iguales que el pivote, y todos los elementos que están a la derecha para el pivote son mayores que el pivote.
La idea de la clasificación rápida de doble pivote es tomar dos pivotes, uno en el extremo izquierdo de la array y el segundo en el extremo derecho de la array. El pivote izquierdo debe ser menor o igual que el pivote derecho, por lo que los intercambiamos si es necesario.
Luego, comenzamos a dividir la array en tres partes: en la primera parte, todos los elementos serán menores que el pivote izquierdo, en la segunda parte todos los elementos serán mayores o iguales que el pivote izquierdo y también serán menores o iguales que el pivote derecho, y en la tercera parte todos los elementos serán mayores que el pivote derecho. Luego, cambiamos los dos pivotes a sus posiciones apropiadas como vemos en la barra de abajo, y luego comenzamos a clasificar rápidamente estas tres partes recursivamente, usando este método.
La clasificación rápida de doble pivote es un poco más rápida que la clasificación rápida original de un solo pivote. Pero aún así, el peor de los casos seguirá siendo O (n ^ 2) cuando la array ya esté ordenada en orden creciente o decreciente.
Un ejemplo:
C++
// C++ program to implement dual pivot QuickSort
#include <iostream>
using namespace std;
int partition(int* arr, int low, int high, int* lp);
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void DualPivotQuickSort(int* arr, int low, int high)
{
if (low < high) {
// lp means left pivot, and rp means right pivot.
int lp, rp;
rp = partition(arr, low, high, &lp);
DualPivotQuickSort(arr, low, lp - 1);
DualPivotQuickSort(arr, lp + 1, rp - 1);
DualPivotQuickSort(arr, rp + 1, high);
}
}
int partition(int* arr, int low, int high, int* lp)
{
if (arr[low] > arr[high])
swap(&arr[low], &arr[high]);
// p is the left pivot, and q is the right pivot.
int j = low + 1;
int g = high - 1, k = low + 1, p = arr[low], q = arr[high];
while (k <= g) {
// if elements are less than the left pivot
if (arr[k] < p) {
swap(&arr[k], &arr[j]);
j++;
}
// if elements are greater than or equal
// to the right pivot
else if (arr[k] >= q) {
while (arr[g] > q && k < g)
g--;
swap(&arr[k], &arr[g]);
g--;
if (arr[k] < p) {
swap(&arr[k], &arr[j]);
j++;
}
}
k++;
}
j--;
g++;
// bring pivots to their appropriate positions.
swap(&arr[low], &arr[j]);
swap(&arr[high], &arr[g]);
// returning the indices of the pivots.
*lp = j; // because we cannot return two elements
// from a function.
return g;
}
// Driver code
int main()
{
int arr[] = { 24, 8, 42, 75, 29, 77, 38, 57 };
DualPivotQuickSort(arr, 0, 7);
cout << "Sorted array: ";
for (int i = 0; i < 8; i++)
cout << arr[i] << " ";
cout << endl;
}
// This code is contributed by SHUBHAMSINGH10
C
// C program to implement dual pivot QuickSort
#include <stdio.h>
int partition(int* arr, int low, int high, int* lp);
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void DualPivotQuickSort(int* arr, int low, int high)
{
if (low < high) {
// lp means left pivot, and rp means right pivot.
int lp, rp;
rp = partition(arr, low, high, &lp);
DualPivotQuickSort(arr, low, lp - 1);
DualPivotQuickSort(arr, lp + 1, rp - 1);
DualPivotQuickSort(arr, rp + 1, high);
}
}
int partition(int* arr, int low, int high, int* lp)
{
if (arr[low] > arr[high])
swap(&arr[low], &arr[high]);
// p is the left pivot, and q is the right pivot.
int j = low + 1;
int g = high - 1, k = low + 1, p = arr[low], q = arr[high];
while (k <= g) {
// if elements are less than the left pivot
if (arr[k] < p) {
swap(&arr[k], &arr[j]);
j++;
}
// if elements are greater than or equal
// to the right pivot
else if (arr[k] >= q) {
while (arr[g] > q && k < g)
g--;
swap(&arr[k], &arr[g]);
g--;
if (arr[k] < p) {
swap(&arr[k], &arr[j]);
j++;
}
}
k++;
}
j--;
g++;
// bring pivots to their appropriate positions.
swap(&arr[low], &arr[j]);
swap(&arr[high], &arr[g]);
// returning the indices of the pivots.
*lp = j; // because we cannot return two elements
// from a function.
return g;
}
// Driver code
int main()
{
int arr[] = { 24, 8, 42, 75, 29, 77, 38, 57 };
DualPivotQuickSort(arr, 0, 7);
printf("Sorted array: ");
for (int i = 0; i < 8; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
Java
// Java program to implement
// dual pivot QuickSort
class GFG{
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void dualPivotQuickSort(int[] arr,
int low, int high)
{
if (low < high)
{
// piv[] stores left pivot and right pivot.
// piv[0] means left pivot and
// piv[1] means right pivot
int[] piv;
piv = partition(arr, low, high);
dualPivotQuickSort(arr, low, piv[0] - 1);
dualPivotQuickSort(arr, piv[0] + 1, piv[1] - 1);
dualPivotQuickSort(arr, piv[1] + 1, high);
}
}
static int[] partition(int[] arr, int low, int high)
{
if (arr[low] > arr[high])
swap(arr, low, high);
// p is the left pivot, and q
// is the right pivot.
int j = low + 1;
int g = high - 1, k = low + 1,
p = arr[low], q = arr[high];
while (k <= g)
{
// If elements are less than the left pivot
if (arr[k] < p)
{
swap(arr, k, j);
j++;
}
// If elements are greater than or equal
// to the right pivot
else if (arr[k] >= q)
{
while (arr[g] > q && k < g)
g--;
swap(arr, k, g);
g--;
if (arr[k] < p)
{
swap(arr, k, j);
j++;
}
}
k++;
}
j--;
g++;
// Bring pivots to their appropriate positions.
swap(arr, low, j);
swap(arr, high, g);
// Returning the indices of the pivots
// because we cannot return two elements
// from a function, we do that using an array.
return new int[] { j, g };
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 24, 8, 42, 75, 29, 77, 38, 57 };
dualPivotQuickSort(arr, 0, 7);
System.out.print("Sorted array: ");
for (int i = 0; i < 8; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
// This code is contributed by Gourish Sadhu
Python3
# Python3 program to implement
# dual pivot QuickSort
def dualPivotQuickSort(arr, low, high):
if low < high:
# lp means left pivot and rp
# means right pivot
lp, rp = partition(arr, low, high)
dualPivotQuickSort(arr, low, lp - 1)
dualPivotQuickSort(arr, lp + 1, rp - 1)
dualPivotQuickSort(arr, rp + 1, high)
def partition(arr, low, high):
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
# p is the left pivot, and q is the right pivot.
j = k = low + 1
g, p, q = high - 1, arr[low], arr[high]
while k <= g:
# If elements are less than the left pivot
if arr[k] < p:
arr[k], arr[j] = arr[j], arr[k]
j += 1
# If elements are greater than or equal
# to the right pivot
else if arr[k] >= q:
while arr[g] > q and k < g:
g -= 1
arr[k], arr[g] = arr[g], arr[k]
g -= 1
if arr[k] < p:
arr[k], arr[j] = arr[j], arr[k]
j += 1
k += 1
j -= 1
g += 1
# Bring pivots to their appropriate positions.
arr[low], arr[j] = arr[j], arr[low]
arr[high], arr[g] = arr[g], arr[high]
# Returning the indices of the pivots
return j, g
# Driver code
arr = [ 24, 8, 42, 75, 29, 77, 38, 57 ]
dualPivotQuickSort(arr, 0, 7)
print('Sorted array: ', end = '')
for i in arr:
print(i, end = ' ')
print()
# This code is contributed by Gourish Sadhu
C#
// C# program to implement
// dual pivot QuickSort
using System;
class GFG {
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void dualPivotQuickSort(int[] arr,
int low, int high)
{
if (low < high)
{
// piv[] stores left pivot and right pivot.
// piv[0] means left pivot and
// piv[1] means right pivot
int[] piv;
piv = partition(arr, low, high);
dualPivotQuickSort(arr, low, piv[0] - 1);
dualPivotQuickSort(arr, piv[0] + 1, piv[1] - 1);
dualPivotQuickSort(arr, piv[1] + 1, high);
}
}
static int[] partition(int[] arr, int low, int high)
{
if (arr[low] > arr[high])
swap(arr, low, high);
// p is the left pivot, and q
// is the right pivot.
int j = low + 1;
int g = high - 1, k = low + 1,
p = arr[low], q = arr[high];
while (k <= g)
{
// If elements are less than the left pivot
if (arr[k] < p)
{
swap(arr, k, j);
j++;
}
// If elements are greater than or equal
// to the right pivot
else if (arr[k] >= q)
{
while (arr[g] > q && k < g)
g--;
swap(arr, k, g);
g--;
if (arr[k] < p)
{
swap(arr, k, j);
j++;
}
}
k++;
}
j--;
g++;
// Bring pivots to their appropriate positions.
swap(arr, low, j);
swap(arr, high, g);
// Returning the indices of the pivots
// because we cannot return two elements
// from a function, we do that using an array.
return new int[] { j, g };
}
// Driver code
public static void Main()
{
int[] arr = { 24, 8, 42, 75, 29, 77, 38, 57 };
dualPivotQuickSort(arr, 0, 7);
Console.Write("Sorted array: ");
for (int i = 0; i < 8; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by Pushpesh Raj
Javascript
<script>
// JavaScript program to implement
// dual pivot QuickSort
function swap(arr,i,j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function dualPivotQuickSort(arr,low,high)
{
if (low < high)
{
// piv[] stores left pivot and right pivot.
// piv[0] means left pivot and
// piv[1] means right pivot
let piv = [];
piv = partition(arr, low, high);
dualPivotQuickSort(arr, low, piv[0] - 1);
dualPivotQuickSort(arr, piv[0] + 1, piv[1] - 1);
dualPivotQuickSort(arr, piv[1] + 1, high);
}
}
function partition(arr,low,high)
{
if (arr[low] > arr[high])
swap(arr, low, high);
// p is the left pivot, and q
// is the right pivot.
let j = low + 1;
let g = high - 1, k = low + 1,
p = arr[low], q = arr[high];
while (k <= g)
{
// If elements are less than the left pivot
if (arr[k] < p)
{
swap(arr, k, j);
j++;
}
// If elements are greater than or equal
// to the right pivot
else if (arr[k] >= q)
{
while (arr[g] > q && k < g)
g--;
swap(arr, k, g);
g--;
if (arr[k] < p)
{
swap(arr, k, j);
j++;
}
}
k++;
}
j--;
g++;
// Bring pivots to their appropriate positions.
swap(arr, low, j);
swap(arr, high, g);
// Returning the indices of the pivots
// because we cannot return two elements
// from a function, we do that using an array.
return [ j, g ];
}
// Driver code
let arr = [ 24, 8, 42, 75, 29, 77, 38, 57 ];
dualPivotQuickSort(arr, 0, 7);
document.write("Sorted array: ");
for (let i = 0; i < 8; i++)
document.write(arr[i] + " ");
document.write("</br>");
// This code is contributed by Shinjan Patra
</script>
Producción:
Sorted array: 8 24 29 38 42 57 75 77
Este artículo es una contribución de Shlomi Elhaiani . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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