logo

TechCodeview

QuickSort: tutoriales sobre algoritmos y estructura de datos

Ordenación rápida es un algoritmo de clasificación basado en la Algoritmo divide y vencerás que elige un elemento como pivote y divide la matriz dada alrededor del pivote seleccionado colocando el pivote en su posición correcta en la matriz ordenada.

¿Cómo funciona QuickSort?

El proceso clave en ordenación rápida es un dividir() . El objetivo de las particiones es colocar el pivote (cualquier elemento puede ser elegido como pivote) en su posición correcta en la matriz ordenada y colocar todos los elementos más pequeños a la izquierda del pivote, y todos los elementos mayores a la derecha del pivote. .

La partición se realiza de forma recursiva en cada lado del pivote después de que el pivote se coloca en su posición correcta y esto finalmente ordena la matriz.



Cómo funciona la clasificación rápida

Cómo funciona la clasificación rápida

calcular la tenencia en excel
Práctica recomendada Clasificación rápida ¡Pruébelo!

Elección de pivote:

Hay muchas opciones diferentes para elegir pivotes.

  • Elija siempre el primer elemento como pivote .
  • Elija siempre el último elemento como pivote (implementado a continuación)
  • Elija un elemento aleatorio como pivote .
  • Elija el medio como pivote.

Algoritmo de partición:

La lógica es simple, comenzamos desde el elemento más a la izquierda y realizamos un seguimiento del índice de elementos más pequeños (o iguales) como i . Mientras recorremos, si encontramos un elemento más pequeño, intercambiamos el elemento actual con arr[i]. De lo contrario, ignoramos el elemento actual.

Entendamos el funcionamiento de la partición y el algoritmo de clasificación rápida con la ayuda del siguiente ejemplo:

cadena java con formato

Considere: arr[] = {10, 80, 30, 90, 40}.

  • Compare 10 con el pivote y, como es menor que el pivote, colóquelo de manera correspondiente.

Partición en QuickSort: comparar pivote con 10

  • Compara 80 con el pivote. Es mayor que el pivote.

Partición en QuickSort: comparar pivote con 80

  • Compara 30 con pivote. Es menos que pivote, así que dispóngalo en consecuencia.

Partición en QuickSort: comparar pivote con 30

  • Compare 90 con el pivote. Es mayor que el pivote.

Partición en QuickSort: comparar pivote con 90

  • Coloque el pivote en su posición correcta.

Partición en QuickSort: coloque el pivote en su posición correcta

Ilustración de Quicksort:

A medida que el proceso de partición se realiza de forma recursiva, sigue colocando el pivote en su posición real en la matriz ordenada. Colocar repetidamente los pivotes en su posición real hace que la matriz se ordene.

Siga las imágenes a continuación para comprender cómo la implementación recursiva del algoritmo de partición ayuda a ordenar la matriz.

números abc
  • Partición inicial en la matriz principal:

Quicksort: realizando la partición

  • Partición de los subarreglos:

Quicksort: realizando la partición

Implementación de código de Quick Sort:

