Quicksort: ¿Cuál es el algoritmo de ordenación rápida?

Quicksort es un algoritmo de clasificación fascinante.

• Pertenece a la clase de algoritmos de divide y vencerás.
• Se ordena en su lugar, lo que significa que no requeriría ningún espacio de memoria adicional para completar la clasificación, a diferencia de mergesort, que necesitaría un espacio igual al tamaño de la matriz que desea ordenar.

Alguna terminología
Pivote: dado que es un algoritmo de división y conquista, debe resolver el problema dividiéndolo en subproblemas y agrupando sucesivamente los subproblemas para el resultado final. Pero, ¿cómo divide su problema en subproblemas?

Ahora, viene el papel de pivote. Pivot es el elemento que usaría para dividir / particionar su matriz. Un buen comienzo podría ser seleccionar el primer elemento como pivote siempre. Pero, elegir el pivote es muy importante para que el algoritmo funcione de manera eficiente.

Particionamiento: es el proceso de dividir su matriz original en dos sub-matrices usando el pivote.
Después de particionar una matriz de tamaño de ‘n’, tiene dos subproblemas, de modo que el elemento que utilizó como pivote va a su lugar correcto como lo estaría en una matriz ordenada, y todos los elementos más pequeños que el elemento pivote serían en el lado izquierdo del pivote y todos los demás elementos mayores que el pivote, estarían en el lado derecho del pivote.
Entonces, efectivamente, ahora tendría dos subproblemas, o sub-matrices que necesitan ser ordenados, uno desde el principio a la izquierda del pivote y otro desde el siguiente al pivote hasta el último.

Suficiente lectura, veámoslo con una matriz- [50,45,23,67,88,32,66]. Aunque hemos visto que quicksort no necesita espacio adicional, aquí usaré espacio adicional para darle una idea más clara de la partición. Por lo tanto, mantenemos una matriz vacía de tamaño 7 como nuestra matriz original.
[-, -, -, -, -, -, -]. Ahora elegimos el primer elemento 50 como pivote, comenzamos a atravesar el conjunto y mantenemos los elementos más pequeños que el pivote al extremo izquierdo del conjunto vacío y un elemento más grande al extremo derecho del conjunto.
Entonces, sería como,
[45, -, -, -, -, -, -] [45,23, -, -, -, -, -] [45,23, -, -, -, -, 67] [45,23, -, -, -, 88,67] [45,23,32, -, -, 88,67] [45,23,32, -, 66,88,67].

Vea, la posición para su pivote ahora queda y es esencialmente la posición donde su pivote debería estar en la matriz ordenada. Ahora pondrás tu pivote en esta posición para obtener [45,23,32, 50 , 66,88,67].

Ahora tiene dos subproblemas, uno a la izquierda y otro a la derecha del pivote. Luego puede aplicar sucesivamente el algoritmo primero para la mitad izquierda y luego para la mitad derecha hasta que todo esté ordenado.

La partición en el lugar también se podría hacer. Digamos que el primer elemento fue pivote, luego comienza desde el segundo elemento y escanea la matriz. Inicialice dos punteros ‘i’ y ‘j’ para apuntar al segundo elemento inicialmente. Incremente ‘j’ a medida que avanza al siguiente elemento. Compare el elemento en ‘j’ con el elemento ‘i’, si el elemento ‘j’ es más pequeño, cámbielo por ese en ‘i’. Incremente ‘i’ siempre que ocurra tal intercambio.

Ahora, después de completar el ciclo, intercambie el elemento en (i-1) con el pivote.

Esto es todo.

Quick Sort ofrece una forma rápida y metódica de ordenar listas de entidades. Si se implementa bien, puede ser mucho más rápido que la ordenación por fusión y la ordenación en montón. Este algoritmo de clasificación fue desarrollado en 1959 por Tony Hoare . La ordenación rápida es utilizada internamente por muchos sistemas operativos. En los sistemas Linux, el comando de clasificación bajo el capó no es más que una clasificación rápida .

Quick Sort trabaja en el paradigma de divide y vencerás . Elige un elemento conocido como pivote y asegura que se coloque en su posición correcta en la lista que se está ordenando y luego el proceso se repite con la sublista a la izquierda del pivote y a la derecha del pivote, hasta que la lista esté ordenado El proceso de colocar el elemento pivote en su posición final se llama partición . Puede elegir cualquier elemento como elemento pivote y dividir la matriz en función de él.

La elección del elemento de partición puede afectar en gran medida el rendimiento del algoritmo. Veamos las variaciones de elegir el elemento pivote.

