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:
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:
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+111 26 47 59 96 32 11 26 47 59 9611 26 32 47 59 96En 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 3211 26 47 59 9611 26 47 59 9611 26 47 59 9611 26 32 47 59 96El 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;
}
}