C++ 
#include  using namespace std; int partition(int arr[],int low,int high) {  //choose the pivot    int pivot=arr[high];  //Index of smaller element and Indicate  //the right position of pivot found so far  int i=(low-1);    for(int j=low;j<=high-1;j++)  {  //If current element is smaller than the pivot  if(arr[j]
C 
// C program for QuickSort #include  // Utility function to swap tp integers void swap(int* p1, int* p2) {  int temp;  temp = *p1;  *p1 = *p2;  *p2 = temp; } int partition(int arr[], int low, int high) {  // choose the pivot  int pivot = arr[high];  // Index of smaller element and Indicate  // the right position of pivot found so far  int i = (low - 1);  for (int j = low; j <= high - 1; j++) {  // If current element is smaller than the pivot  if (arr[j] < pivot) {  // Increment index of smaller element  i++;  swap(&arr[i], &arr[j]);  }  }  swap(&arr[i + 1], &arr[high]);  return (i + 1); } // The Quicksort function Implement void quickSort(int arr[], int low, int high) {  // when low is less than high  if (low < high) {  // pi is the partition return index of pivot  int pi = partition(arr, low, high);  // Recursion Call  // smaller element than pivot goes left and  // higher element goes right  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  } } int main() {  int arr[] = { 10, 7, 8, 9, 1, 5 };  int n = sizeof(arr) / sizeof(arr[0]);    // Function call  quickSort(arr, 0, n - 1);    // Print the sorted array  printf('Sorted Array
');  for (int i = 0; i < n; i++) {  printf('%d ', arr[i]);  }  return 0; } // This Code is Contributed By Diwakar Jha>
Java 
// Java implementation of QuickSort import java.io.*; class GFG {  // A utility function to swap two elements  static void swap(int[] arr, int i, int j)  {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // This function takes last element as pivot,  // places the pivot element at its correct position  // in sorted array, and places all smaller to left  // of pivot and all greater elements to right of pivot  static int partition(int[] arr, int low, int high)  {  // Choosing the pivot  int pivot = arr[high];  // Index of smaller element and indicates  // the right position of pivot found so far  int i = (low - 1);  for (int j = low; j <= high - 1; j++) {  // If current element is smaller than the pivot  if (arr[j] < pivot) {  // Increment index of smaller element  i++;  swap(arr, i, j);  }  }  swap(arr, i + 1, high);  return (i + 1);  }  // The main function that implements QuickSort  // arr[] -->Matriz a ordenar, // baja --> Índice inicial, // alta --> Índice final 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);  }  }  // To print sorted array  public static void printArr(int[] arr)  {  for (int i = 0; i < arr.length; i++) {  System.out.print(arr[i] + ' ');  }  }  // Driver Code  public static void main(String[] args)  {  int[] arr = { 10, 7, 8, 9, 1, 5 };  int N = arr.length;  // Function call  quickSort(arr, 0, N - 1);  System.out.println('Sorted array:');  printArr(arr);  } } // This code is contributed by Ayush Choudhary // Improved by Ajay Virmoti>
Pitón 
# Python3 implementation of QuickSort # Function to find the partition position def partition(array, low, high): # Choose the rightmost element as pivot pivot = array[high] # Pointer for greater element i = low - 1 # Traverse through all elements # compare each element with pivot for j in range(low, high): if array[j] <= pivot: # If element smaller than pivot is found # swap it with the greater element pointed by i i = i + 1 # Swapping element at i with element at j (array[i], array[j]) = (array[j], array[i]) # Swap the pivot element with # the greater element specified by i (array[i + 1], array[high]) = (array[high], array[i + 1]) # Return the position from where partition is done return i + 1 # Function to perform quicksort def quicksort(array, low, high): if low < high: # Find pivot element such that # element smaller than pivot are on the left # element greater than pivot are on the right pi = partition(array, low, high) # Recursive call on the left of pivot quicksort(array, low, pi - 1) # Recursive call on the right of pivot quicksort(array, pi + 1, high) # Driver code if __name__ == '__main__': array = [10, 7, 8, 9, 1, 5] N = len(array) # Function call quicksort(array, 0, N - 1) print('Sorted array:') for x in array: print(x, end=' ') # This code is contributed by Adnan Aliakbar>
C# 
// C# implementation of QuickSort using System; class GFG {  // A utility function to swap two elements  static void swap(int[] arr, int i, int j)  {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // This function takes last element as pivot,  // places the pivot element at its correct position  // in sorted array, and places all smaller to left  // of pivot and all greater elements to right of pivot  static int partition(int[] arr, int low, int high)  {  // Choosing the pivot  int pivot = arr[high];  // Index of smaller element and indicates  // the right position of pivot found so far  int i = (low - 1);  for (int j = low; j <= high - 1; j++) {  // If current element is smaller than the pivot  if (arr[j] < pivot) {  // Increment index of smaller element  i++;  swap(arr, i, j);  }  }  swap(arr, i + 1, high);  return (i + 1);  }  // The main function that implements QuickSort  // arr[] -->Matriz a ordenar, // baja --> Índice inicial, // alta --> Índice final 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  // and after partition index  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  }  // Driver Code  public static void Main()  {  int[] arr = { 10, 7, 8, 9, 1, 5 };  int N = arr.Length;  // Function call  quickSort(arr, 0, N - 1);  Console.WriteLine('Sorted array:');  for (int i = 0; i < N; i++)  Console.Write(arr[i] + ' ');  } } // This code is contributed by gfgking>
javascript 
// Function to partition the array and return the partition index function partition(arr, low, high) {  // Choosing the pivot  let pivot = arr[high];    // Index of smaller element and indicates the right position of pivot found so far  let i = low - 1;    for (let j = low; j <= high - 1; j++) {  // If current element is smaller than the pivot  if (arr[j] < pivot) {  // Increment index of smaller element  i++;  [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements  }  }    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot to its correct position  return i + 1; // Return the partition index } // The main function that implements QuickSort function quickSort(arr, low, high) {  if (low < high) {  // pi is the partitioning index, arr[pi] is now at the 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);  } } // Driver code let arr = [10, 7, 8, 9, 1, 5]; let N = arr.length; // Function call quickSort(arr, 0, N - 1); console.log('Sorted array:'); console.log(arr.join(' '));>
PHP 
 // code ?>// Esta función toma lugar como último elemento como pivote // Coloca el pivote en la posición correcta // En una matriz ordenada y coloca todos los elementos más pequeños a la izquierda // del pivote y todos los elementos mayores a su derecha de la función de pivote partición(&$arr, $low,$high) { // Elija el elemento pivote $pivot= $arr[$high]; // Índice del elemento más pequeño e indica // La posición correcta del pivote $i=($low-1); por($j=$bajo;$j<=$high-1;$j++) { if($arr[$j]<$pivot) { // Increment index of smaller element $i++; list($arr[$i],$arr[$j])=array($arr[$j],$arr[$i]); } } // Pivot element as correct position list($arr[$i+1],$arr[$high])=array($arr[$high],$arr[$i+1]); return ($i+1); } // The main function that implement as QuickSort // arr[]:- Array to be sorted // low:- Starting Index //high:- Ending Index function quickSort(&$arr,$low,$high) { if($low<$high) { // pi is partition $pi= partition($arr,$low,$high); // Sort the array // Before the partition of Element quickSort($arr,$low,$pi-1); // After the partition Element quickSort($arr,$pi+1,$high); } } // Driver Code $arr= array(10,7,8,9,1,5); $N=count($arr); // Function Call quickSort($arr,0,$N-1); echo 'Sorted Array:
