Ordenamiento rápido

1. Algoritmo de ordenamiento rápido
2. Ejemplo de ordenamiento rápido
3. Implementación del algoritmo de ordenamiento rápido
4. Complejidad del algoritmo de ordenamiento rápido

La ordenamiento rápido es un algoritmo de ordenación muy eficiente basado en el principio del algoritmo de dividir y conquistar. La ordenamiento rápido funciona dividiendo el array en dos partes alrededor de un elemento pivote seleccionado. Mueve los elementos más pequeños a la izquierda del pivote y los más grandes a la derecha. Después de esto, las subpartes izquierda y derecha se ordenan recursivamente para ordenar toda la array. Se denomina ordenamiento rápido porque es unas 2 o 3 veces más rápida que los algoritmos de ordenación habituales. La ordenamiento rápido se utiliza ampliamente para la búsqueda de información y los cálculos numéricos dentro de las estructuras de datos.

Algoritmo de ordenamiento rápido

Supongamos que tenemos un array sin ordenar A[] que contiene n elementos. Tomamos dos variables, beg y end, y almacenamos el índice del elemento inicial y final.

Partition()

QuickSort()

Ejemplo de ordenamiento rápido

Supongamos que tenemos el array (6,5,1,4,2,3). Vamos a ordenarlo utilizando el algoritmo de ordenamiento rápido.

Implementación del algoritmo de ordenamiento rápido

#include <bits/stdc++.h>
using namespace std;

int partition(int arr[], int beg, int end) {
  // Select the last element as pivot element
  int pivot = arr[end];
  int i = (beg - 1);
  // Move smaller elements to left side and larger on right side
  for (int j = beg; j < end; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1],
       arr[end]);  // Move pivot element to its right position in array
  return (i + 1);
}

void quickSort(int arr[], int beg, int end) {
  if (beg < end) {
    int pi = partition(arr, beg, end);
    quickSort(arr, beg,
              pi - 1);  // Recursive Sort element on left side of partition
    quickSort(arr, pi + 1,
              end);  // Recursive Sort element on right side of partition
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  quickSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complejidad del algoritmo de ordenamiento rápido

Complejidad temporal

• Caso medio

El tiempo que tarda ordenamiento rápido viene dado por la siguiente relación de recurrencia:

 T(n) = T(k) + T(n-k-1) + θ(n)

k representa aquí el número de elementos menores/mayores que el elemento pivote.

El resultado de esta relación de recurrencia da T(n) = nLogn.El caso medio se produce cuando obtenemos particiones aleatorias desigualmente equilibradas. La complejidad temporal es del orden de [Big Theta]: O(nLogn).

• El peor caso

T(n) = T(n-1) + θ(n)

El peor caso se produce cuando el elemento pivote es siempre el mayor o el menor elemento de la array. En este caso, todos los elementos caen en una subarray y hay que hacer un máximo de n llamadas. La complejidad temporal en el peor de los casos es [Big O]: O(n²).

• El mejor caso

 T(n) = 2T(n/2) + θ(n)

El mejor caso se produce cuando el elemento pivote seleccionado es siempre el elemento central o cuando ambas particiones están equilibradas, es decir, la diferencia de tamaño es de 1 o menos. La complejidad temporal del mejor caso es [Big Omega]: O(nLogn).

Complejidad espacial

La complejidad espacial media del algoritmo de ordenamiento rápido es O(Logn). Es el espacio requerido por la pila de recursión. Pero en el peor de los casos, cuando la ordenación de un array requiere n recursivas, la complejidad espacial es O(n).