Código de PHP - Contando en sort de Inserción

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)
513 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 2020gráfica de visualizaciones de la versión: 1
514 visualizaciones desde el 7 de Diciembre del 2020
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function insertSort($a) {
    // definimos un nuevo array vacio
    $r=[];
    $movimientos=0;
 
    // bucle por cada elemento del array
    foreach ($a as $n) {
        for ($i=0; $i<count($r); $i++) {
            if ($n<$r[$i]) {
                // Si el valor es mas pequeño salimos del bucle.
                // "$i" tendra el valor de la posición donde añadir
                // el nuevo elemento.
                break;
            }
        }
 
        // añadimos un nuevo elemento al final del nuevo array
        array_push($r, "");
 
        // Recorremos el nuevo array empezando por el final hasta
        // ls posicion "$i".
        // "$j" contendra la posición donde añadir el nuevo valor
        for ($j=count($r)-1; $j>$i; $j--) {
 
            // Movemos cada elemento a una posición mayor
            $r[$j]=$r[$j-1];
 
            // Contamos los movimientos que hacemos
            $movimientos++;
        }
 
        // añadimos el nuevo valor
        $r[$j]=$n;
    }
    return $movimientos;
}



Comentarios sobre la versión: 1 (0)


No hay comentarios
 

Comentar la versión: 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad

http://lwp-l.com/s6757