Algoritmos en línea

Los algoritmos en línea pueden procesar pedazo-por-pedazo sobre un conjunto de datos que están siendo procesados, sin tener un historial de datos. En cambio los algoritmos fuera de línea trabajan con  datos históricos para dar respuesta a la toma de decisiones.

Se dice que un algoritmo es en línea  (en inglés on line) 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... ý 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.

La siguiente tabla muestra los dos tipos de algoritmos:

ON-LINE	OFF-LINE
Búsqueda Secuencial	Búsqueda Binaria
Ordenación por Inserción	QuickSort
	Ordenación por Selección
	Merge Sort

Debido a que no conoce la entrada de  todo, un algoritmo en línea se ve obligado a tomar decisiones que luego pueden resultar  no ser óptima, y el  estudio de los algoritmos  en línea se ha centrado en  la calidad de la toma de decisiones que es posible en este contexto. El algoritmo de análisis competitivo formaliza  esta idea al comparar el rendimiento relativo de un algoritmo en línea y sin conexión para la instancia del mismo problema. Para otros puntos de vista sobre las entradas en línea a los algoritmos,  ver Algoritmo de flujo (centrado  en la cantidad de memoria  necesaria para representar con precisión las entradas anteriores),  el algoritmo dinámico (centrado  en la complejidad de tiempo de  mantenimiento de soluciones a  los problemas con las entradas de línea) y la máquina de aprendizaje en línea.

Ejemplo de un algoritmo en línea:

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Si vieramos el procedimiento de este algoritmo, mas o menos tendría el siguiente comportamiento:

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

En el siguiente ejemplo, 32 debe ser insertado entre 26 y 47, y por lo tanto 47, 59 y 96 deben ser desplazados.

k+1

11 26 47 59 96 32 

11 26    47 59 96

11 26 32 47 59 96

En la implementación computacional, el elemento k+1 va comparándose de atrás para adelante, deteniéndose con el primer elemento menor. Simultáneamente se van haciendo los desplazamientos.

11 26 47 59 96 32

11 26 47 59    96

11 26 47    59 96

11 26    47 59 96

11 26 32 47 59 96

El algoritmo  en pseudocódigo (con listas que empiezan por 0) debería ser como el siguiente:

algoritmo insertSort( A : lista de elementos ordenables )
    para i=1 hasta longitud(A) hacer
         index=A[i]
         j=i-1
         mientras j>=0 y A[j]>index hacer
              A[j+1] = A[j]
              j = j - 1
         fin mientras
         A[j+1] = index
    fin para
fin algoritmo

Aunque este algoritmo tiene un mejor orden de complejidad que el de burbuja, es muy ineficiente al compararlo con otros algoritmos como quicksort. Sin embargo, para listas relativamente pequeñas el orden por inserción es una buena elección, no sólo porque puede ser más rápido para cantidades pequeñas de elementos sino particularmente debido a su facilidad de programación. 

Implementación en JavaScript

void insertionSort(int numbers[], int array_size) {
   int i, a, index;
   for (i=1; i < array_size; i++) {
      index = numbers[i];
      a = i-1; 
      while (a >= 0 && numbers[a] > index) {
         numbers[a + 1] = numbers[a];
         a--;
      }
      numbers[a+1] = index;
   }
}