• Elegir el primer elemento como pivote (implementado a continuación).
• Elegir el último elemento como pivote.
• Elegir un elemento aleatorio como pivote.
• Elección del elemento mediano como pivote.

Vamos a entender la explicación gráfica del proceso de partición

Puede ver que todos los elementos a la izquierda de 54 son más pequeños y todos los elementos a la derecha de 54 son más grandes.

Veamos el algoritmo.

1. Elija un elemento, llamado pivote, de la matriz.

2. Partición: reorganice la matriz de manera que todos los elementos con valores menores que el pivote estén antes del pivote, mientras que todos los elementos con valores mayores que el pivote vienen después. El elemento pivote estará en su posición final después de que

3. Aplique recursivamente los pasos anteriores al subconjunto de elementos en el lado izquierdo del pivote y en el lado derecho del pivote.

La clasificación rápida es un algoritmo de clasificación eficiente y rápido . Básicamente se basa en la estrategia de dividir y conquistar, como se usa en el tipo de fusión.

• En la ordenación rápida, la matriz se divide en dos partes y las siguientes partes o submatrices se resuelven recursivamente.
• Todo el concepto gira en torno a un elemento pivote o, en palabras simples, un elemento marcado. El pivote ayuda a dividir la matriz en dos partes, de modo que la primera parte de las dos submatrices contiene elementos más pequeños y la segunda parte contiene elementos más grandes.
• Ahora, este algoritmo utiliza dos funciones importantes denominadas partición y clasificación rápida . El objetivo de las funciones son:

• función de partición : establece el índice apropiado para el pivote de modo que los elementos que le quedan serán más pequeños y el derecho a ellos será más grande. Este es el corazón del algoritmo.
• función de clasificación rápida : divide la matriz en dos partes según la ubicación de pivote obtenida de la función de partición y las llama recursivamente para su clasificación.

Fuente de la imagen: Quick Sort-algoskills

Los conceptos principales se encuentran en encontrar esta ubicación de pivote. Este trabajo lo realiza la función de partición. Comenzamos con dos variables i y j . Fuera de la cual, j inicialmente apunta al primer elemento e i apunta al índice anterior del primer elemento. Comenzamos a comparar un [j] con pivote / último elemento y

• si a [j] <= pivote entonces incremente i e intercambie a [i] con un [j].
• si a [j]> pivote, simplemente aumente j

Debe notarse que j es de p a r-1 , incrementándose en 1 cada vez; donde array es a [p, p + 1 … r] .

fuente de la imagen: Quick Sort-algoskills

CÓDIGO PSEUDO PARA LA FUNCIÓN QUICKSORT

fuente de la imagen: Quick Sort-algoskills

Para una comprensión detallada y códigos y pseudocódigos de ambas funciones , consulte Quick-sort-algoskills

Para más algoritmos, sintonice Algoskills | una plataforma interactiva para algoritmos informáticos

Fuente- algoskills

¡Feliz codificación!

La ordenación rápida es el algoritmo más utilizado para ordenar datos en tiempo nlogn . La clasificación funciona con la selección de pivote. Algoritmo selecciona cualquier pivote aleatorio que reorganizar la matriz de manera que el lado izquierdo del pivote serán todos los elementos más pequeños y el lado derecho serán elementos más grandes, significa que el pivote encuentra su posición final y luego en la posición de la matriz pivote se divide en dos matrices y así sucesivamente. A continuación se muestra la implementación completa y la explicación:
Implementación y análisis de ordenación rápida

La ordenación rápida es rápida, en su lugar, inestable.
En Clasificación rápida, selecciona un elemento aleatorio (Hay diferentes estrategias para seleccionar Pivotar) como Pivote, luego mueve todo el elemento más grande que el pivote a su derecha y menos que el pivote a su izquierda.
Entonces, básicamente, ha colocado el pivote en su posición final en una matriz ordenada. Repite esto hasta que se ordena la matriz

El peor caso es n ^ 2, el caso promedio es n log n

Clasificación rápida: la clasificación rápida es el algoritmo de clasificación interna más rápido sin memoria adicional para clasificar datos.

Complejidad de tiempo de ordenación rápida: La complejidad de tiempo de ordenación rápida es la O (n log n). Para el caso promedio y el peor de los casos, la complejidad del tiempo es O (n2).

Estimado Solo ve el video …

Definitivamente lo entenderás pronto …

En lugar de escribir un montón de texto, recomendaría ver este video