'; for($i=0;$i<$N;$i++) { echo $arr[$i]. ' '; } //This code is contributed by Diwakar Jha>
Producción 
Sorted Array 1 5 7 8 9 10>

Análisis de complejidad de clasificación rápida :

Complejidad del tiempo:

  • Mejor caso : Ω (norte log (norte))
    El mejor de los casos para la ordenación rápida ocurre cuando el pivote elegido en cada paso divide la matriz en mitades aproximadamente iguales.
    En este caso, el algoritmo creará particiones equilibradas, lo que conducirá a una clasificación eficiente.
  • Caso promedio: θ (N log (N))
    El rendimiento promedio de Quicksort suele ser muy bueno en la práctica, lo que lo convierte en uno de los algoritmos de clasificación más rápidos.
  • Peor caso: O(N2)
    El peor de los casos para Quicksort ocurre cuando el pivote en cada paso da como resultado particiones altamente desequilibradas. Cuando el array ya está ordenado y el pivote siempre se elige como el elemento más pequeño o más grande. Para mitigar el peor de los casos, se utilizan varias técnicas, como elegir un buen pivote (por ejemplo, una mediana de tres) y utilizar un algoritmo aleatorio (Randomized Quicksort) para mezclar el elemento antes de ordenarlo.
  • Espacio Auxiliar: O(1), si no consideramos el espacio de pila recursivo. Si consideramos el espacio de pila recursivo, en el peor de los casos, la ordenación rápida podría hacer oh ( norte ).

Ventajas de la clasificación rápida:

  • Es un algoritmo de divide y vencerás que facilita la resolución de problemas.
  • Es eficiente en grandes conjuntos de datos.
  • Tiene una sobrecarga baja, ya que sólo requiere una pequeña cantidad de memoria para funcionar.

Desventajas de la clasificación rápida:

  • Tiene una complejidad temporal en el peor de los casos de O (N2), que ocurre cuando se elige mal el pivote.
  • No es una buena opción para conjuntos de datos pequeños.
  • No es una clasificación estable, lo que significa que si dos elementos tienen la misma clave, su orden relativo no se conservará en la salida ordenada en caso de una clasificación rápida, porque aquí estamos intercambiando elementos según la posición del pivote (sin considerar su orden original). posiciones).