Copiado al portapapeles
Descripción
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:
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.
Entrada
Los datos de entrada consisten de múltiples casos de prueba. Cada caso de prueba es un vector con 1 <= n <= 50 números, que están en una línea, separados por un espacio. La entrada termina cuando no hay mas datos.
Salida
Por cada caso de prueba escriba una línea con la cantidad de movimientos necesarios para ordenar el vector utilizando en método descrito.
Ayuda
crear un vector y realiza insercion sort, de esto por cada movimiento al insertar debera ser contado