Quicksort pivote

Question

Ordenar la siguiente matriz de un usando quicksort,

[6, 11, 4, 9, 8, 2, 5, 8, 13, 7] 

El pivote debe ser elegido como la media aritmética de la primera y el último elemento, es decir, (a[0] + a[size - 1])/2 (rounded down).

mostrar todos los pasos importantes, tales como la separación y las llamadas recursivas al algoritmo.

---

Entiendo cómo ordenar la matriz usando quicksort, sin embargo, no estoy seguro de cómo calcular el pivote.

es el pivote calcula 6 + 7 = 13 entonces 13/2 = 6.5 (redondeado hacia abajo es 6) por lo que el pivote es 2 (es decir, el sexto elemento)?

Sé que los elementos que no sean de pivote aparecen en el lado izquierdo, y los elementos superiores al pivote aparecen en el lado derecho, y la partición repite este paso de clasificar el subconjunto.

Cualquier ayuda sería muy apreciada.

Answer 1

Para quicksort, el pivote puede ser el elemento que desee. Consulte Wikipedia.

El problema se resolvió fácilmente eligiendo ya sea un índice de azarpara el pivote, la elección de la índice medio de la partición o (especialmente para las particiones más largos) la elección de la mediana de la primera, media y última elemento de la partición para el pivote

Tres opciones así:

• Fi elemento de primera
• elemento de Medio
• mediana de la primera, media y última.

Y en ti caso utilizando la media de primero y último elemento valor le daría:

6 + 7 = 13 
13/2 = 6.5 
6.5 rounded down = 6 

Answer 2

Por cierto, la cuestión está redactada, el pivote debe ser sólo 6 y no necesariamente el sexto elemento de la matriz.

Esto es definitivamente el caso, porque si solo hubiera 3 elementos en la matriz, por ejemplo, y la media aritmética fuera mayor que 3, no tendría pivote para elegir porque no hay ningún elemento con esa índice.

Nota: Tenga cuidado con la forma de los elementos de índice en la matriz. Usted dijo que el 6 ° elemento es '2', cuando puede ser '5' si su lenguaje de programación comienza con índices 0.

Answer 3

Su pivote es 6. Su pivote NO es el 6 ° elemento Ahora puede aplicar el siguiente algoritmo .

function quicksort(array) 
var list less, greater 
if length(array) ≤ 1 
    return array // an array of zero or one elements is already sorted 
select and remove a pivot value pivot from array 
for each x in array 
    if x ≤ pivot then append x to less 
    else append x to greater 
return concatenate(quicksort(less), pivot, quicksort(greater)) 

Answer 4

La posición del pivote de dicho cálculo no es importante, la clasificación rápida ordena los elementos en función de si son más o menos que el pivote. Luego, el pivote se coloca entre los dos conjuntos (más y menos).