Ordenación por inserción

def insercion(a):
    """Ordena a por inserción y devuelve cuántos elementos ha tenido que desplazar."""
    desplazamientos = 0
    for i in range(1, len(a)):
        x = a[i]                                # el que se va a insertar
        j = i - 1
        while j >= 0 and a[j] > x:              # los mayores que x se corren una posición
            a[j + 1] = a[j]
            j -= 1
            desplazamientos += 1
        a[j + 1] = x                            # el hueco que queda es su sitio
    return desplazamientos


casi = [1, 2, 4, 3, 5, 6, 8, 7]
reves = [8, 7, 6, 5, 4, 3, 2, 1]
print(f"Casi ordenado: {insercion(casi)} desplazamientos → {casi}")
print(f"Al revés: {insercion(reves)} desplazamientos → {reves}")

/** Ordena a por inserción y devuelve cuántos elementos ha tenido que desplazar. */
function insercion(a) {
    let desplazamientos = 0;
    for (let i = 1; i < a.length; i++) {
        const x = a[i];                       // el que se va a insertar
        let j = i - 1;
        while (j >= 0 && a[j] > x) {          // los mayores que x se corren una posición
            a[j + 1] = a[j];
            j--;
            desplazamientos++;
        }
        a[j + 1] = x;                         // el hueco que queda es su sitio
    }
    return desplazamientos;
}

const casi = [1, 2, 4, 3, 5, 6, 8, 7];
const reves = [8, 7, 6, 5, 4, 3, 2, 1];
console.log(`Casi ordenado: ${insercion(casi)} desplazamientos → [${casi.join(", ")}]`);
console.log(`Al revés: ${insercion(reves)} desplazamientos → [${reves.join(", ")}]`);

using System;

class Program {
    // Ordena a por inserción y devuelve cuántos elementos ha tenido que desplazar.
    static int Insercion(int[] a) {
        int desplazamientos = 0;
        for (int i = 1; i < a.Length; i++) {
            int x = a[i];                         // el que se va a insertar
            int j = i - 1;
            while (j >= 0 && a[j] > x) {          // los mayores que x se corren una posición
                a[j + 1] = a[j];
                j--;
                desplazamientos++;
            }
            a[j + 1] = x;                         // el hueco que queda es su sitio
        }
        return desplazamientos;
    }

    static void Main() {
        int[] casi = { 1, 2, 4, 3, 5, 6, 8, 7 };
        int[] reves = { 8, 7, 6, 5, 4, 3, 2, 1 };
        Console.WriteLine(
quot;Casi ordenado: {Insercion(casi)} desplazamientos → [{string.Join(", ", casi)}]");
        Console.WriteLine(
quot;Al revés: {Insercion(reves)} desplazamientos → [{string.Join(", ", reves)}]");
    }
}

<?php
/** Ordena $a por inserción y devuelve cuántos elementos ha tenido que desplazar. */
function insercion(array &$a): int {
    $desplazamientos = 0;
    for ($i = 1; $i < count($a); $i++) {
        $x = $a[$i];                          // el que se va a insertar
        $j = $i - 1;
        while ($j >= 0 && $a[$j] > $x) {      // los mayores que $x se corren una posición
            $a[$j + 1] = $a[$j];
            $j--;
            $desplazamientos++;
        }
        $a[$j + 1] = $x;                      // el hueco que queda es su sitio
    }
    return $desplazamientos;
}

$casi = [1, 2, 4, 3, 5, 6, 8, 7];
$reves = [8, 7, 6, 5, 4, 3, 2, 1];
$d = insercion($casi);
echo "Casi ordenado: $d desplazamientos → [" . implode(", ", $casi) . "]\n";
$d = insercion($reves);
echo "Al revés: $d desplazamientos → [" . implode(", ", $reves) . "]\n";

import bisect


def insertar_ordenado(l, x):
    """Inserta x en la lista ordenada l sin desordenarla: un solo paso de la inserción."""
    pos = bisect.bisect_right(l, x)   # dónde va (después de los iguales: estable)
    l.insert(pos, x)                  # insert desplaza los de la derecha

# bisect.insort(l, x) hace las dos cosas a la vez

/** Inserta x en el array ordenado a sin desordenarlo: un solo paso de la inserción. */
function insertarOrdenado(a, x) {
    let pos = a.length;
    while (pos > 0 && a[pos - 1] > x) pos--;     // dónde va, buscando desde el final
    a.splice(pos, 0, x);                         // splice desplaza los de la derecha
}

// Inserta x en la lista ordenada l sin desordenarla: un solo paso de la inserción.
static void InsertarOrdenado(List<int> l, int x) {
    int pos = l.BinarySearch(x);
    if (pos < 0) pos = ~pos;              // no estaba: ~pos es dónde iría
    l.Insert(pos, x);                     // Insert desplaza los de la derecha
}

/** Inserta $x en el array ordenado $a sin desordenarlo: un solo paso de la inserción. */
function insertarOrdenado(array &$a, int $x): void {
    $pos = count($a);
    while ($pos > 0 && $a[$pos - 1] > $x) $pos--;   // dónde va, buscando desde el final
    array_splice($a, $pos, 0, [$x]);                 // array_splice desplaza los de la derecha
}