Saltar al contenido

Cómo poner en práctica la ordenación rápida algoritmo en JavaScriptDec, 31stQuicksort es un algoritmo de ordenación eficiente para los conjuntos de datos más grandes …

marzo 13, 2020

 

ordenación rápida

  • es un algoritmo de ordenación eficiente para los conjuntos de datos más grandes, donde itperforms más rápido que la combinación de clasificación y almacenamiento dinámico de clasificación.
  • Fue desarrollado por un informático británico Tony Hoare en 1959 y se publicó en 1961.

¿Cómo quicksort obras?

matriz tiene 5 artículos [3, 6, 4, de 1, 2]

1). primero tenemos que elegir el valor de pivote de la matriz podemos elegir cualquier cosa como un valor de pivote, pero estamos eligiendo último elemento 2 como pivote.

2). Después, tenemos que recorrer la matriz y la compara con el pivote si cualquier artículo que es menor que el lugar de pivote en el lado de la izquierda más si cualquier artículo es mayor que el lugar de pivote en el lado derecho.

ordenación rápida implementación del algoritmo

vamos a implementar el algoritmo de ordenación rápida en JavaScript.

En primer lugar, estamos creando una función con tres parámetros que son arr, longitud y empezar.

arr : sin clasificar arr ay. longitud

: ¿cuántas veces tenemos que bucle, nuestro valor de pivote es el último elemento de la matriz para que nuestros extremos del bucle antes de que el valor de pivote.

inicio : bucle inicio s desde 0.

function quickSort(arr,length = arr.length-1,start=0){

if(arr.length < 2) return arr const pivot = arr[arr.length-1]; const left = [ ]; const right = [ ]; }

A continuación, estamos usando un bucle while que nos ayuda para recorrer los elementos de la matriz sin clasificar y si cualquier artículo que es menor que el valor de pivote de empuje en el hilera izquierda otra incursión en la matriz de la derecha.

function quickSort(arr,length = arr.length-1,start=0){

if(arr.length < 2) return arr const pivot = arr[arr.length-1]; const left = [ ]; const right = [ ]; while (start < length) { if (arr[start] < pivot) left.push(arr[start]) else right.push(arr[start]) start++ } }

el paso final que necesitamos para ejecutar la ordenación rápida recursiva tanto de la izquierda sideand lado derecho.

function quickSort(arr, length = arr.length - 1, start = 0) {

if (arr.length < 2) return arr // base case const pivot = arr[arr.length - 1]; //pivot value const left = [ ]; const right = [ ]; while (start < length) { if (arr[start] < pivot) left.push(arr[start]) else right.push(arr[start]) start++ } return [...quickSort(left), pivot, ...quickSort(right)]; } console.log(quickSort([4, 9, 2, 6, 8, 10, 3, 1, 7, 5])) //output => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

En el código anterior que utiliza operador de difusión de combinar la parte derecha e izquierda de las matrices.

ordenación rápida Complejidad de tiempo

caso

  • Media - S (nlogn)
  • mejor de los casos - O (nlogn)

Probado utilizando Mocha y chai