Te encuentras en la páginas de Blogsperu, los resultados son los ultimos contenidos del blog. Este es un archivo temporal y puede no representar el contenido actual del mismo.
Bueno acabo de crear un plugin de carousel con Jquery si desean utilizarlo pueden descargarlo
aquí así como la documentación.
Vamos a revisar como utilizar el paradigma divide y vencerás (divide and conquer) para contar inversiones (no las económicas obviamente), pero primero para ello definamos lo que son inversiones, según Wikipedia:
"En ciencias de la computación y en matemática discreta, dada una secuencia de números, una inversión es un par de números en dicha secuencia que están "desordenados" con respecto a un orden ascendente o descendente."
o formalmente:
"Sea (A(1), A(2) , ... , A(n) ) una secuencia de n distintos números. Si i < j y A(i) > A(j), entonces el par (i, j) es llamado una inversión de A."
Por lo que por ejemplo en la secuencia A = [2, 4, 1, 3, 5], tenemos 3 inversiones (A[1], A[3]) = (2, 1), (A[2], A[3]) = (4, 1) y (A[2], A[4]) = (4, 3) con respecto a un orden ascendente.
Cualquiera que no conozca mucho sobre algoritmos lo primero que haría tal vez es tratar de solucionarlo por fuerza bruta, a través de bucle anidado, como ejemplo en código JavaScript sería de la siguiente forma:
function inversionBruteForce(array) {
var inversions = 0;
for (i in array) {
for (j in array) {
if ((i < j) && (array[i] > array[j]))
inversions++;
}
}
return inversions;
}
Como vemos la condición para aumentar el número de inversiones es precisamente la definición que dimos anteriormente, vemos que el código es fácil de leer y seguir mentalmente, pero esta manera de hacerlo tiene una
complejidad Θ(n^2) lo que para entradas muy grandes sería muy ineficiente, ya que precisamente su complejidad se debe a que hace todas las comparaciones posibles.
Pero como nosotros estamos estudiando algoritmos obviamente vamos a buscar maneras de ser mas eficientes, así que para ello, como mencione al principio, vamos a seguir el paradigma divide y vencerás (divide and conquer).
Si han visto antes el algoritmo de ordenación Merge Sort les será mas facil comprenderlo, pues utilizaremos el mismo principio, es más, en realidad lo que haremos sera montarnos sobre ese algoritmo y adicionarle un paso más en cada recursión, que será el de contar las inversiones. Vamos a darnos una idea mental primero de lo que vamos a hacer con un ejemplo.
Si tuviéramos la secuencia [4, 2, 1, 3] y quisiéramos encontrar el numero de inversiones (el cual es 4) vamos a dividir el problema en dos, la primera secuencia [4, 2] (izquierda) y la segunda secuencia [1, 3] (derecha). En la secuencia de la izquierda vemos que tenemos 1 inversión y en la segunda no tenemos ninguna, entonces hasta ahora vamos 1, ya que ya hemos analizado ambas partes por separado, ahora vamos ordenarlas para comparar elementos entre las dos partes, este paso no modificará el problema en absoluto pues ya llevamos la cuenta de las inversiones que tienen la subsecuencias que hemos ordenado, y el hecho de estar ordenadas nos da una ventaja, veamos porque.
Si ordenamos las subsecuencias tenemos entonces [2, 4] (izquierda) y [1, 3] (derecha), entonces comparamos ahora el primer elemento de la secuencia de la derecha, es decir 1, con el primer elemento de la secuencia de la izquierda, es decir 2, notamos entonces que 1, al estar en la derecha tiene una posición mayor (3) pero su valor es menor que elemento de la izquierda, con lo cual adicionamos uno mas a la cuenta de inversiones. Ahora fíjense que no tenemos que comparar ese elemento 1 con los demás elementos después de 2 (en este caso 4) ya que al estar ordenada la secuencia de la izquierda los elementos sobrantes tienen que ser mayores con lo que concluimos que si los comparáramos con 1, obtendríamos también mas inversiones (en este caso 1 mas), con lo cual el numero de inversiones adicionales seria el numero de elementos restantes en la secuencia de la izquierda. De igual manera procederíamos con el 3, con lo cual nos dará una inversión mas al compararla con 4. Y así al final el numero de inversiones que tendríamos será de 4 si repasamos todas las lineas subrayadas anteriormente.
Realizar la busqueda de inversiones de esta manera tiene la ventaja que al estar montado en el algoritmo Merge Sort va a tener su misma complejidad, la cual es
O(n*logn).
Ahora si veámoslo en pseudocódigo, porque ya estamos grandecitos y ya debemos poder implementar pseudocódigo en cualquier lenguaje de programación :), pero de todas formas mas abajo dejaré adicionalmente una implementación en JavaScript, si lo quieren ver funcionando.
Construiremos nuestra función "sortAndCount", la cual tendrá como entrada una secuencia de números y tendrá como salida la secuencia de números ordenada y el numero de inversiones que hay en ella.
1. sortAndCount(A)
2. /* L es la mitad izquierda
3. * R es la mitad derecha
4. * iL el numero de inversiones en L
5. * iR el numero de inversiones en R
6. * oL la secuencia L pero en forma ordenada
7. * oR la secuencia R pero en forma ordenada
8. * LR la unión de L Y R en forma ordenada
9. * iLR el numero de inversiones de LR
10 */
11.
12. if A tiene un elemento return 0
13. else
14. divide A into L, R
15. (iL, oL) = sortAndCount(L)
16. (iR, oR) = sortAndCount(R)
17. (iLR, oLR) = mergeAndCount(oL,oR)
18. return iL+iR+iLR, LR
Al igual que en el algoritmo Merge Sort vamos a dividir la secuencia, hasta el caso base en que A sea de tamaño 1 y resolverla recursivamente para lo cual nos ayudaremos como vemos en la linea 17 de otra función llamada "mergeAndCount", la cual tendra como pseucódigo:
1. mergeAndCount(oLeft,oRight)
2. ; oLeft,oRight dos secuencias ordenadas
3. ; result secuencia unida de oLeft y oRight en forma ordenada
4. ; i,j indices de las secuencias
5. ; oLeft(i), oRight(j) elementos con indice i, j
6. ; count numero of inversiones, inicializa en 0
7.
8. while oLeft,oRight != empty
9. append min(oRight(i), oLeft(j)) to result
10. if oRight(j) < oLeft(i)
11. count += numero de elementos restantes en oLeft
12. j++
13. else
14. i++
15. ; ahora si una lista esta vacia
16. agregar el resto de la lista a result
17. return count, C
Esta función tomara dos listas ordenadas y devolverá la unión de las dos en forma ordenada y el numero de inversiones que hay entre ellas.
Podemos ver como funcionaría toda la secuencia en el siguiente gráfico.
Aquí podemos ver toda la recursión y como se van acumulando los valores y las secuencias ordenadas,
note que SAC se refiere a una llamada a sortAndCount y MAC a una llamada a mergeAndCount que no aparece en el gráfico pero se asume que se devolvieron los valores esperados para continuar con la recursión.
Espero que se pueda haber entendido todo, y para finalizar les dejo la implementación del algoritmo en código JavaScript.
/* Counting Inversions Algorithm */
function sortAndCount(array) {
if (array.length < 2)
return [0, array];
var mLeft = array.slice(0, array.length / 2);
var mRight = array.slice(array.length / 2);
var x = sortAndCount(mLeft);
var y = sortAndCount(mRight);
var z = mergeAndCount(x[1], y[1]);
return [x[0] + y[0] + z[0], z[1]];
}
function mergeAndCount(oLeft, oRight) {
var count = 0;
var arrayOrdered = [];
while (oLeft.length && oRight.length) {
if (oRight[0] < oLeft[0]) {
arrayOrdered.push(oRight.shift());
count += oLeft.length;
} else {
arrayOrdered.push(oLeft.shift());
}
}
while (oLeft.length)
arrayOrdered.push(oLeft.shift());
while (oRight.length)
arrayOrdered.push(oRight.shift());
return [count, arrayOrdered];
}
Hace unos días estuve realizando una aplicación con
node js,
express js,
socket io y
mongodb, la cual consiste en un bot conversacional, no muy sofisticado por cierto, el cual simula una conversación y se le puede enseñar a responder.
Realizando esta aplicación me vi en la necesidad de obtener una variable adicional desde el cliente en mitad de la ejecución del código en el servidor; es decir luego de que el cliente enviara los datos para ser procesados por el servidor; este en base a unas características que tenia la información enviada por el cliente, decidía si pedir o no un dato adicional. El problema era precisamente ello, que los datos ya habían sido enviados y se estaban procesando; lo que necesitaba era parar la ejecución en ese punto y solicitar un dato mas al cliente para luego regresar al servidor y seguir con la ejecución desde el punto en que se detuvo. Pude resolver el problema y esto me hizo dar cuenta además de como poder compartir variables y funciones entre el cliente y el servidor, siguiendo la misma lógica.
La solución para ello la pude realizar gracias a una característica de Javascript, la cual nos permite pasar funciones como argumentos de otras funciones, lo que nos da la posibilidad de realizar callbacks, como los que se usan en Jquery. Veamos un ejemplo de callback primero.
function mathematics(params, callback) {
var result = null;
if(params.operation == 'suma')
result = params.values[0] + params.values[1]
else if(params.operation == 'resta')
result = params.values[0] - params.values[1]
callback(result);
}
Bien, no es una función muy útil pero sirve para fines de ejemplo, vamos a recibir un objeto con los valores y la operación que queremos realizar, y luego le aplicamos el callback, es decir, con el callback le estamos diciendo a Javascript ejecuta esta función y luego que termines, con el resultado haces otra cosa (lo que se indique en el callback), veamos como utilizarlo.
// Usando el callback
mathematics({operation: 'suma', values: [3, 2]}, function(result){
var result = result + 10;
alert(result); // 15
})
Como decia, podemos dejarle indicado a Javascript "vas a sumar estos numeros y luego cuando termines, con el resultado vas a hacer lo que te estoy indicando".
Habiendo visto esto, vayamos a la cuestión que les mencione al principio. La idea de este código va a ser enviar un dato al servidor y procesar ese dato, y según a las características de ese dato, pedir o no un dato adicional para continuar con el procesamiento, para ello utilizaremos Socket IO. Por cierto voy a asumir que sabes como funciona socket IO, node js, express, etc, si no que esperas para aprender!! :D.
El cliente nos va a enviar el nombre de su gato (porque los ejemplos sin gatos no tienen sentido :D), en el servidor la vamos a recibir, si el nombre de su gato comienza con "m" vamos a solicitarle adicionalmente de que color es para seguir procesando la información (ok se que no tiene nada que ver el nombre con el color pero no soy muy creativo para ejemplo, pero al menos se entienda la idea).
// En el cliente
socket('connect', function(){
// Enviamos el nombre del gato
socket.emit('sendCat', 'michi');
// Si el nombre del gato comienza con "m", activamos esto desde el servidor
socket.on('getCatColor', function(callback){
var catColor= prompt('Comienza con m, asi que dime de que color es');
callback(catColor)
});
});
// En el servidor
io.sockets.on('connection', function(socket) {
// Recibimos nombre del gato
socket.on('sendCat', function(catName){
// Si comienza con "m" pedimos su color y luego guardamos nombre y color
if(catName[0] === 'm'){
socket.emit('getCatColor', function(catColor) {
var catColor = 'es de color: ' + catColor;
save(catName, catColor);
});
}
// si no comienza con "m" solo guardamos nombre
else {
save(catName);
};
});
});
La parte interesante del código es el socket.emit('getCatColor', callback); aqui enviamos el callback que sera ejecutado en la parte del cliente socket.on('getCatColor', function(callback){...}) y de esa manera podemos tener acceso a la variable catColor en el cliente.
Pues como vimos hemos pedido un dato adicional en tiempo de ejecución en el servidor, esto nos lleva a que podemos también acceder a cualquier otra variable o función del cliente desde el servidor, y viceversa.
Cabe resaltar que existe un framework que nos da esta funcionalidad llamado
NowJs aunque tiene demasiadas dependencias para mi gusto, y al menos yo no necesitaba toda sus funcionalidad, pero si desean explorar mas de estas características esa opción esta diseñada precisamente para compartir variables y funciones en ambos lados.
Veamos un primer análisis para el algoritmo de ordenamiento por inserción.
Existen diferentes aspectos que podemos tomar en cuenta para analizar la eficiencia de un algoritmo, de entre las cuales el tiempo de ejecución (running time) es el que con mas frecuencia nos va a interesar.
El tiempo tomado por el algoritmo insertion sort para resolver el problema depende del tamaño del input y de cuan ordenado esté antes de ser procesado. Tradicionalmente definimos el running time de un programa como una función del tamaño de su input.
El tamaño del input en este caso es el numero de elementos de la matriz, pero este concepto de tamaño puede variar según el contexto del problema, algunas veces por ejemplo sera mejor medir de acuerdo a la cantidad de bits que el input representa.
Cada linea que constituye nuestro código representa cada uno de los pasos que sigue nuestro algoritmo, cada paso es ejecutado en un cierto intervalo de tiempo, representamos entonces con "ci" el costo de tiempo de una determinada linea "i". Vemos ademas que en nuestro código tenemos bucles lo cual hace que tengamos lineas de código ejecutándose repetidamente cierto numero de veces.
Tres cosas importantes que debemos notar antes de continuar; primero, tenemos que tomar en cuenta que la condición del bucle, es decir la primera linea que controla su continuidad, es leida una vez mas que el cuerpo del bucle; segundo, ya que el bucle while es un bucle que esta anidado dentro del bucle for, este se va a repetir varias veces por lo cual vamos a representar las veces que este se ejecuta por "ti" (t sub i) con lo que la sumatoria de los "ti" esta definida por la cantidad de veces que se ejecute el bucle for; tercero, consideramos que los comentarios incluidos en el código no son ejecutados y por lo tanto no consumen tiempo alguno. Veamos entonces ahora nuestro codigo.
Como vemos el tiempo tomado por cada linea es el producto de cost por time, el running time es entonces la sumatoria de todos estos.
Como vemos el running time es una función del tamaño del input (n), ya que el costo por cada linea lo consideramos constante.
Para un determinado tamaño de input tenemos dos casos extremos que constituyen respectivamente el mínimo y máximo tiempo que puede tomar el algoritmo en resolver el problema.
El mejor caso (best-case) es cuando tenemos ya el input ordenado antes de ser procesado por el algoritmo, en ese caso la condición de ejecucion del bucle while no se cumplira a lo largo del recorrido de la matriz por lo que no se ejecutara el cuerpo del bucle (ojo que la comprobación si) por consiguiente nuestra expresión se reduce a esto.
Factorizando n vemos que tenemos entonces una función lineal de n.
El peor caso (worst-case) es cuando tenemos como input la matriz pero en orden decreciente, ya que el el cuerpo del bucle while siempre se va a ejecutar y este va a recorrer hasta el final de la matriz en todas las iteraciones del bucle for. Por lo que nuestra expresión quedaría así.
Factorizando nuevamente n vemos que tenemos una función cuadrática de n.
Con estos resultados podemos darnos una primera idea sobre la eficiencia del algoritmo, pero cuando nosotros analizamos un algoritmo no estamos tan interesados en el valor que nos pueda dar el calculo de la sumatoria, mas nos interesa el comportamiento de dicha función respecto a los valores de n, es decir el radio u orden de crecimiento del running time para valores grandes de n, asi que con el único termino con el que nos vamos a quedar es con el de mayor grado, mas aun descartaremos su coeficiente, con lo cual podemos decir que el ordenamiento por inserción tiene un worst-case running time de Θ(n^2).
Nosotros usualmente consideramos que un algoritmo es mas eficiente que otro si su worst-case running time tiene un menor orden de crecimiento.
Hemos introducido algunos conceptos muy superficialmente y sin mucho detalle que iremos ampliando en próximas publicaciones
Bibliografia: Introduction to Algorithms: Thomas H. Cormen, Charles E. Leiserson,Ronald L. Rivest,Clifford, Third Edition.En el post anterior habíamos explicado el funcionamiento del algoritmo insertion sort, quedaba pendiente explicar algunos conceptos importantes así que pasemos a ello.
Primero es importante resaltar el concepto de loop invariant (o invariante de bucle no estoy muy seguro de su correcta traducción, la usaré así en el resto del articulo si estoy equivocado o en lo correcto agradecería su confirmación :)). Veamos primero que dice Wikipedia.
Loop Invariant: "En ciencia de la computación el invariante de bucle es un invariante usado para verificar las propiedades de un bucle, Informalmente, un invariante de bucle es un enunciado con las condiciones que deberían ser ciertas al inicio de un bucle y que son garantizadas para permanecer verdaderas sobre cada iteración del bucle."
Bien, habiendo leído mi intento de traducción :D, rescatemos los términos subrayados, primero el de "es un enunciado" debe quedar claro eso ya veremos despues como lo aplicamos al algoritmo, segundo el de invariante, aunque creo que quedo claro la definición creo que si queremos entender bien que es un invariante de bucle seria buena idea saber que cosa es un invariante así que pasemos a Wikipedia nuevamente.
Invariant: "En ciencia de la computación un predicado es llamado un invariante para una secuencia de operaciones siempre que: Si el predicado es verdad antes de que empiece la secuencia, entonces este es verdad al final de la secuencia."
Bien, ya tenemos la definición de invariante, pero ahora seguro se preguntaran que es un predicado, bueno nuevamente Wikipedia :).
Predicate: "Un predicado es un enunciado que puede ser verdadero o falso dependiendo de los valores de sus variables. Este puede ser pensando como un operador o función que retorna verdadero o falso."
Bien ya no sigamos retrocediendo mas sino vamos a terminar en la creación del universo, asi que en resumen creo que queda mas claro lo de invariante de bucle (y ademas la importancia de la lógica en algoritmos) así que revisemos cual es el invariante de bucle en nuestro algoritmo.
Habíamos visto que cada vez que seleccionamos un elemento teníamos dos submatrices y entre ellas la submatriz A[1 ... j-1], la cual contiene los elementos originales A[1 ... j-1] pero ordenados. Entonces definamos nuestro invariante:
"Al inicio de cada iteración del bucle for la submatriz A[1 ... j-1] consiste en los elementos originales de A[1 ... j-1] pero en forma ordenada"
Bien como habíamos definido y subrayado aquí tenemos el enunciado que constituye nuestro invariante de bucle, es decir el enunciado con las propiedades que deben ser verdaderas al inicio del bucle y durante cada iteración.
Pues bien, y ¿Para que nos sirve eso?. Esto nos sirve para probar si el algoritmo es o no correcto, nosotros deberíamos buscar tres cosas en un invariante de bucle.
Initialization: Es verdadero antes de la primera iteración del bucle. Como vimos anteriormente, antes de la primera iteración cuando j=2, la submatriz A[1 ... j-1] = A[1] contenía solo un elemento <6>, el cual es la matriz original A[1 ... j-1] en forma ordenada (obviamente es un solo elemento y estará ordenado) por lo cual cumple con nuestro invariante de bucle.
Maintenance: Es verdadero antes de una iteración de bucle y permanece verdadero antes de la siguiente iteración. Como habíamos visto anteriormente la submatriz A[1 ... j-1] en cada iteración consistía en la submatriz original pero en forma ordenada, por lo cual nuestro algoritmo cumple con nuestro invariante de bucle.
Termination: Es verdadero al finalizar el bucle. Al finalizar nuestro bucle tenemos nuestra matriz A[1 ... j-1] = A[1 ... n]. la cual consiste en la matriz original A[1 ... n] pero en forma ordenada, con lo cual también cumple nuestro invariante de bucle.
Como vemos para las dos primeras propiedades el invariante de bucle es cierto antes de cada iteración. Note que similarmente a la inducción matemática nosotros probamos que la propiedad permanece verdadera, probando un caso base y un paso inductivo. Aquí la inicialización corresponde al caso base y mostrando que el invariante se mantiene a través de cada iteración corresponde al paso inductivo.
La terca propiedad es quizás la mas importante pues esta nos indica si el algoritmo es correcto o no, típicamente la inducción se realiza para un numero infinito de casos, pero aquí nosotros detenemos la "inducción" cuando el bucle termina.
Bibliografia: 1. Introduction to Algorithms: Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford, Third Edition.2. http://en.wikipedia.org/
Uno de los problemas con el que se suele empezar el estudio de algoritmos es el de ordenamiento, ya existen diferentes formas por las cuales se puede abordar este problema y con ello permite explicar muchos conceptos y técnicas algorítmicas.
En esta oportunidad veremos una explicación del algoritmo de ordenamiento por inserción (insertion sort) para resolver el problema de ordenamiento (sorting problem), ademas de repasar algunos conceptos importantes.
Como sabemos un algoritmo es un procedimiento bien definido que toma un valor o conjunto de valores (entrada o input) y produce un valor o conjunto de valores (salida o output). Asi que definamos ambos conceptos para nuestro algoritmo.
Input: Una secuencia de n números <a1, a2, ... ,an>
Output: Un secuencia ordenada <a1', a2', ... ,an'> a partir del input tal que a1'<=a2'<=...<=an'
En términos generales, la idea del algoritmo es ir tomando cada valor del input comenzando por el segundo por medio de un bucle e ir comparándolo con los anteriores elementos para
insertarlo en la posición adecuada así como podemos apreciar en la imagen(es decir que este a la derecha de los valores que son menores a el y a la izquierda de los que son mayores que el), esto conlleva a que en una iteración determinada los elementos anteriores al elemento seleccionado se encuentran en orden, esto constituirá lo que denominaremos
loop invariant (cosa que explicamos en
este otro artículo con mas detalle).
Veamos como funciona el algoritmo con una instancia del problema.
Tenemos la siguiente matriz A = <6, 3, 5, 7, 2, 4>, representamos a la posición de cada elemento que seleccionamos por "j", tal que 1<=j<=6, donde j es un entero. Entonces podemos representar como A[j] a cada elemento que seleccionemos de acuerdo a su posición, por ejemplo A[1]=6 , A[3]=5 , etc.
Empezamos seleccionado el elemento j = 2, es decir A[2] = 3, en ese instante notemos que tenemos dos submatrices, una es la submatriz A[1 ... j-1] = A[1] = <6> que es la que contiene los valores a la izquierda del elemento seleccionado, la cual contiene los elementos que vamos ordenando hasta una determinada iteración y la otra es la submatriz A[j+1 ... n] = A[3, 4, 5, 6] = <5, 7, 2, 4> la cual contiene los elementos que nos falta seleccionar para ordenarlos.
Siguiendo con el ejemplo, habiendo seleccionado el elemento A[2] = 3 lo comparamos con el que se encuentra a su izquierda inmediata si este es mayor lo movemos a la derecha (resalto esto puesto que el hecho de moverlo a la derecha requiere una serie de pasos en el código menos intuitivos que el simple hecho de pensar en moverlo a la derecha, pero ya veremos eso), si este no es mayor entonces dejamos el elemento en su misma posición y pasamos al siguiente elemento de nuestra sub matriz A[j+1 ... n]. Tenga en cuenta que ahora nuestra matriz A = <6, 3, 5, 7, 2, 4>, es ahora A = <3, 6, 5, 7, 2, 4> .En este primer paso solo tuvimos que comparar con un elemento así que de todas maneras teníamos que pasar a seleccionar el siguiente elemento, pero sigamos con el algoritmo.
Seleccionamos ahora el elemento A[3] = 5 y vemos que el elemento que se encuentra a su izquierda es el 6 así que 5<6 por lo tanto tenemos que moverlo a la derecha, ahora comparamos con el de su izquierda nuevamente y tenemos que 5>3, por lo tanto terminamos e insertamos el valor seleccionado en esa posición y pasamos a seleccionar el siguiente elemento de la matriz A[j+1 ... n]. Es importante notar que si hubieran habido mas elementos después de 3 de todas maneras no hubiera sido necesario continuar examinando los demás elementos pues como dijimos anteriormente la matriz A[1 ... j-1] esta ordenada por consiguiente los elementos restantes van a ser menores que el que hemos seleccionado, así que basta toparse con el primero para terminar de comparar.
Veamos ahora un seudocódigo para realizar este algoritmo.
1 for j = 2 to A.length2 key = A[j]3 i = j - 14 while i > 0 and A[i] > key5 A[i+1] = A[i]6 i = i - 17 A[i+1] = key
Como vemos en la linea 1 el bucle ira desde 2 hasta A.lenght que es el tamaño de la matriz, es decir 6 (tenga en cuenta que en este código estamos considerando que la primera posición es 1 y no 0 como normalmente es en programación), en la linea 2 estamos seleccionando el valor que tomaremos para ordenarlo, en la linea 3 definimos la posición anterior a la del valor seleccionado, en la linea 4 definimos el bucle para comparar el elemento seleccionado con los de su izquierda con las condiciones necesarias para la búsqueda, es decir que i sea mayor que cero ya que si no lo es significa que habremos llegado al final de todos los elementos y por lo tanto debemos de terminar la búsqueda, igualmente si A[i] > key, ya que si es mayor ya no es necesario seguir ordenando debemos terminar la búsqueda y pasar al siguiente elemento.
Desde la linea 5 hasta la 7 es lo que anteriormente resaltamos como mover a la derecha, lo que hace en realidad es copiar a la derecha el elemento que se esta revisando si es que este cumple las condiciones, y así sucesivamente vamos moviendo los elementos hasta que ya no se cumpla la condición y es ahí cuando insertamos el elemento seleccionado (el que queremos ordenar) como se indica en la linea 7 del seudocodigo, el cual reemplaza el ultimo elemento revisado por el elemento seleccionado.
Para mas exactitud en como funciona el algoritmo con el seudocódigo imagine en la imagen al principio del post que nunca quedan espacios en blanco, sino que cada movimiento a la derecha es en realidad una copia de ese elemento, y el hecho de que otro elemento llene un espacio en blanco así como el hecho de que el elemento seleccionado para ordenar llene un espacio en blanco es en realidad un reemplazo o superposición.
Al final del algoritmo logramos obtener una matriz ordenada.
Espero que haya quedado claro por ahora , queda pendiente explicar como dije al inicio algunos conceptos importantes (como el
loop invariant), pero lo dejaremos para
la siguiente publicación ya que no me gusta hacer post muy largos. Cualquier pregunta, aclaración o corrección lo pueden hacer con sus comentarios.
Bibliografia: Introduction to Algorithms: Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford, Third Edition.