Hemos discutido la implementación de QuickSort usando el esquema de partición de Lomuto . El esquema de partición de Lomuto es fácil de implementar en comparación con el esquema de Hoare. Esto tiene un rendimiento inferior al QuickSort de Hoare.
Esquema de partición de Lomuto:
Este algoritmo funciona asumiendo que el elemento pivote es el último elemento. Si se proporciona cualquier otro elemento como elemento pivote, cámbielo primero por el último elemento. Ahora inicialice dos variables i como baja y j también baja, itere sobre la array e incremente i cuando arr[j] <= pivote e intercambie arr[i] con arr[j], de lo contrario incremente solo i. Después de salir del bucle, cambie arr[i] por arr[hi]. Este i almacena el elemento pivote.
partition(arr[], lo, hi)
pivot = arr[hi]
i = lo // place for swapping
for j := lo to hi – 1 do
if arr[j] <= pivot then
i = i + 1
swap arr[i] with arr[j]
swap arr[i] with arr[hi]
return i
Consulte QuickSort para obtener detalles de este esquema de partición.
A continuación se muestran las implementaciones de este enfoque: –
C++
/* C++ implementation QuickSort using Lomuto's partition
Scheme.*/
#include<bits/stdc++.h>
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)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
/* 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(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++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
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 QuickSort
// using Lomuto's partition Scheme
import java.io.*;
class GFG
{
static void Swap(int[] array,
int position1,
int position2)
{
// Swaps elements in an array
// Copy the first position's element
int temp = array[position1];
// Assign to the second element
array[position1] = array[position2];
// Assign to the first element
array[position2] = temp;
}
/* 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)
{
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)
{
i++; // increment index of
// smaller element
Swap(arr, i, j);
}
}
Swap(arr, i + 1, high);
return (i + 1);
}
/* The main function that
implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static 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(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 */
static void printArray(int []arr, int size)
{
int i;
for (i = 0; i < size; i++)
System.out.print(" " + arr[i]);
System.out.println();
}
// Driver Code
static public void main (String[] args)
{
int []arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n-1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
}
// This code is contributed by vt_m.
Python3
''' Python3 implementation QuickSort using Lomuto's partition
Scheme.'''
''' 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 '''
def partition(arr, low, high):
# pivot
pivot = arr[high]
# Index of smaller element
i = (low - 1)
for j in range(low, high):
# If current element is smaller than or
# equal to pivot
if (arr[j] <= pivot):
# increment index of smaller element
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return (i + 1)
''' The main function that implements QuickSort
arr --> Array to be sorted,
low --> Starting index,
high --> Ending index '''
def quickSort(arr, low, high):
if (low < high):
''' pi is partitioning index, arr[p] is now
at right place '''
pi = partition(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 '''
def printArray(arr, size):
for i in range(size):
print(arr[i], end = " ")
print()
# Driver code
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr, 0, n - 1)
print("Sorted array:")
printArray(arr, n)
# This code is contributed by SHUBHAMSINGH10
C#
// C# implementation QuickSort
// using Lomuto's partition Scheme
using System;
class GFG
{
static void Swap(int[] array,
int position1,
int position2)
{
// Swaps elements in an array
// Copy the first position's element
int temp = array[position1];
// Assign to the second element
array[position1] = array[position2];
// Assign to the first element
array[position2] = temp;
}
/* 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)
{
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)
{
i++; // increment index of
// smaller element
Swap(arr, i, j);
}
}
Swap(arr, i + 1, high);
return (i + 1);
}
/* The main function that
implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static 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(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 */
static void printArray(int []arr, int size)
{
int i;
for (i = 0; i < size; 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;
quickSort(arr, 0, n-1);
Console.WriteLine("Sorted array: ");
printArray(arr, n);
}
}
// This code is contributed by vt_m.
Javascript
<script>
// JavaScript implementation QuickSort
// using Lomuto's partition Scheme
function Swap(array, position1, position2)
{
// Swaps elements in an array
// Copy the first position's element
let temp = array[position1];
// Assign to the second element
array[position1] = array[position2];
// Assign to the first element
array[position2] = temp;
}
/* 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 */
function partition(arr, low, high)
{
let pivot = arr[high];
// Index of smaller element
let i = (low - 1);
for (let j = low; j <= high- 1; j++)
{
// If current element is smaller
// than or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of
// smaller element
Swap(arr, i, j);
}
}
Swap(arr, i + 1, high);
return (i + 1);
}
/* The main function that
implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
function quickSort(arr, low, high)
{
if (low < high)
{
/* pi is partitioning index,
arr[p] is now at right place */
let pi = partition(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 */
function printArray(arr, size)
{
let i;
for (i = 0; i < size; i++)
document.write(" " + arr[i]);
document.write("<br/>");
}
// Driver Code
let arr = [10, 7, 8, 9, 1, 5];
let n = arr.length;
quickSort(arr, 0, n-1);
document.write("Sorted array: ");
printArray(arr, n);
// This code is contributed by chinmoy1997pal.
</script>
Producción
Sorted array: 1 5 7 8 9 10
Esquema de partición de Hoare:
El esquema de partición de Hoare funciona mediante la inicialización de dos índices que comienzan en dos extremos, los dos índices se mueven uno hacia el otro hasta que se encuentra una inversión (un valor más pequeño en el lado izquierdo y un valor mayor en el lado derecho). Cuando se encuentra una inversión, se intercambian dos valores y se repite el proceso.
Algoritmo:
partition(arr[], lo, hi)
pivot = arr[lo]
i = lo - 1 // Initialize left index
j = hi + 1 // Initialize right index
// 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--;
while (arr[j] > pivot);
if i >= j then
return j
swap arr[i] with arr[j]
A continuación se muestran las implementaciones de este enfoque: –
C++
/* C++ implementation of QuickSort using Hoare's
partition scheme. */
#include <bits/stdc++.h>
using namespace std;
/* This function takes first element as pivot, and places
all the elements smaller than the pivot on the left side
and all the elements greater than the pivot on
the right side. It returns the index of the last element
on the smaller side*/
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]);
}
}
/* 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(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 QuickSort
// using Hoare's partition scheme
import java.io.*;
class GFG {
/* This function takes first element as pivot, and
places all the elements smaller than the pivot on the
left side and all the elements greater than the pivot
on the right side. It returns the index of the last
element on the smaller side*/
static 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;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// swap(arr[i], arr[j]);
}
}
/* The main function that
implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static 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(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 */
static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
System.out.print(" " + arr[i]);
System.out.println();
}
// Driver Code
static public void main(String[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
}
// This code is contributed by vt_m.
Python3
''' Python implementation of QuickSort using Hoare's
partition scheme. '''
''' This function takes first element as pivot, and places
all the elements smaller than the pivot on the left side
and all the elements greater than the pivot on
the right side. It returns the index of the last element
on the smaller side '''
def partition(arr, low, high):
pivot = arr[low]
i = low - 1
j = high + 1
while (True):
# Find leftmost element greater than
# or equal to pivot
i += 1
while (arr[i] < pivot):
i += 1
# Find rightmost element smaller than
# or equal to pivot
j -= 1
while (arr[j] > pivot):
j -= 1
# If two pointers met.
if (i >= j):
return j
arr[i], arr[j] = arr[j], arr[i]
''' The main function that implements QuickSort
arr --> Array to be sorted,
low --> Starting index,
high --> Ending index '''
def quickSort(arr, low, high):
''' pi is partitioning index, arr[p] is now
at right place '''
if (low < high):
pi = partition(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 '''
def printArray(arr, n):
for i in range(n):
print(arr[i], end=" ")
print()
# Driver code
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr, 0, n - 1)
print("Sorted array:")
printArray(arr, n)
# This code is contributed by shubhamsingh10
C#
// C# implementation of QuickSort
// using Hoare's partition scheme
using System;
class GFG {
/* This function takes first element as pivot, and
places all the elements smaller than the pivot on the
left side and all the elements greater than the pivot
on the right side. It returns the index of the last
element on the smaller side*/
static 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;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// swap(arr[i], arr[j]);
}
}
/* The main function that
implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static 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(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 */
static void printArray(int[] arr, int n)
{
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;
quickSort(arr, 0, n - 1);
Console.WriteLine("Sorted array: ");
printArray(arr, n);
}
}
// This code is contributed by vt_m.
Javascript
<script>
// Javascript implementation of QuickSort
// using Hoare's partition scheme
/* This function takes first element as pivot, and
places all the elements smaller than the pivot on the
left side and all the elements greater than the pivot
on the right side. It returns the index of the last
element on the smaller side*/
function partition(arr, low, high)
{
let pivot = arr[low];
let 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;
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// swap(arr[i], arr[j]);
}
}
/* The main function that
implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
function quickSort(arr, low, high)
{
if (low < high) {
/* pi is partitioning index,
arr[p] is now at right place */
let pi = partition(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 */
function printArray(arr, n)
{
for (let i = 0; i < n; i++)
document.write(" " + arr[i]);
document.write("</br>");
}
let arr = [ 10, 7, 8, 9, 1, 5 ];
let n = arr.length;
quickSort(arr, 0, n - 1);
document.write("Sorted array: " + "</br>");
printArray(arr, n);
</script>
Producción
Sorted array: 1 5 7 8 9 10
Nota: si cambiamos la partición de Hoare para elegir el último elemento como pivote, entonces la partición de Hoare puede hacer que QuickSort entre en una recursividad infinita. Por ejemplo, {10, 5, 6, 20} y el pivote es arr[alto], el índice devuelto siempre será alto y se realizará la llamada a la misma ordenación rápida. Para manejar un pivote aleatorio, siempre podemos intercambiar ese elemento aleatorio con el primer elemento y simplemente seguir el algoritmo anterior.
Comparación:
- El esquema de Hoare es más eficiente que el esquema de partición de Lomuto porque hace tres veces menos intercambios en promedio y crea particiones eficientes incluso cuando todos los valores son iguales.
- Al igual que el esquema de partición de Lomuto, la partición de Hoare también hace que la ordenación rápida se degrade a O(n^2) cuando la array de entrada ya está ordenada, tampoco produce una ordenación estable.
- Tenga en cuenta que en este esquema, la ubicación final del pivote no está necesariamente en el índice que se devolvió, y los siguientes dos segmentos en los que recurre el algoritmo principal son (lo..p) y (p+1..hi) en lugar de (lo..p-1) y (p+1..hi) como en el esquema de Lomuto.
- Tanto la partición de Hoare como la partición de Lomuto son inestables.
| Algoritmo de partición de Hoare | Algoritmo de partición de Lomuto |
|---|---|
| En general, se supone que el primer elemento o elemento es el elemento pivote inicial. Algunos eligen el elemento medio e incluso el último elemento. | Generalmente, un elemento aleatorio de la array se localiza y selecciona y luego se intercambia con el primer o el último elemento para dar valores pivote iniciales. En el algoritmo antes mencionado, el último elemento de la lista se considera como el elemento pivote inicial. |
| Es un algoritmo lineal. | También es un algoritmo lineal. |
| Es relativamente más rápido. | es mas lento |
| Es un poco difícil de entender e implementar. | Es fácil de entender y fácil de implementar. |
| No fija el elemento de pivote en la posición correcta. | Fija el elemento de pivote en la posición correcta. |
Fuente: https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
Este artículo es una contribución de Sahil Chhabra (akku) . 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