Contando en sort de Inserción
PHP
Publicado el 7 de Diciembre del 2020 por Kata (76 códigos)
866 visualizaciones desde el 7 de Diciembre del 2020
Una secuencia de números distintos va a ser ordenada utilizando el método de ordenación por inserción.
La ordenación por inserción funciona como sigue:
por ejemplo una ordenación por inserción del vector {20,40,30,10} producirá los siguientes estados para R.
El primer elemento (índice 0) es R={20}
Insertar 40 no requiere movimientos R={20,40}
Insertar el próximo elemento requiere que el 40 se mueva un lugar R={20,30,40}
El 10 debe insertarse en la posicion 0 haciendo que se recorran los elementos siguientes, para obtener finalmente el vector ordenado R={10,20,30,40}
¿ Cuantos elementos se movieron?. Para insertar el 30 movimos el 40 una vez, para insertar el 10 tuvimos que mover el 20, 30 y 40, haciendo un total de 4 movimientos.
Dado un vector de números escribir una línea con el número de movimientos necesarios para ordenar el vector.
La ordenación por inserción funciona como sigue:
1
2
3
4
5
6
7
8
9
10
insertion-sort(A)
inicializar una nueva secuencia vacía R
para cada numero N en A en el orden original hacer: determinar el índice donde i en R debe ser insertado,para que R permanezca ordenado
mueva cada elemento en R con un índice
mayor o igual a i
al índice siguiente para hacer un espacio
ponga R[i]=N
El vector R esta ordenado
por ejemplo una ordenación por inserción del vector {20,40,30,10} producirá los siguientes estados para R.
El primer elemento (índice 0) es R={20}
Insertar 40 no requiere movimientos R={20,40}
Insertar el próximo elemento requiere que el 40 se mueva un lugar R={20,30,40}
El 10 debe insertarse en la posicion 0 haciendo que se recorran los elementos siguientes, para obtener finalmente el vector ordenado R={10,20,30,40}
¿ Cuantos elementos se movieron?. Para insertar el 30 movimos el 40 una vez, para insertar el 10 tuvimos que mover el 20, 30 y 40, haciendo un total de 4 movimientos.
Dado un vector de números escribir una línea con el número de movimientos necesarios para ordenar el vector.
1
2
3
insertSort([20, 40, 30, 10]); // 4
insertSort([-1, 1, 0]); // 1
insertSort([-1000, 0, 1000]); // 0