En el algoritmo QuickSort simple , seleccionamos un elemento como pivote, dividimos la array alrededor de un pivote y recurrimos a los subarreglos a la izquierda y derecha del pivote.
Considere una array que tiene muchos elementos redundantes. Por ejemplo, {1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 4, 4, 4}. Si se elige 4 como pivote en la Ordenación rápida simple, arreglamos solo un 4 y procesamos recursivamente las ocurrencias restantes.
La idea de la clasificación rápida de 3 vías es procesar todas las ocurrencias del pivote y se basa en el algoritmo de la bandera nacional holandesa.
In 3 Way QuickSort, an array arr[l..r] is divided in 3 parts: a) arr[l..i] elements less than pivot. b) arr[i+1..j-1] elements equal to pivot. c) arr[j..r] elements greater than pivot.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program for 3-way quick sort
#include <bits/stdc++.h>
using namespace std;
/* This function partitions a[] in three parts
a) a[l..i] contains all elements smaller than pivot
b) a[i+1..j-1] contains all occurrences of pivot
c) a[j..r] contains all elements greater than pivot */
void partition(int a[], int l, int r, int& i, int& j)
{
i = l - 1, j = r;
int p = l - 1, q = r;
int v = a[r];
while (true) {
// From left, find the first element greater than
// or equal to v. This loop will definitely
// terminate as v is last element
while (a[++i] < v)
;
// From right, find the first element smaller than
// or equal to v
while (v < a[--j])
if (j == l)
break;
// If i and j cross, then we are done
if (i >= j)
break;
// Swap, so that smaller goes on left greater goes
// on right
swap(a[i], a[j]);
// Move all same left occurrence of pivot to
// beginning of array and keep count using p
if (a[i] == v) {
p++;
swap(a[p], a[i]);
}
// Move all same right occurrence of pivot to end of
// array and keep count using q
if (a[j] == v) {
q--;
swap(a[j], a[q]);
}
}
// Move pivot element to its correct index
swap(a[i], a[r]);
// Move all left same occurrences from beginning
// to adjacent to arr[i]
j = i - 1;
for (int k = l; k < p; k++, j--)
swap(a[k], a[j]);
// Move all right same occurrences from end
// to adjacent to arr[i]
i = i + 1;
for (int k = r - 1; k > q; k--, i++)
swap(a[i], a[k]);
}
// 3-way partition based quick sort
void quicksort(int a[], int l, int r)
{
if (r <= l)
return;
int i, j;
// Note that i and j are passed as reference
partition(a, l, r, i, j);
// Recur
quicksort(a, l, j);
quicksort(a, i, r);
}
// A utility function to print an array
void printarr(int a[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
}
// Driver code
int main()
{
int a[] = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 };
int size = sizeof(a) / sizeof(int);
// Function Call
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
return 0;
}
Java
// Java program for 3-way quick sort
import java.util.*;
class GFG
{
static int i, j;
/* This function partitions a[] in three parts
a) a[l..i] contains all elements smaller than pivot
b) a[i+1..j-1] contains all occurrences of pivot
c) a[j..r] contains all elements greater than pivot */
static void partition(int a[], int l, int r)
{
i = l - 1; j = r;
int p = l - 1, q = r;
int v = a[r];
while (true)
{
// From left, find the first element greater than
// or equal to v. This loop will definitely
// terminate as v is last element
while (a[++i] < v)
;
// From right, find the first element smaller than
// or equal to v
while (v < a[--j])
if (j == l)
break;
// If i and j cross, then we are done
if (i >= j)
break;
// Swap, so that smaller goes on left greater goes
// on right
int temp = a[i];
a[i] = a[j];
a[j] = temp;
// Move all same left occurrence of pivot to
// beginning of array and keep count using p
if (a[i] == v) {
p++;
temp = a[i];
a[i] = a[p];
a[p] = temp;
}
// Move all same right occurrence of pivot to end of
// array and keep count using q
if (a[j] == v) {
q--;
temp = a[q];
a[q] = a[j];
a[j] = temp;
}
}
// Move pivot element to its correct index
int temp = a[i];
a[i] = a[r];
a[r] = temp;
// Move all left same occurrences from beginning
// to adjacent to arr[i]
j = i - 1;
for (int k = l; k < p; k++, j--)
{
temp = a[k];
a[k] = a[j];
a[j] = temp;
}
// Move all right same occurrences from end
// to adjacent to arr[i]
i = i + 1;
for (int k = r - 1; k > q; k--, i++)
{
temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
// 3-way partition based quick sort
static void quicksort(int a[], int l, int r)
{
if (r <= l)
return;
i = 0; j = 0;
// Note that i and j are passed as reference
partition(a, l, r);
// Recur
quicksort(a, l, j);
quicksort(a, i, r);
}
// A utility function to print an array
static void printarr(int a[], int n)
{
for (int i = 0; i < n; ++i)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
// Driver code
public static void main(String[] args)
{
int a[] = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 };
int size = a.length;
// Function Call
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
}
}
// This code is contributed by Rajput-Ji
Python3
''' This function partitions a[] in three parts a) a[first..start] contains all elements smaller than pivot b) a[start+1..mid-1] contains all occurrences of pivot c) a[mid..last] contains all elements greater than pivot ''' def partition(arr, first, last, start, mid): pivot = arr[last] end = last # Iterate while mid is not greater than end. while (mid[0] <= end): # Inter Change position of element at the starting if it's value is less than pivot. if (arr[mid[0]] < pivot): arr[mid[0]], arr[start[0]] = arr[start[0]], arr[mid[0]] mid[0] = mid[0] + 1 start[0] = start[0] + 1 # Inter Change position of element at the end if it's value is greater than pivot. elif (arr[mid[0]] > pivot): arr[mid[0]], arr[end] = arr[end], arr[mid[0]] end = end - 1 else: mid[0] = mid[0] + 1 # Function to sort the array elements in 3 cases def quicksort(arr,first,last): # First case when an array contain only 1 element if (first >= last): return # Second case when an array contain only 2 elements if (last == first + 1): if (arr[first] > arr[last]): arr[first], arr[last] = arr[last], arr[first] return # Third case when an array contain more than 2 elements start = [first] mid = [first] # Function to partition the array. partition(arr, first, last, start, mid) # Recursively sort sublist containing elements that are less than the pivot. quicksort(arr, first, start[0] - 1) # Recursively sort sublist containing elements that are more than the pivot quicksort(arr, mid[0], last) # Code Start from here arr = [4,9,4,4,1,9,4,4,9,4,4,1,4] # Call the quicksort function. quicksort(arr,0,len(arr) - 1) # print arr after sorting the elements print(arr)
C#
// C# program for 3-way quick sort
using System;
class GFG {
// A function which is used to swap values
static void swap<T>(ref T lhs, ref T rhs)
{
T temp;
temp = lhs;
lhs = rhs;
rhs = temp;
}
/* This function partitions a[] in three parts
a) a[l..i] contains all elements smaller than pivot
b) a[i+1..j-1] contains all occurrences of pivot
c) a[j..r] contains all elements greater than pivot
*/
public static void partition(int[] a, int l, int r,
ref int i, ref int j)
{
i = l - 1;
j = r;
int p = l - 1, q = r;
int v = a[r];
while (true) {
// From left, find the first element greater
// than or equal to v. This loop will definitely
// terminate as v is last element
while (a[++i] < v)
;
// From right, find the first element smaller
// than or equal to v
while (v < a[--j])
if (j == l)
break;
// If i and j cross, then we are done
if (i >= j)
break;
// Swap, so that smaller goes on left greater
// goes on right
swap(ref a[i], ref a[j]);
// Move all same left occurrence of pivot to
// beginning of array and keep count using p
if (a[i] == v) {
p++;
swap(ref a[p], ref a[i]);
}
// Move all same right occurrence of pivot to
// end of array and keep count using q
if (a[j] == v) {
q--;
swap(ref a[j], ref a[q]);
}
}
// Move pivot element to its correct index
swap(ref a[i], ref a[r]);
// Move all left same occurrences from beginning
// to adjacent to arr[i]
j = i - 1;
for (int k = l; k < p; k++, j--)
swap(ref a[k], ref a[j]);
// Move all right same occurrences from end
// to adjacent to arr[i]
i = i + 1;
for (int k = r - 1; k > q; k--, i++)
swap(ref a[i], ref a[k]);
}
// 3-way partition based quick sort
public static void quicksort(int[] a, int l, int r)
{
if (r <= l)
return;
int i = 0, j = 0;
// Note that i and j are passed as reference
partition(a, l, r, ref i, ref j);
// Recur
quicksort(a, l, j);
quicksort(a, i, r);
}
// A utility function to print an array
public static void printarr(int[] a, int n)
{
for (int i = 0; i < n; ++i)
Console.Write(a[i] + " ");
Console.Write("\n");
}
// Driver code
static void Main()
{
int[] a = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 };
int size = a.Length;
// Function Call
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
}
// This code is contributed by DrRoot_
}
Javascript
<script>
// javascript program for 3-way quick sort
var i, j;
/*
* This function partitions a in three parts a) a[l..i] contains all elements
* smaller than pivot b) a[i+1..j-1] contains all occurrences of pivot c)
* a[j..r] contains all elements greater than pivot
*/
function partition(a , l , r) {
i = l - 1;
j = r;
var p = l - 1, q = r;
var v = a[r];
while (true) {
// From left, find the first element greater than
// or equal to v. This loop will definitely
// terminate as v is last element
while (a[++i] < v)
;
// From right, find the first element smaller than
// or equal to v
while (v < a[--j])
if (j == l)
break;
// If i and j cross, then we are done
if (i >= j)
break;
// Swap, so that smaller goes on left greater goes
// on right
var temp = a[i];
a[i] = a[j];
a[j] = temp;
// Move all same left occurrence of pivot to
// beginning of array and keep count using p
if (a[i] == v) {
p++;
temp = a[i];
a[i] = a[p];
a[p] = temp;
}
// Move all same right occurrence of pivot to end of
// array and keep count using q
if (a[j] == v) {
q--;
temp = a[q];
a[q] = a[j];
a[j] = temp;
}
}
// Move pivot element to its correct index
var temp = a[i];
a[i] = a[r];
a[r] = temp;
// Move all left same occurrences from beginning
// to adjacent to arr[i]
j = i - 1;
for (k = l; k < p; k++, j--) {
temp = a[k];
a[k] = a[j];
a[j] = temp;
}
// Move all right same occurrences from end
// to adjacent to arr[i]
i = i + 1;
for (k = r - 1; k > q; k--, i++) {
temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
// 3-way partition based quick sort
function quicksort(a , l , r) {
if (r <= l)
return;
i = 0;
j = 0;
// Note that i and j are passed as reference
partition(a, l, r);
// Recur
quicksort(a, l, j);
quicksort(a, i, r);
}
// A utility function to print an array
function printarr(a , n) {
for (i = 0; i < n; ++i)
document.write(" "+ a[i]);
document.write("<br/>");
}
// Driver code
var a = [ 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 ];
var size = a.length;
// Function Call
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
// This code contributed by aashish1995
</script>
Producción
4 9 4 4 1 9 4 4 9 4 4 1 4 1 1 4 4 4 4 4 4 4 4 9 9 9
Complejidad del tiempo : O(N * log(N))
Donde ‘N’ es el número de elementos en la array/lista dada
El número promedio de llamadas recursivas realizadas a la función de clasificación rápida es log N, y cada vez que se llama a la función, estamos atravesando la array/lista dada que requiere tiempo O (N). Por tanto, la complejidad temporal total es O(N * log (N)).
Complejidad espacial: O (log N)
donde ‘N’ es el número de elementos en la array/lista dada.
Gracias a Utkarsh por sugerir la implementación anterior.
Otra implementación utilizando el algoritmo de la bandera nacional holandesa
C++
// C++ program for 3-way quick sort
#include <bits/stdc++.h>
using namespace std;
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// A utility function to print an array
void printarr(int a[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
}
/* This function partitions a[] in three parts
a) a[l..i] contains all elements smaller than pivot
b) a[i+1..j-1] contains all occurrences of pivot
c) a[j..r] contains all elements greater than pivot */
// It uses Dutch National Flag Algorithm
void partition(int a[], int low, int high, int& i, int& j)
{
// To handle 2 elements
if (high - low <= 1) {
if (a[high] < a[low])
swap(&a[high], &a[low]);
i = low;
j = high;
return;
}
int mid = low;
int pivot = a[high];
while (mid <= high) {
if (a[mid] < pivot)
swap(&a[low++], &a[mid++]);
else if (a[mid] == pivot)
mid++;
else if (a[mid] > pivot)
swap(&a[mid], &a[high--]);
}
// update i and j
i = low - 1;
j = mid; // or high+1
}
// 3-way partition based quick sort
void quicksort(int a[], int low, int high)
{
if (low >= high) // 1 or 0 elements
return;
int i, j;
// Note that i and j are passed as reference
partition(a, low, high, i, j);
// Recur two halves
quicksort(a, low, i);
quicksort(a, j, high);
}
// Driver Code
int main()
{
int a[] = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 };
// int a[] = {4, 39, 54, 14, 31, 89, 44, 34, 59, 64, 64,
// 11, 41}; int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// int a[] = {91, 82, 73, 64, 55, 46, 37, 28, 19, 10};
// int a[] = {4, 9, 4, 4, 9, 1, 1, 1};
int size = sizeof(a) / sizeof(int);
// Function Call
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
return 0;
}
Java
// Java program for 3-way quick sort
import java.util.*;
class GFG
{
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// A utility function to print an array
static void printarr(int a[], int n)
{
for (int i = 0; i < n; ++i)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
/* This function partitions a[] in three parts
a) a[l..i] contains all elements smaller than pivot
b) a[i+1..j-1] contains all occurrences of pivot
c) a[j..r] contains all elements greater than pivot */
// It uses Dutch National Flag Algorithm
static void partition(int a[], int low, int high, int i, int j)
{
// To handle 2 elements
if (high - low <= 1) {
if (a[high] < a[low])
swap(a, high, low);
i = low;
j = high;
return;
}
int mid = low;
int pivot = a[high];
while (mid <= high) {
if (a[mid] < pivot)
swap(a, low++, mid++);
else if (a[mid] == pivot)
mid++;
else if (a[mid] > pivot)
swap(a, mid, high--);
}
// update i and j
i = low - 1;
j = mid; // or high+1
}
// 3-way partition based quick sort
static void quicksort(int a[], int low, int high)
{
if (low >= high) // 1 or 0 elements
return;
int i=low, j=high;
// Note that i and j are passed
partition(a, low, high, i, j);
// Recur two halves
quicksort(a, low, i);
quicksort(a, j, high);
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 };
// int a[] = {4, 39, 54, 14, 31, 89, 44, 34, 59, 64, 64,
// 11, 41}; int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// int a[] = {91, 82, 73, 64, 55, 46, 37, 28, 19, 10};
// int a[] = {4, 9, 4, 4, 9, 1, 1, 1};
int size = a.length;
// Function Call
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
}
}
// This code is contributed by Pushpesh Raj.
Python3
# python3 program for 3-way quick sort
# Function to find lexicographically minimum
def swap(a,i,j) :
temp = a[i]
a[i] = a[j]
a[j] = temp
# A utility function to print an array
def printarr(a, n) :
for i in range (n) :
print(a[i],end=' ')
print("\n")
''' This function partitions a[] in three parts
a) a[l..i] contains all elements smaller than pivot
b) a[i+1..j-1] contains all occurrences of pivot
c) a[j..r] contains all elements greater than pivot '''
# It uses Dutch National Flag Algorithm
def partition(a, low, high, i, j) :
# To handle 2 elements
if high - low <= 1 :
if a[high] < a[low] :
swap(a,high, low)
i = low
j = high
return
mid = low; pivot = a[high];
while mid <= high :
if a[mid] < pivot :
swap(a,low,mid)
low+=1
mid+=1
elif a[mid] == pivot :
mid+=1
elif a[mid] > pivot :
swap(a,mid,high)
high-=1
# update i and j
i = low - 1
j = mid # or high+1
# 3-way partition based quick sort
def quickSort(a,low,high) :
if low >= high : # 1 or 0 elements
return
i = low; j = high;
# Note that i and j are passed as reference
partition(a,low,high,i,j)
# Recur two halves
quickSort(a,low,i)
quickSort(a,j,high)
# Driver code
if __name__ == "__main__" :
a = [4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4]
size = len(a)
printarr(a,size)
quickSort(a,0,size-1)
printarr(a,size)
#this code is contributed by aditya942003patil
C#
// C# program for 3-way quick sort
using System;
class GFG {
// A function which is used to swap values
static void swap<T>(ref T lhs, ref T rhs)
{
T temp;
temp = lhs;
lhs = rhs;
rhs = temp;
}
// A utility function to print an array
public static void printarr(int[] a, int n)
{
for (int i = 0; i < n; ++i)
Console.Write(a[i] + " ");
Console.Write("\n");
}
/* This function partitions a[] in three parts
a) a[l..i] contains all elements smaller than pivot
b) a[i+1..j-1] contains all occurrences of pivot
c) a[j..r] contains all elements greater than pivot */
// It uses Dutch National Flag Algorithm
public static void partition(int[] a, int low, int high,
ref int i, ref int j)
{
// To handle 2 elements
if (high - low <= 1) {
if (a[high] < a[low])
swap(ref a[high], ref a[low]);
i = low;
j = high;
return;
}
int mid = low;
int pivot = a[high];
while (mid <= high) {
if (a[mid] < pivot)
swap(ref a[low++], ref a[mid++]);
else if (a[mid] == pivot)
mid++;
else if (a[mid] > pivot)
swap(ref a[mid], ref a[high--]);
}
// update i and j
i = low - 1;
j = mid; // or high+1
}
// 3-way partition based quick sort
public static void quicksort(int[] a, int low, int high)
{
if (low >= high) // 1 or 0 elements
return;
int i = 0, j = 0;
// Note that i and j are passed as reference
partition(a, low, high, ref i, ref j);
// Recur two halves
quicksort(a, low, i);
quicksort(a, j, high);
}
// Driver code
static void Main()
{
int[] a = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 };
// int[] a = {4, 39, 54, 14, 31, 89, 44, 34, 59, 64,
// 64, 11, 41}; int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9,
// 10}; int[] a = {91, 82, 73, 64, 55, 46, 37, 28,
// 19, 10}; int[] a = {4, 9, 4, 4, 9, 1, 1, 1};
int size = a.Length;
// Function Call
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
}
// This code is contributed by DrRoot_
}
Javascript
<script>
// Javascript program for 3-way quick sort
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// A utility function to print an array
function printarr(a, n) {
for (let i = 0; i < n; ++i)
document.write(a[i]);
document.write("<br>");
}
/* This function partitions a[] in three parts
a) a[l..i] contains all elements smaller than pivot
b) a[i+1..j-1] contains all occurrences of pivot
c) a[j..r] contains all elements greater than pivot */
// It uses Dutch National Flag Algorithm
function partition(a, low, high, i, j) {
// To handle 2 elements
if (high - low <= 1) {
if (a[high] < a[low])
swap(a, high, low);
i = low;
j = high;
return;
}
let mid = low;
let pivot = a[high];
while (mid <= high) {
if (a[mid] < pivot)
swap(a, low++, mid++);
else if (a[mid] == pivot)
mid++;
else if (a[mid] > pivot)
swap(a, mid, high--);
}
// update i and j
i = low - 1;
j = mid; // or high+1
}
// 3-way partition based quick sort
function quicksort(a, low, high) {
if (low >= high) // 1 or 0 elements
return;
let i = low, j = high;
// Note that i and j are passed
partition(a, low, high, i, j);
// Recur two halves
quicksort(a, low, i);
quicksort(a, j, high);
}
// Driver Code
let a = [4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4];
// let a[] = {4, 39, 54, 14, 31, 89, 44, 34, 59, 64, 64,
// 11, 41}; let a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// let a[] = {91, 82, 73, 64, 55, 46, 37, 28, 19, 10};
// let a[] = {4, 9, 4, 4, 9, 1, 1, 1};
let size = a.length;
// Function Call
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
// This code is contributed by gfgking
</script>
Producción
4 9 4 4 1 9 4 4 9 4 4 1 4 1 1 4 4 4 4 4 4 4 4 9 9 9
Gracias Aditya Goel por esta implementación.
Referencia:
http://algs4.cs.princeton.edu/lectures/23DemoPartitioning.pdf
http://www.sorting-algorithms.com/quick-sort-3-way
Escriba comentarios si encuentra algo incorrecto o si desea para 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