Convención de reducción a la mitad
Cuando el número de elementos de una lista es par, dividir la lista a la mitad significa que la primera mitad literal de la lista es la primera mitad y la segunda mitad literal de la lista es la segunda mitad. El elemento medio (medio) de toda la lista, es el último elemento de la primera lista. Esto significa que el índice medio es la longitud / 2 - 1, ya que el recuento del índice comienza desde cero. La longitud es el número de elementos de la lista. Por ejemplo, si el número de elementos es 8, entonces la primera mitad de la lista tiene 4 elementos y la segunda mitad de la lista también tiene 4 elementos. Eso está bien. Dado que el recuento de índices comienza desde 0, el índice medio es 3 = 8/2 - 1.
¿Qué pasa con el caso, cuando el número de elementos en la lista o sublista es impar? Al principio, la longitud todavía se divide por 2. Por convención, el número de elementos en la primera mitad de esta división es longitud / 2 + 1/2. El recuento de índices comienza desde cero. El índice medio viene dado por la longitud / 2 - 1/2. Esto se considera el término medio, por convención. Por ejemplo, si el número de elementos en una lista es 5, entonces el índice medio es 2 = 5/2 - 1/2. Y hay tres elementos en la primera mitad de la lista y dos elementos en la segunda mitad. El elemento intermedio de toda la lista es el tercer elemento en el índice, 2, que es el índice intermedio porque el recuento del índice comienza desde 0.
La división de esta manera es un ejemplo de aritmética de números enteros.
Mediana de tres valores
Pregunta: ¿Cuál es la mediana de la secuencia?
C B A
Solución:
Organizar la lista en orden ascendente:
A B C
El término medio, B, es la mediana. Es la magnitud que se encuentra entre las otras dos magnitudes.
Buscar la mediana en una lista no es de ese tipo. Por ejemplo, en una lista de 19 elementos sin clasificar, es posible que se requiera la mediana del primer elemento, del medio y del último elemento. Estos tres valores pueden no estar en orden ascendente; por tanto, sus índices deben tenerse en cuenta.
Con Quick Sort, se requiere la mediana de la lista completa y las sublistas. El pseudocódigo para buscar la mediana de tres valores espaciados en una lista (matriz) es:
medio:=⌊(bajo+elevado) / 2⌋siarr[medio] <arr[bajo]
cambiar arr[bajo]con arr[medio]
siarr[elevado] <arr[bajo]
cambiar arr[bajo]con arr[elevado]
siarr[medio] <arr[elevado]
cambiar arr[medio]con arr[elevado]
pivote:=arr[elevado]
El término arr significa matriz. Este segmento de código busca la mediana y también realiza alguna clasificación. Este segmento de código parece simple, pero puede resultar bastante confuso. Entonces, preste atención a la siguiente explicación:
La clasificación en este tutorial producirá una lista donde el primer valor es el valor más pequeño y el último valor es el valor más grande. Con el alfabeto, A es menor que Z.
Aquí, el pivote es la mediana resultante. Bajo es el índice más bajo de la lista o sublista (no necesariamente para el valor más bajo); alto es el índice más alto de la lista o sublista (no necesariamente para el valor más alto) y el medio es el índice medio convencional (no necesariamente para el valor medio de toda la lista).
Entonces, la mediana a obtener está entre el valor del índice más bajo, el valor del índice medio y el valor del índice más alto.
En el código, primero se obtiene el índice medio convencional. En este comienzo, la lista no está ordenada. La comparación y alguna reordenación en orden ascendente de los tres valores deben tener lugar al mismo tiempo. La primera sentencia if compara el valor del índice más bajo y el del índice medio. Si el del índice medio es menor que el del índice más bajo, entonces los dos valores intercambian posiciones. Esto comienza a ordenar y cambia la disposición de los valores en la lista o sublista. La segunda sentencia if compara el valor del índice más alto y el del índice más bajo. Si el del índice más alto es menor que el del índice más bajo, los dos valores intercambian posiciones. Esto lleva a ordenar y cambiar la disposición de los valores en la lista o sublista. La tercera sentencia if compara el valor del índice medio y el del índice más alto. Si el del índice más alto es menor que el del medio, los dos valores intercambian posiciones. También puede ocurrir aquí alguna clasificación o reordenamiento. Esta tercera condición if no es como las dos anteriores.
Al final de estos tres intercambios, el valor medio de los tres valores en cuestión sería A [alto], cuyo contenido original podría haber cambiado en el segmento de código. Por ejemplo, considere la secuencia sin clasificar:
C B A
Ya sabemos que la mediana es B. Sin embargo, esto debería demostrarse. El objetivo aquí es obtener la mediana de estos tres valores utilizando el segmento de código anterior. La primera sentencia if compara B y C. Si B es menor que C, entonces las posiciones de B y C deben intercambiarse. B es menor que C, por lo que la nueva disposición se convierte en:
B C A
Observe que los valores para el índice más bajo y el índice medio han cambiado. El segundo enunciado if compara A y B. Si A es menor que B, entonces las posiciones de A y B deben intercambiarse. A es menor que B, por lo que la nueva disposición se convierte en:
A C B
Observe que los valores para el índice más alto y el índice más bajo han cambiado. El tercer enunciado if compara C y B. Si C es menor que B, entonces las posiciones de C y B deben intercambiarse. C no es menor que B, por lo que no se produce ningún intercambio. El nuevo arreglo permanece como el anterior, es decir:
A C B
B es la mediana, que es, A [alto], y es el pivote. Entonces, el pivote nace al final de la lista o sublista.
La función de intercambio
Otra característica que necesita Quick Sort es la función de intercambio. La función de intercambio, intercambia los valores de dos variables. El pseudocódigo para la función de intercambio es:
definir intercambio(x,y)temperatura:=x
x:=y
y:=temperatura
Aquí, xey se refieren a los valores reales y no a las copias.
La clasificación en este artículo producirá una lista donde el primer valor es el valor más pequeño y el último valor es el valor más grande.
Contenido del artículo
- Algoritmo de clasificación rápida
- Un pseudocódigo de partición
- Ilustración de clasificación rápida
- Codificación Java
- Conclusión
Algoritmo de clasificación rápida
La forma normal de ordenar una lista no ordenada es considerar los dos primeros valores. Si no están en orden, póngalos en orden. A continuación, considere los primeros tres valores. Escanee los dos primeros para ver dónde encaja el tercer valor y ajústelo adecuadamente. Luego, considere los primeros cuatro valores. Escanee los primeros tres valores para ver dónde encaja el cuarto valor y ajústelo apropiadamente. Continúe con este procedimiento hasta que se ordene toda la lista.
Este procedimiento, también conocido como el tipo de fuerza bruta, en el lenguaje de la programación de computadoras, es demasiado lento. El algoritmo de clasificación rápida viene con un procedimiento mucho más rápido.
Los pasos para el algoritmo de ordenación rápida son los siguientes:
- Asegúrese de que haya al menos 2 números para ordenar en la lista sin clasificar.
- Obtenga un valor central estimado para la lista, llamado pivote. La mediana, como se describió anteriormente, es una forma de obtener el pivote. Las diferentes formas tienen sus ventajas y desventajas. - Te veo despues.
- Divida la lista. Esto significa que coloque el pivote en la lista. De esta forma, todos los elementos de la izquierda son menores que el valor de pivote y todos los elementos de la derecha son mayores o iguales que el valor de pivote. Hay diferentes formas de particionar. Cada método de partición tiene sus ventajas y desventajas. Particionar es dividir en el paradigma de divide y vencerás.
- Repita los pasos 1, 2 y 3 de forma recursiva para los nuevos pares de sublistas que surgen hasta que se ordene la lista completa. Esto es conquistar en el paradigma de divide y vencerás.
El pseudocódigo de clasificación rápida es:
algoritmo de clasificación rápida(arr,bajo,elevado)essibajo<alto entonces
pivote(bajo,elevado)
pag:=dividir(arr,bajo,elevado)
ordenación rápida(arr,bajo,pag- 1)
ordenación rápida(arr,pag+ 1,elevado)
Un pseudocódigo de partición
El pseudocódigo de partición utilizado en este tutorial es:
partición de algoritmo(arr,bajo,elevado)espivote:=arr[elevado]
I:=bajo
j:=elevado
hacer
hacer
++I
tiempo(arr[I] <pivote)
hacer
--j
tiempo(arr[j] >pivote)
si (I<j)
cambiar arr[I]con arr[j]
tiempo(I<j)
cambiar arr[I]con arr[elevado]
regresoI
En la ilustración de Clasificación rápida a continuación, se utiliza este código:
Ilustración de clasificación rápida
Considere la siguiente lista (matriz) sin clasificar de letras alfabéticas:
Q W E R T Y U I O P
Por inspección, la lista ordenada es:
E I O P Q R T U W Y
La lista ordenada ahora se probará, utilizando el algoritmo anterior y los segmentos de pseudocódigo, de la lista no ordenada:
Q W E R T Y U I O P
El primer pivote se determina a partir de arr [0] = Q, arr [4] = T y arr [9] = P, y se identifica como Q y se coloca en el extremo derecho de la lista. Entonces, la lista con cualquier clasificación de función pivote se convierte en:
P W E R T Y U I O Q
El pivote actual es Q. El procedimiento de pivote hizo una pequeña clasificación y colocó P en la primera posición. La lista resultante tiene que ser reorganizada (dividida), de modo que, todos los elementos de la izquierda sean de menor valor, entonces el pivote y todos los elementos de la derecha del pivote sean iguales o mayores que el pivote. La computadora no puede realizar particiones mediante inspección. Entonces, lo hace usando los índices y el algoritmo de partición anterior.
Los índices bajo y alto ahora son 0 y 9. Entonces, la computadora comenzará escaneando desde el índice 0 hasta llegar a un índice, cuyo valor es igual o mayor que el pivote y se detiene allí temporalmente. También escaneará desde el extremo superior (derecho), índice 9, bajando, hasta que alcance un índice cuyo valor sea menor o igual que el pivote y se detenga allí temporalmente. Esto significa dos posiciones de parada. Si i, la variable de índice incremental, de baja aún no es igual o mayor que la variable de índice decreciente, j de alta, entonces estos dos valores se intercambian. En la situación actual, el escaneo desde ambos extremos se detuvo en W y O. Entonces la lista se convierte en:
P O E R T Y U I W Q
El pivote sigue siendo Q. La exploración en direcciones opuestas continúa y se detiene en consecuencia. Si i aún no es igual o mayor que j, entonces se intercambian los dos valores en los que se detuvo el escaneo desde ambos extremos. Esta vez, el escaneo desde ambos extremos se detuvo en R e I. Entonces, la disposición de la lista se convierte en:
P O E I T Y U R W Q
El pivote sigue siendo Q. La exploración en direcciones opuestas continúa y se detiene en consecuencia. Si i aún no es igual o mayor que j, se intercambian los dos valores en los que se detuvo el escaneo. Esta vez, el escaneo desde ambos extremos se detuvo en T para i e I para j. Yo y yo nos hemos encontrado o cruzado. Entonces, no puede haber intercambio. La lista sigue siendo la misma que:
P O E I T Y U R W Q
En este punto, el pivote, Q, debe colocarse en su posición final en la clasificación. Esto se hace intercambiando arr [i] con arr [high], intercambiando T y Q. La lista se convierte en:
P O E I Q Y U R W T
En este punto, la partición de toda la lista ha finalizado. El pivote = Q ha jugado su papel. Ahora hay tres sublistas, que son:
P O E I Q Y U R W T
La partición es división y conquista (clasificación) en el paradigma. Q está en su posición de clasificación correcta. Cada elemento a la izquierda de Q es más pequeño que Q, y cada elemento a la derecha de Q es más grande que Q. Sin embargo, la lista de la izquierda todavía no está ordenada; y la lista de la derecha todavía no está ordenada. Toda la función de clasificación rápida debe llamarse de forma recursiva para ordenar la sublista izquierda y la sublista derecha. Este retiro de Quick Sort debe continuar; Se desarrollarán nuevas sublistas hasta que toda la lista original esté completamente ordenada. Para cada recuperación de la función de clasificación rápida, se atiende primero a la sublista izquierda antes de que se atienda a la sublista derecha correspondiente. Se debe obtener un nuevo pivote para cada sublista.
Para la sublista:
P O E I
Se determina el pivote (mediana) para P, O e I. El pivote sería O. Para esta sublista, y en relación con la lista completa, el nuevo arr [bajo] es arr [0], y el nuevo arr [alto] es el último arr [i-1] = arr [ 4-1] = arr [3], donde i es el índice de pivote final de la partición anterior. Después de que se haya llamado a la función pivot (), el nuevo valor pivote, pivot = O. No confunda entre la función pivote y el valor pivote. La función pivote puede realizar una pequeña ordenación y colocar el pivote en el extremo derecho de la sublista. Esta sublista se convierte en,
I P E O
Con este esquema, el pivote siempre termina en el extremo derecho de la sublista o lista después de su llamada a la función. El escaneo desde ambos extremos comienza desde arr [0] y arr [3] hasta que iyj se encuentran o se cruzan. La comparación se realiza con pivot = O.Las primeras paradas están en P y E. Se intercambian y la nueva sublista se convierte en:
I E P O
El escaneo desde ambos extremos continúa y las nuevas paradas están en P para i y en E para j. Ahora yo y yo nos hemos encontrado o nos hemos cruzado. Entonces la sublista sigue siendo la misma que:
I E P O
La partición de una sublista o lista finaliza cuando el pivote se ha colocado en su posición final. Entonces, los nuevos valores para arr [i] y arr [high] se intercambian. Es decir, P y O se intercambian. La nueva sublista se convierte en:
I E O P
O está ahora en su posición final para toda la lista. Su papel de pivote ha terminado. Actualmente, la sublista está dividida en tres listas más, que son:
I E O P
En este punto, se debe llamar a Quick Sort de la primera sublista de la derecha. Sin embargo, no se llamará. En su lugar, se anotará y se reservará, para ser llamado más tarde. A medida que se estaban ejecutando las instrucciones de la función de partición, desde la parte superior de la función, es la clasificación rápida de la sublista izquierda la que debe llamarse ahora (después de que se haya llamado a pivot ()). Se llamará para la lista:
ES DECIR
Comenzará buscando la mediana de I y E. Aquí, arr [bajo] = I, arr [medio] = I y arr [alto] = E. Entonces, la mediana, pivote, debe ser determinada por el algoritmo pivote como , I. Sin embargo, el pseudocódigo de pivote anterior determinará el pivote como E. Este error se produce aquí porque el pseudocódigo anterior está destinado a tres elementos y no a dos. En la implementación a continuación, hay algunos ajustes en el código. La sublista se convierte en,
E yo
El pivote siempre termina en el extremo derecho de la sublista o lista después de su llamada a la función. El escaneo desde ambos extremos comienza desde arr [0] y arr [1] exclusivo hasta que iyj se encuentran o se cruzan. La comparación se realiza con pivote = I. Las primeras y únicas paradas están en I y E: en I para i y en E para j. Ahora yo y yo nos hemos encontrado o cruzado. Entonces, la sublista sigue siendo la misma que:
E yo
La partición de una sublista o lista finaliza cuando el pivote se ha colocado en su posición final. Entonces, los nuevos valores para arr [i] y arr [high] se intercambian. Aquí sucede que arr [i] = I y arr [alto] = I. Entonces, el mismo valor se intercambia consigo mismo. La nueva sublista se convierte en:
E yo
Ahora estoy en su posición final para toda la lista. Su papel de pivote ha terminado. La sublista ahora está dividida en dos listas más, que son,
E yo
Ahora, los pivotes hasta ahora han sido Q, O e I. Los pivotes terminan en sus posiciones finales. Una sublista de un solo elemento, como la P anterior, también termina en su posición final.
En este punto, la primera sublista izquierda se ha ordenado por completo. Y el procedimiento de clasificación está ahora en:
E I O P Q Y U R W T
La primera sublista de la derecha:
Y U R W T
todavía necesita ser ordenado.
Conquistando la sublista de la primera derecha
Recuerde que la llamada de clasificación rápida para la primera sublista derecha se anotó y se reservó en lugar de ejecutarse. En este punto, se ejecutará. Y así, el nuevo arr [bajo] = arr [5] = arr [QPivotIndex + 1], y el nuevo arr [alto] permanece arr [9]. Un conjunto similar de actividades que sucedió para la primera sublista izquierda sucederá aquí. Y esta primera sublista de la derecha está ordenada por:
R T U W Y
Y la lista original sin clasificar se ha ordenado a:
E I O P Q R T U W Y
Codificación Java
Poner el algoritmo en Java es simplemente poner todos los segmentos de pseudocódigo anteriores en métodos Java en una clase. No olvide que debe haber un método main () en la clase que llamará a la función quicksort () con la matriz sin clasificar.
El método pivot ()
El método Java pivot () que devuelve el valor, pivot, debería ser:
vacíopivote(carbonizarsearr[], En tbajo, En televado) {En tmedio= (bajo+elevado) / 2;
si (arr[medio] <arr[bajo])
intercambio(arr,bajo,medio);
si (arr[elevado] <arr[bajo])
intercambio(arr,bajo,elevado);
si ((elevado-bajo) > 2) {
si (arr[medio] <arr[elevado])
intercambio(arr,medio,elevado);
}
}
El método swap ()
El método swap () debería ser:
vacíointercambio(carbonizarsearr[], En tx, En ty) {carbonizarsetemperatura=arr[x];
arr[x] =arr[y];
arr[y] =temperatura;
}
El método quicksort ()
El método quicksort () debería ser:
vacíoordenación rápida(carbonizarsearr[], En tbajo, En televado) {si (bajo<elevado) {
pivote(arr,bajo,elevado);
En tpag=dividir(arr,bajo,elevado);
ordenación rápida(arr,bajo,pag- 1);
ordenación rápida(arr,pag+ 1,elevado);
}
}
El método de la partición ()
El método de partición () debe ser:
En tdividir(carbonizarsearr[], En tbajo, En televado) {carbonizarsepivote=arr[elevado];
En tI=bajo;
En tj=elevado;
hacer {
hacer
++I;
tiempo(arr[I] <pivote);
hacer
--j;
tiempo(arr[j] >pivote);
si (I<j)
intercambio(arr,I,j);
}tiempo(I<j);
intercambio(arr,I,elevado);
regresoI;
}
El método main ()
El método main () puede ser:
públicoestático vacíoprincipal(Cuerda[]argumentos) {carbonizarsearr[] = {'Q', 'EN', 'Y', 'R', 'T', 'Y', 'U', 'I', 'O', 'PAG'};
TheClass QuickSort= nuevoLa clase();
Ordenación rápida.ordenación rápida(arr, 0, 9);
Sistema.fuera.println('Los elementos ordenados:');
por(En tI=0;I<10;I++) {
Sistema.fuera.impresión(arr[I]);Sistema.fuera.impresión(' ');
}
Sistema.fuera.println();
}
Todos los métodos anteriores se pueden poner en una clase.
Conclusión
Quick Sort es un algoritmo de clasificación que utiliza el paradigma divide y vencerás. Comienza dividiendo una lista sin clasificar en dos o tres sublistas. En este tutorial, Quick Sort ha dividido una lista en tres sublistas: una sublista izquierda, una lista intermedia de un solo elemento y una sublista derecha. Conquistar en Clasificación rápida es dividir una lista o sublista mientras la ordena, utilizando un valor de pivote. Este tutorial ha explicado una implementación de Quick Sort en el lenguaje informático Java.
Sobre el Autor
Chrysanthus Forcha
Descubridor de la integración matemática de First Principles y series relacionadas. Maestría en Educación Técnica, especialidad en Electrónica y Software de Computación. BSc Electronics. También tengo conocimientos y experiencia a nivel de Maestría en Computación y Telecomunicaciones. De 20.000 escritores, fui el 37º mejor escritor en devarticles.com. Trabajo en estos campos desde hace más de 10 años.
Ver todas las publicacionesPUBLICACIONES DE CONSEJOS DE LINUX RELACIONADOS
- Comparación de cadenas en Java
- Cómo usar HashMap en Java
- Explicación de la clasificación rápida en Java
- Traversal de preorden de árbol binario en Java
- Fusionar Ordenar en Java Explicado
- Cómo utilizar Scanner en Java
- Java escribir en archivo