1

Buscando por internet muestran de ejemplo de ordenación este código:

int i, pos, aux;

for (i = 0; i<5; i++) {

     pos = i;
     aux = notas[i];

     while ((pos>0) && (aux < notas[pos - 1])) {
        notas[pos] = notas[pos -1];
        pos--;
     }

     notas[pos] = aux;

   }

y funciona correctamente, pero no entiendo por qué está pensado así especificamente cuando en vez de hacer un intercambio de valores lo que hace es copiar el valor de la posición anterior y seguir copiando la posición anterior mientras sea menor y al final poner el valor original que se había guardado en una auxiliar.

No entiendo por qué ese copiar en vez de usar un intercambio de valores y así olvidarme de la variable auxiliar que queda fuera del while (aunque en el intercambio de valores debería usar una auxiliar igualmente, pero es en el momento mismo, lo que lo hace mas entendible al codigo).

¿Hay algún motivo que tal vez se me escapa?

3
  • No se ni cómo responder la pregunta. No hay ningún motivo, simplemente es un algoritmo que funciona así. Pero como has notado es un algoritmo más bien ineficiente además de acceder a la posición -1 de notas para i = 0, usar un while donde sería más conveniente un for, funcionar contra-intuitivamente... el 28 mar. 2018 a las 5:45
  • @Paula_plus_plus si i==0, entonces pos==0, luego no entra en el while... en todo lo demás coincidimos
    – eferion
    el 28 mar. 2018 a las 6:23
  • Cierto, 0 no es mayor que 0. el 28 mar. 2018 a las 6:25

1 respuesta 1

4

El algoritmo de inserción es uno intuitivo y fácil de comprender (no precisamente el más eficiente) y que puede ser útil para ordenar un conjunto de cartas cuando las tenemos en las manos.

Tienes que hacer tantas "iteraciones" como cartas tienes en las manos. En cada iteración i se trata de mover la carta i-ésima lo más a la izquierda que puedas, de modo que las i primeras cartas queden ordenadas al finalizar esa iteración.

Así, en la primera iteración "movemos" la primera carta lo más a la izquierda posible. Es decir, no hacemos nada en este caso pues ya está a la izquierda del todo. De hecho podríamos saltarnos esta primera iteración.

En la siguiente iteración tomamos la segunda carta y la comparamos con la que tiene a su izquierda. Si la que hemos tomado es menor, la movemos si no la dejamos ahi. En las siguientes iteraciones tomamos la carta correspondiente y la vamos comparando con todas las que tiene a su izquierda, de una en una. Mientras la que hemos tomado sea menor, seguimos comparando, hasta llegar a una que es menor a ella y en ese lugar la insertamos y pasamos a la iteración siguiente. Tras la última iteración todas estarán ordenadas.

Si te fijas, no obstante, al hacer la ordenación en la mano, en cada iteración en que movemos una carta de su lugar original a "su sitio correcto" más a la izquierda, para poder hacer ese movimiento estamos desplazando hacia la derecha todas las cartas que había entre su posición inicial y su posición destino. Por eso es necesario ir copiando en cada elemento del array lo que había en su posición anterior, para "hacer sitio" en el lugar donde se va a colocar.

No sé si lo que tú propones (de usar una auxiliar dentro del bucle) sería esto:

int i, pos, aux;

for (i = 0; i<5; i++) {
     pos = i;
     while ((pos>0) && (notas[pos] < notas[pos - 1])) {
        aux = notas[pos]
        notas[pos] = notas[pos -1];
        notas[pos-1] = aux;
        pos--;
     }
   }

Efectivamente este algoritmo es equivalente, pero es ligeramente más ineficiente al tener más asignaciones dentro del bucle. El número total de asignaciones ejecutadas es mayor en esta implementación.

Extra

Esta animación (sacada de brilliant.org, donde explica también otros algoritmos de ordenación) muestra perfectamente cómo funciona la ordenación por inserción:

animación

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.