Se dice que un algoritmo es en línea cuando es capaz de ponerse a trabajar en el problema para el que fue diseñado sin necesidad de disponer de todos los datos de entrada antes de empezar, es decir, que puede trabajar a medida que va recibiendo los datos de entrada.
Por ejemplo, el algoritmo de ordenación BubbleSort no es un algoritmo en línea (podría decirse que es fuera de línea u offline), porque si tiene que trabajar sobre 10 valores, necesita que los diez valores estén disponibles al comienzo del algoritmo. Sin embargo, el algoritmo de ordenación InsertionSort sí es un algoritmo en línea, porque si tiene que trabajar sobre 10 valores, puede leer el primero y procesarlo, y luego el segundo y procesarlo, y luego el tercero y procesarlo... y así hasta el último. Puede realizar parte de su trabajo con una entrada parcial de los datos, ya que el procesamiento de los datos sólo depende de los datos de entrada leídos hasta el momento, y no de la totalidad.
Vamos a intentar ver el funcionamiento del algoritmo. Supondremos que el arreglo tiene n elementos.
Realizaremos n-1 pasadas. En cada una de ellas analizaremos un elemento, colocándolo en orden relativo con respecto a los analizados en pasadas anteriores. El motivo de realizar n-1 pasadas y no n es que empezamos por el segundo elemento. Si analizáramos el primer elemento deberíamos colocarlo en orden con respecto a los anteriores, pero al no haber realizado pasadas anteriores, el primer elemento forma él solito una lista ordenada. Así pues, empezamos con el segundo directamente.
En cada pasada escogemos un elemento sucesivamente (en la primera pasada el segundo elemento, en la segunda el tercero.... en la n-1 el n) y recorreremos el arreglo hacia atrás (hacia la izquierda, si quieres) buscando el orden relativo del elemento en cuestión entre los anteriores (los de su izquierda). Cada vez que encontremos un elemento que sea mayor que él realizaremos un intercambio.
A continuación veremos el código ejemplo de este algoritmo:
¿Y la relación de todo esto a la toma de decisiones? Te pongo 4 puntos.
ResponderBorrar