Ordenamiento rápido

Harshit Jindal 12 octubre 2023
  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
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()

  • Selecciona el último elemento (puede ser cualquiera dependiendo de la implementación) como elemento pivote.
  • Inicializa el valor del puntero i a beg - 1 para que podamos mover los elementos más pequeños que el pivote al inicio del array.
  • Recorrer iterativamente el array y hacer lo siguiente para cada elemento.
  • Si el elemento A[i] < pivot incrementa i e intercambia A[i] con A[j].
  • Intercambia A[i] con A[end] para poner el elemento pivote en su posición correcta.
  • Retorna el índice del elemento pivote.

QuickSort()

  • Selecciona el índice del pivote pi.
  • Particionar el array alrededor del índice pivote.
  • Ordena recursivamente los elementos del lado izquierdo arr[beg,...,pi] del elemento pivote.
  • Ordena recursivamente los elementos del lado derecho arr[pi+1,...,end] del elemento pivote.

algoritmo de ordenamiento rápido

resultado del algoritmo de ordenamiento rápido

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.

  • Primero se selecciona 3 como elemento pivote, el array se divide en dos subpartes (1,2) - elementos más pequeños, y (6,5,4) - elementos más grandes. Y luego 3 se coloca en su posición ordenada. Las dos submatrices formadas se ordenan entonces recursivamente.
  • Para la subarray (1,2), se selecciona 2 como elemento pivote y se coloca en la posición correcta y se forma la subarray (1) que ya está ordenada.
  • Para la subarray (6,5,4), se pone 4 en la posición correcta, y se forma la subarray (6,5), que luego se ordena recursivamente.
  • Para la subarray (6,5), se selecciona 5 como pivote y se pone en la posición correcta, lo que da (6) como nueva subarray. La subarray de un solo elemento (6) ya está ordenada.
  • Finalmente, obtenemos el array ordenado como (1, 2, 3, 4, 5, 6).

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(n2).

  • 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).

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Artículo relacionado - Sort Algorithm