En QuickSort , la situación ideal es cuando la mediana siempre se elige como pivote, ya que esto da como resultado un tiempo mínimo. En este artículo, Merge Sort Tree se usa para encontrar la mediana de diferentes rangos en QuickSort y se analiza el número de comparaciones.
Ejemplos:
Input : arr = {4, 3, 5, 1, 2}
Output : 11
Explanation
We have to make 11 comparisons when we
apply quick sort to the array.
Si analizamos detenidamente el algoritmo de ordenación rápida, cada vez que la array se asigna a la función de ordenación rápida, la array siempre consta de una permutación de los números en algún rango de L a R. Inicialmente, es [1 a N], luego es [ 1 para girar – 1] y [girar + 1 para N] y así sucesivamente. Además, no es fácil observar que el orden relativo de los números en todos los arreglos posibles no cambia. Ahora, para obtener el elemento pivote, solo necesitamos obtener el número del medio, es decir, el (r – l + 2)/2º número entre la array.
Para hacer esto eficientemente, podemos usar un árbol de segmentos persistentes , un árbol de Fenwick o un árbol de clasificación por combinación . Este artículo se centra en la implementación del árbol de ordenación de combinación.
En el algoritmo de clasificación rápida modificado, donde elegimos el elemento pivote de la array como la mediana de la array. Ahora, determinar la mediana requiere que encontremos el elemento central considerado, después de ordenar la array, que es en sí misma una operación O(n*log(n)) donde n es el tamaño de la array.
Digamos que tenemos un rango de L a R, entonces la mediana de este rango se calcula como:
Median of A[L; R] = Middle element of sorted(A[L; R])
= (R - L + 1)/2th element of
sorted(A[L; R])
Consideremos que tenemos particiones P durante el algoritmo de ordenación rápida, lo que significa que tenemos que encontrar el pivote ordenando el rango de la array de L a R, donde L y R son los puntos inicial y final de cada partición. Esto es costoso.
Pero tenemos una permutación de números de L a R en cada partición, por lo que podemos encontrar el ceil((R – L + 1)/2) el número más pequeño en este rango, ya que sabemos cuándo habríamos ordenado esta partición. entonces siempre habría sido este elemento el que habría terminado siendo el elemento mediano como resultado también el pivote. Ahora los elementos menores que pivote van al subárbol izquierdo y los mayores que él van al subárbol derecho también manteniendo su orden.
Repetimos este procedimiento para todas las particiones P y encontramos las comparaciones involucradas en cada partición. Dado que en la partición actual todos los elementos de L a R de esa partición se comparan con el pivote, tenemos (R – L + 1) comparaciones en la partición actual. También necesitamos considerar, calculando recursivamente, las comparaciones totales en los subárboles izquierdo y derecho formados también. Así concluimos,
Total Comparisons = Comparisons in Current Partition +
Comparisons in Left partition +
Comparisons in right partition
Discutimos anteriormente el enfoque que se usará para encontrar el elemento pivote de manera eficiente aquí, las estadísticas de
K -ésimo orden que usan el árbol de clasificación de combinación se pueden usar para encontrar lo mismo que se discutió.
CPP
// CPP program to implement number of comparisons
// in modified quick sort
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Constructs a segment tree and stores tree[]
void buildTree(int treeIndex, int l, int r, int arr[],
vector<int> tree[])
{
/* l => start of range,
r => ending of a range
treeIndex => index in the Segment Tree/Merge
Sort Tree */
/* leaf node */
if (l == r) {
tree[treeIndex].push_back(arr[l - 1]);
return;
}
int mid = (l + r) / 2;
/* building left subtree */
buildTree(2 * treeIndex, l, mid, arr, tree);
/* building left subtree */
buildTree(2 * treeIndex + 1, mid + 1, r, arr, tree);
/* merging left and right child in sorted order */
merge(tree[2 * treeIndex].begin(),
tree[2 * treeIndex].end(),
tree[2 * treeIndex + 1].begin(),
tree[2 * treeIndex + 1].end(),
back_inserter(tree[treeIndex]));
}
// Returns the Kth smallest number in query range
int queryRec(int segmentStart, int segmentEnd,
int queryStart, int queryEnd, int treeIndex,
int K, vector<int> tree[])
{
/* segmentStart => start of a Segment,
segmentEnd => ending of a Segment,
queryStart => start of a query range,
queryEnd => ending of a query range,
treeIndex => index in the Segment
Tree/Merge Sort Tree,
K => kth smallest number to find */
if (segmentStart == segmentEnd)
return tree[treeIndex][0];
int mid = (segmentStart + segmentEnd) / 2;
// finds the last index in the segment
// which is <= queryEnd
int last_in_query_range =
(upper_bound(tree[2 * treeIndex].begin(),
tree[2 * treeIndex].end(), queryEnd)
- tree[2 * treeIndex].begin());
// finds the first index in the segment
// which is >= queryStart
int first_in_query_range =
(lower_bound(tree[2 * treeIndex].begin(),
tree[2 * treeIndex].end(), queryStart)
- tree[2 * treeIndex].begin());
int M = last_in_query_range - first_in_query_range;
if (M >= K) {
// Kth smallest is in left subtree,
// so recursively call left subtree for Kth
// smallest number
return queryRec(segmentStart, mid, queryStart,
queryEnd, 2 * treeIndex, K, tree);
}
else {
// Kth smallest is in right subtree,
// so recursively call right subtree for the
// (K-M)th smallest number
return queryRec(mid + 1, segmentEnd, queryStart,
queryEnd, 2 * treeIndex + 1, K - M, tree);
}
}
// A wrapper over query()
int query(int queryStart, int queryEnd, int K, int n, int arr[],
vector<int> tree[])
{
return queryRec(1, n, queryStart, queryEnd,
1, K, tree);
}
/* Calculates total Comparisons Involved in Quick Sort
Has the following parameters:
start => starting index of array
end => ending index of array
n => size of array
tree => Merge Sort Tree */
int quickSortComparisons(int start, int end, int n, int arr[],
vector<int> tree[])
{
/* Base Case */
if (start >= end)
return 0;
// Compute the middle point of range and the pivot
int middlePoint = (end - start + 2) / 2;
int pivot = query(start, end, middlePoint, n, arr, tree);
/* Total Comparisons = (Comparisons in Left part +
Comparisons of right +
Comparisons in parent) */
// count comparisons in parent array
int comparisons_in_parent = (end - start + 1);
// count comparisons involved in left partition
int comparisons_in_left_part =
quickSortComparisons(start, pivot - 1, n, arr, tree);
// count comparisons involved in right partition
int comparisons_in_right_part =
quickSortComparisons(pivot + 1, end, n, arr, tree);
// Return Total Comparisons
return comparisons_in_left_part +
comparisons_in_parent +
comparisons_in_right_part;
}
// Driver code
int main()
{
int arr[] = { 4, 3, 5, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
// Construct segment tree in tree[]
vector<int> tree[MAX];
buildTree(1, 1, n, arr, tree);
cout << "Number of Comparisons = "
<< quickSortComparisons(1, n, n, arr, tree);;
return 0;
}
Producción:
Number of Comparisons = 11
La complejidad es O (log 2 (n)) por consulta para el pivote informático