Requisito previo: Eliminación de llamada de cola
En QuickSort , la función de partición está en su lugar, pero necesitamos espacio adicional para las llamadas a funciones recursivas. Una implementación simple de QuickSort realiza dos llamadas a sí mismo y, en el peor de los casos, requiere espacio O (n) en la pila de llamadas de funciones.
El peor de los casos ocurre cuando el pivote seleccionado siempre divide la array de manera que una parte tiene 0 elementos y la otra parte tiene n-1 elementos. Por ejemplo, en el siguiente código, si elegimos el último elemento como pivote, obtenemos el peor de los casos para las arrays ordenadas (consulte esto para la visualización)
C
/* A Simple implementation of QuickSort that makes two
two recursive calls. */
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);
}
}
// See below link for complete running code
// http://geeksquiz.com/quick-sort/
Java
// A Simple implementation of QuickSort that
// makes two recursive calls.
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);
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program for the above approach 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) # This code is contributed by sanjoy_62
C#
// A Simple implementation of QuickSort that
// makes two recursive calls.
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);
}
}
// This code is contributed by pratham76.
Javascript
<script>
// A Simple implementation of QuickSort that
// makes two recursive calls.
function quickSort(arr , low , high)
{
if (low < high)
{
// pi is partitioning index, arr[p] is
// now at right place
var pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// This code is contributed by umadevi9616.
</script>
¿Podemos reducir el espacio auxiliar para la pila de llamadas a funciones?
Podemos limitar el espacio auxiliar a O(Log n). La idea se basa en la eliminación de llamadas de cola . Como se vio en la publicación anterior , podemos convertir el código para que haga una llamada recursiva. Por ejemplo, en el siguiente código, hemos convertido el código anterior para usar un bucle while y hemos reducido la cantidad de llamadas recursivas.
C
/* QuickSort after tail call elimination using while loop */
void quickSort(int arr[], int low, int high)
{
while (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);
low = pi+1;
}
}
// See below link for complete running code
// https://ide.geeksforgeeks.org/qrlM31
Java
/* QuickSort after tail call elimination using while loop */
static void quickSort(int arr[], int low, int high)
{
while (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);
low = pi+1;
}
}
// See below link for complete running code
// https://ide.geeksforgeeks.org/qrlM31
// This code is contributed by gauravrajput1
Python3
# QuickSort after tail call elimination using while loop ''' def quickSort(arr, low, high): while (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) low = pi+1 # See below link for complete running code # https:#ide.geeksforgeeks.org/qrlM31 # This code is contributed by gauravrajput1
C#
/* QuickSort after tail call elimination using while loop */
static void quickSort(int []arr, int low, int high)
{
while (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);
low = pi+1;
}
}
// See below link for complete running code
// https://ide.geeksforgeeks.org/qrlM31
// This code contributed by gauravrajput1
Javascript
<script>
/* QuickSort after tail call elimination using while loop */
function quickSort(arr , low , high)
{
while (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
var pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
low = pi+1;
}
}
// See below link for complete running code
// https://ide.geeksforgeeks.org/qrlM31
// This code is contributed by gauravrajput1
</script>
Aunque hemos reducido el número de llamadas recursivas, el código anterior aún puede usar el espacio auxiliar O(n) en el peor de los casos. En el peor de los casos, es posible que la array se divida de manera que la primera parte siempre tenga n-1 elementos. Por ejemplo, esto puede suceder cuando el último elemento se elige como pivote y la array se ordena en orden creciente.
Podemos optimizar el código anterior para hacer una llamada recursiva solo para la parte más pequeña después de la partición. A continuación se muestra la implementación de esta idea.
Optimización adicional:
C++
// C++ program of th above approach
#include <bits/stdc++.h>
using namespace std;
void quickSort(int arr[], int low, int high)
{
while (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// If left part is smaller, then recur for left
// part and handle right part iteratively
if (pi - low < high - pi)
{
quickSort(arr, low, pi - 1);
low = pi + 1;
}
// Else recur for right part
else
{
quickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
// This code is contributed by code_hunt.
C
/* This QuickSort requires O(Log n) auxiliary space in
worst case. */
void quickSort(int arr[], int low, int high)
{
while (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// If left part is smaller, then recur for left
// part and handle right part iteratively
if (pi - low < high - pi)
{
quickSort(arr, low, pi - 1);
low = pi + 1;
}
// Else recur for right part
else
{
quickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
// See below link for complete running code
// https://ide.geeksforgeeks.org/LHxwPk
Java
/* This QuickSort requires O(Log n) auxiliary space in
worst case. */
static void quickSort(int arr[], int low, int high)
{
while (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// If left part is smaller, then recur for left
// part and handle right part iteratively
if (pi - low < high - pi)
{
quickSort(arr, low, pi - 1);
low = pi + 1;
}
// Else recur for right part
else
{
quickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
// See below link for complete running code
// https://ide.geeksforgeeks.org/LHxwPk
// This code is contributed by gauravrajput1
Python3
''' This QuickSort requires O(Log n) auxiliary space in
worst case. '''
def quickSort(arr, low, high)
{
while (low < high):
''' pi is partitioning index, arr[p] is now
at right place '''
pi = partition(arr, low, high);
# If left part is smaller, then recur for left
# part and handle right part iteratively
if (pi - low < high - pi):
quickSort(arr, low, pi - 1);
low = pi + 1;
# Else recur for right part
else:
quickSort(arr, pi + 1, high);
high = pi - 1;
# See below link for complete running code
# https:#ide.geeksforgeeks.org/LHxwPk
# This code is contributed by gauravrajput1
C#
/* This QuickSort requires O(Log n) auxiliary space in
worst case. */
static void quickSort(int []arr, int low, int high)
{
while (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// If left part is smaller, then recur for left
// part and handle right part iteratively
if (pi - low < high - pi)
{
quickSort(arr, low, pi - 1);
low = pi + 1;
}
// Else recur for right part
else
{
quickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
// See below link for complete running code
// https://ide.geeksforgeeks.org/LHxwPk
// This code is contributed by gauravrajput1
Javascript
<script>
/* This QuickSort requires O(Log n) auxiliary space in
worst case. */
function quickSort(arr , low , high)
{
while (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
var pi = partition(arr, low, high);
// If left part is smaller, then recur for left
// part and handle right part iteratively
if (pi - low < high - pi)
{
quickSort(arr, low, pi - 1);
low = pi + 1;
}
// Else recur for right part
else
{
quickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
// See below link for complete running code
// https://ide.geeksforgeeks.org/LHxwPk
// This code contributed by gauravrajput1
</script>
En el código anterior, si la parte izquierda se vuelve más pequeña, hacemos una llamada recursiva para la parte izquierda. De lo contrario para la parte derecha. En el peor de los casos (para el espacio), cuando ambas partes tienen el mismo tamaño en todas las llamadas recursivas, usamos O (Log n) espacio extra.
Referencia:
http://www.cs.nthu.edu.tw/~wkhon/algo08-tutorials/tutorial2b.pdf
Este artículo es una contribución de Dheeraj Jain . 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