Unidad 8 Proyecto opcional: Ordenar, Página 3

Ordenar por partición

Otra clasificación de uso común se denomina ordenación por partición. Así es cómo funciona:

Paso 1. En una lista desordenada, selecciona el primer elemento de la lista (que probablemente no sea el elemento que debería aparecer primero después de ordenar). Este elemento se denomina pivote.
Un elemento está "con el pivote" solo si tiene el mismo valor que el pivote.
Paso 2. Para cada elemento de la lista, decide si viene antes del pivote, con el pivote, o después del pivote.
Paso 3. Divide los datos en tres categorías: elementos antes del pivote, con el pivote, después del pivote. Las listas antes y después del pivote no están ordenadas.
Paso 4. Si hay elementos antes del pivote, usa una ordenación de partición para ordenarlos. Si hay elementos después del pivote, usa una ordenación de partición para ordenarlos.
Paso 5. La lista ordenada se crea anexando las tres listas que resultan.

Los nombres no se ordenan al colocarlos antes o después de un pivote. Para lista{Emma, Olivia, Sophia, Isabella, Ava, Mia, Emily, Abigail}

, este es el estado después de la primera división utilizando el pivote: el pivote es Emma, la lista antes del pivote es {Ava, Abigail} y la lista después del pivote es {Olivia, Sophia, Isabella, Mia, Emily}. Luego, el proceso de clasificación continúa en estas dos listas desordenadas más pequeñas.

Explora la ordenación de partición antes de escribir cualquier código. Con tu clase, ponte de pie y forma una fila. Luego, sigue el proceso de ordenación de partición para ordenar a todos, de menor a mayor, por el número de la dirección de su casa.
¿Cómo es la ordenación de partición un ejemplo de recursividad? ¿Cuál es el caso base?

Para escribir un bloque de ordenar por partición en Snap!, necesitarás código para un caso base y código que siga los pasos de la ordenación por partición.

Deberás descubrir cómo colocar los elementos en las tres categorías y cómo crear una lista final para la salida.
Crea el reportero recursivo ordenar por partición. Su salida, para cualquier lista, debe ser la misma que la salida para ordenar por selección.

Revelar un ejemplo.

Por ejemplo, supongamos que ayer tenía una gran lista ordenada y hoy agrega algunos elementos nuevos, por lo que necesita volver a ordenar la lista. Un algoritmo de ordenamiento de propósito general no aprovechará el carácter que esté casi en orden de su entrada. Pero la ordenación por inserción, un algoritmo que es lento en general, maneja este caso especial rápidamente.

¿Por qué hay diferentes algoritmos de ordenamiento? Algunos algoritmos de ordenación tardan más en ejecutarse que otros, pero incluso un algoritmo que es lento en general puede ser útil en casos especiales.

Aquí también puedes utilizar una lista larga de nombres.
Crea una lista de 500 elementos de números aleatorios y luego ordénala usando los tres algoritmos de ordenación que creaste en esta práctica de laboratorio. Toma nota del tiempo:
¿Qué algoritmo fue el más rápido? ¿Por qué podría este tipo de algoritmo funcionar más rápido?