algorithm - bubble - selection sort java
Clasificación de inserción vs. Selección (12)
Tipo de selección:
Dada una lista, toma el elemento actual y cámbialo con el elemento más pequeño en el lado derecho del elemento actual.
Tipo de inserción:
Dada una lista, tome el elemento actual e insértelo en la posición adecuada de la lista, ajustando la lista cada vez que inserte. Es similar a organizar las cartas en un juego de cartas.
La ordenación de Complejidad de tiempo de selección siempre es n(n - 1)/2 , mientras que la ordenación de inserción tiene una mejor complejidad de tiempo ya que su complejidad más desfavorable es n(n - 1)/2 . Generalmente tomará comparaciones menores o iguales que n(n - 1)/2 .
Fuente: http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html
Estoy tratando de entender las diferencias entre Insertion Sort y Selection Sort.
Ambos parecen tener dos componentes: una lista desordenada y una lista ordenada. Ambos parecen tomar un elemento de la lista desordenada y ponerlo en la lista ordenada en el lugar correcto. He visto algunos sitios / libros que dicen que el tipo de selección hace esto al intercambiar uno a la vez mientras que el tipo de inserción simplemente encuentra el lugar correcto y lo inserta. Sin embargo, he visto otros artículos decir algo, diciendo que el tipo de inserción también intercambia. En consecuencia, estoy confundido. ¿Hay alguna fuente canónica?
Ambos algoritmos generalmente funcionan así
Paso 1: toma el siguiente elemento sin clasificar de la lista desordenada
Paso 2: colóquelo en el lugar correcto en la lista ordenada.
Uno de los pasos es más fácil para un algoritmo y viceversa.
Clasificación por inserción : tomamos el primer elemento de la lista desordenada, lo colocamos en la lista ordenada, en algún lugar . Sabemos dónde tomar el siguiente elemento (la primera posición en la lista desordenada), pero se necesita algo de trabajo para encontrar dónde colocarlo (en algún lugar ). El paso 1 es fácil.
Clasificación de selección : tomamos el elemento en algún lugar de la lista desordenada, luego lo colocamos en la última posición de la lista ordenada. Necesitamos encontrar el siguiente elemento (lo más probable es que no esté en la primera posición de la lista desordenada, sino más bien, en algún lugar ) y luego ponerlo justo al final de la lista ordenada. El paso 2 es fácil
Básicamente, la ordenación por inserción funciona al comparar dos elementos a la vez y la ordenación por selección selecciona el elemento mínimo de toda la matriz y la ordena.
La ordenación por inserción conceptual sigue ordenando la lista secundaria al comparar dos elementos hasta que se ordena todo el conjunto, mientras que la selección selecciona el elemento mínimo y lo cambia al primer elemento mínimo de la segunda posición a la segunda posición, y así sucesivamente.
La ordenación de inserción se puede mostrar como:
for(i=1;i<n;i++)
for(j=i;j>0;j--)
if(arr[j]<arr[j-1])
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
La clasificación de selección se puede mostrar como:
for(i=0;i<n;i++)
min=i;
for(j=i+1;j<n;j++)
if(arr[j]<arr[min])
min=j;
temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
Clasificación de selección: cuando comienza a compilar la sublista ordenada, el algoritmo garantiza que la sublista ordenada esté siempre completamente ordenada, no solo en términos de sus propios elementos sino también en términos de la matriz completa, es decir, sublista ordenada y no ordenada. Por lo tanto, el nuevo elemento más pequeño encontrado una vez de la sublista no ordenada se agregará al final de la sublista ordenada.
Clasificación de inserción: el algoritmo divide nuevamente la matriz en dos partes, pero aquí el elemento se selecciona de la segunda parte y se inserta en la posición correcta de la primera parte. Esto nunca garantiza que la primera parte esté ordenada en términos de la matriz completa, aunque, por supuesto, en el pase final cada elemento está en su posición ordenada correcta.
En breve,
Clasificación de selección: seleccione el primer elemento de la matriz no ordenada y compárelo con los elementos no ordenados restantes. Es similar al ordenamiento de burbuja, pero en lugar de intercambiar cada elemento más pequeño, mantiene actualizado el índice de elemento más pequeño y lo intercambia al final de cada ciclo .
Clasificación de inserción: es opuesta a la ordenación por selección, en la que selecciona el primer elemento del subarreglo sin clasificar y lo compara con el subarreglo ordenado e inserta el elemento más pequeño donde se encuentra y desplaza todos los elementos ordenados de su derecha al primer elemento sin clasificar.
En pocas palabras, creo que la ordenación por selección busca primero el valor más pequeño en la matriz, y luego realiza el intercambio, mientras que la ordenación por inserción toma un valor y lo compara con cada valor que le queda (detrás de él). Si el valor es menor, se intercambia. Luego, el mismo valor se compara de nuevo y si es más pequeño que el que está detrás, cambia de nuevo. ¡Espero que tenga sentido!
En términos simples, (y probablemente la forma más fácil de lograr un alto nivel de comprensión del problema)
El tipo de burbuja es similar a pararse en una línea e intentar ordenar por altura. Sigues cambiando con la persona que tienes al lado hasta que estás en el lugar correcto. Esto se lleva a cabo desde la izquierda (o derecha dependiendo de la implementación) y sigues cambiando hasta que todo el mundo esté ordenado.
Sin embargo, en la ordenación por selección, lo que estás haciendo es similar a organizar una mano de cartas. Miras las cartas, tomas la más pequeña, la colocas todo el camino hacia la izquierda, y así sucesivamente.
Es posible que la confusión se deba a que está comparando una descripción de clasificar una lista vinculada con una descripción de ordenar una matriz . Pero no puedo estar seguro, ya que no citaron sus fuentes.
La forma más fácil de entender los algoritmos de clasificación es a menudo obtener una descripción detallada del algoritmo (no cosas vagas como "este tipo usa el intercambio. En algún lugar. No estoy diciendo dónde"), obtener algunas cartas (5-10 debería ser suficiente para algoritmos de clasificación simple), y ejecuta el algoritmo a mano.
Clasificación de selección: escanee a través de los datos sin clasificar buscando el elemento restante más pequeño, luego cambie la posición inmediatamente después de los datos ordenados. Repita hasta que termine. Si está ordenando una lista, no necesita cambiar el elemento más pequeño a su posición, en su lugar puede eliminar el nodo de la lista de su posición anterior e insertarlo en el nuevo.
Clasificación de inserción: tome el elemento inmediatamente después de los datos ordenados, escanee los datos ordenados para encontrar el lugar donde colocarlos y colóquelos allí. Repita hasta que termine.
La ordenación de inserción puede usar el intercambio durante su fase de "exploración", pero no tiene que ser así y no es la manera más eficiente a menos que esté ordenando una matriz de un tipo de datos que: (a) no se puede mover, solo copiar o intercambiar; y (b) es más costoso copiar que cambiar. Si la ordenación por inserción sí utiliza swap, la forma en que funciona es que busca simultáneamente el lugar y pone el nuevo elemento allí, intercambiando repetidamente el nuevo elemento con el elemento inmediatamente anterior, siempre que el elemento anterior sea mayor que eso. Una vez que alcanzas un elemento que no es más grande, has encontrado la ubicación correcta y pasas al siguiente elemento nuevo.
La lógica para ambos algoritmos es bastante similar. Ambos tienen una sub-matriz parcialmente ordenada al principio de la matriz. La única diferencia es cómo buscan el siguiente elemento que se colocará en la matriz ordenada.
Tipo de inserción : inserta el siguiente elemento en la posición correcta;
Clasificación de selección : selecciona el elemento más pequeño y lo intercambia con el elemento actual;
Además, Insertion Sort es estable, a diferencia de Selection Sort .
Implementé ambos en Python, y vale la pena señalar lo similares que son:
def insertion(data):
data_size = len(data)
current = 1
while current < data_size:
for i in range(current):
if data[current] < data[i]:
temp = data[i]
data[i] = data[current]
data[current] = temp
current += 1
return data
Con un pequeño cambio, es posible hacer el algoritmo de selección de clases.
def selection(data):
data_size = len(data)
current = 0
while current < data_size:
for i in range(current, data_size):
if data[i] < data[current]:
temp = data[i]
data[i] = data[current]
data[current] = temp
current += 1
return data
Le daré una oportunidad más: considere lo que sucede en el afortunado caso de una matriz casi ordenada.
Durante la clasificación, se puede pensar que el conjunto tiene dos partes: lado izquierdo - clasificado, lado derecho - sin clasificar.
Clasificación de inserción: selecciona el primer elemento sin clasificar e intenta encontrar un lugar para él entre la parte ya clasificada. Dado que busca de derecha a izquierda, es muy posible que el primer elemento ordenado con el que esté comparando (el más grande, más a la derecha en la parte izquierda) sea más pequeño que el elemento elegido, por lo que puede continuar inmediatamente con el siguiente elemento sin clasificar.
Clasificación de selección: elija el primer elemento sin clasificar e intente encontrar el elemento más pequeño de la parte sin clasificar completa, e intercambie los dos si lo desea. El problema es que, como la parte correcta no está ordenada, debes pensar en cada elemento todo el tiempo, ya que no puedes estar seguro de si hay o no un elemento incluso más pequeño que el elegido.
Por cierto, esto es exactamente lo que heapsort mejora con la ordenación por selección: es capaz de encontrar el elemento más pequeño mucho más rápidamente debido al heap .
Tanto la clasificación de inserción como la de selección tienen un bucle externo (sobre cada índice) y un bucle interno (sobre un subconjunto de índices). Cada pasada del bucle interno expande la región clasificada por un elemento, a expensas de la región sin clasificar, hasta que se agote de elementos sin clasificar.
La diferencia está en lo que hace el ciclo interno:
En la ordenación de selección, el bucle interno está sobre los elementos sin clasificar . Cada pasada selecciona un elemento y lo mueve a su ubicación final (en el extremo actual de la región ordenada).
En ordenación por inserción, cada pasada del ciclo interno itera sobre los elementos ordenados . Los elementos ordenados se desplazan hasta que el bucle encuentra el lugar correcto para insertar el siguiente elemento sin clasificar.
Por lo tanto, en una ordenación de selección, los elementos clasificados se encuentran en orden de salida y permanecen allí una vez que se encuentran. Por el contrario, en una clasificación de inserción, los elementos sin clasificar permanecen hasta que se consumen en orden de entrada, mientras que los elementos de la región ordenada se siguen moviendo.
En lo que respecta al intercambio, la ordenación por selección hace un intercambio por pasada del bucle interno. El tipo de inserción generalmente guarda el elemento que se va a insertar como temp antes del bucle interno, dejando espacio para que el bucle interno mueva los elementos ordenados hacia arriba en uno, luego copia la temp al punto de inserción después.
selección -selección de un elemento particular (el más bajo) e intercambio con el elemento i (no de iteración) th. (es decir, primero, segundo, tercero .......) por lo tanto, hacer la lista ordenada en un lado.
inserción - comparando primero con el segundo comparar tercero con el segundo y primero comparar cuarto con el tercero, segundo y primer ......