Primero diré la respuesta qué es la clasificación estable e inestable.
Clasificación estable: clasificación por inserción, clasificación por fusión, clasificación por burbujas.
Ordenación inestable: ordenación de montón, ordenación de selección ordenación de shell, ordenación rápida.
- ¿Qué es un código de clasificación?
- ¿Qué tiene de malo el algoritmo de recomendación de la historia de Quora?
- ¿Cuáles son los errores en el libro Data Structures and Algorithms Made Easy by Narsimha Karumanchi?
- ¿Cuál es la mejor manera de depurar un algoritmo recursivo?
- ¿Qué tan difícil sería para un novato la 'Introducción a los algoritmos' de Thomas H. Cormen?
La clasificación estable son aquellos que mantienen la posición relativa del elemento después de la clasificación, es decir, si tenemos los siguientes elementos 1,9 8,8,9,2,4,5, podemos representar como
a-1, b-9, c-8, d-8, e-9, f-2, g-4, h-5 el orden de clasificación será 1,2,4,5,8,8,9, 9 9
aquí podemos observar que el orden es como a-1, f-2, g-4, h-5, c-8, d-8, b-9, e-9 después de la clasificación de c-8 antes de d- 8, es decir, estamos manteniendo el orden después de ordenar el orden relativo de manera similar en b-9 viene de e-9, por lo que es una clasificación estable.
Ordenar inestable: pero si este es el arreglo después de ordenar
1,2,4,5,8,8,9,9 que puedo escribir a-1, f-2, g-4, h-5, c-8, d-8, e-9, b-9 , que era antes de ordenar, puede ver que e-9 viene antes que d-9, por lo que ambos tienen el mismo valor pero el orden no se mantiene, por lo que dicha ordenación se llama ordenación inestable.
¿Por qué la ordenación rápida es una ordenación inestable?
Tomemos el ejemplo 1,9 8,8,9,2,4,5 ahora tenemos que ordenar usando la ordenación rápida.
primero consideraremos que el elemento fundamental es el último elemento, es decir, 5
pivote = a [fin]
ahora dos índices i = inicio-1; j = inicio, es decir, i = -1 y j = 0 ahora desde la izquierda de la matriz, sigue viendo el elemento si es menor que pivote, es decir, 5 intercambia con el índice de la mayoría del elemento izquierdo por i y finalmente coloca el elemento pivote en la posición donde todo el elemento se fue a pivote es menor que pivote y derecha mayor. Ahora empezar
1,9 8,8,9,2,4,5
1 <5 intercambiando i = 0, j = 1
los siguientes 9,8,8,9 no son menos 5, por lo que no hay intercambio, por lo que j será 4. ahora los siguientes 2 <5, así que no se intercambian
1,2,8,8,9,9,4,5 i = 1 y j = 5, por lo que ahora el 9 que estaba antes se intercambia después de 9, que estaba relativamente detrás del primer 9, tan inestable nuevamente 4 <5, así que intercambia 1,2 , 4,8,9,8,9,8,5
finalmente intercambie el pivote con i = 3 para 1,2,4,5,8,9,8,9.
ahora vea que 8 y 9 se intercambian con los 8,9 posteriores, que ha cambiado el orden relativo.
a-1, b-9, c-8, d-8, e-9, f-2, g-4, h-5
- a- 1, f-2, g-4, h-5, d-8, e-9, c-8, b-9. ahora el orden ha cambiado d-8 y e-9 es anterior a c-8, b-9
