Estadísticas de la versión: 1 - Contando en sort de Inserción - PHP

Imágen de perfil
Val: 716
Bronce
Ha aumentado 1 puesto en PHP (en relación al último mes)
Gráfica de PHP

Contando en sort de Insercióngráfica de visualizaciones


PHP

Publicado el 7 de Diciembre del 2020 por Kata (76 códigos)
522 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:

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

1

Publicado el 7 de Diciembre del 2020
522 visualizaciones desde el 7 de Diciembre del 2020

34 visualizaciones durante los últimos 90 días


5
0