Algoritmos de ordenación lineal





Algoritmos de búsqueda de ordenación lineal


Estructura de Datos












INDICE:
1.- Introducción 3
2.- Tipos de algoritmos según su función. 4
2.1 – Métodos iterativos. 5
2.2 – Métodos recursivos. 5
3 – Método de la burbuja 5
3. 1 – Burbuja simple 6
3.2.- Burbuja mejorada 6
3. 3- Burbuja optimizada 6
4 – Inserción y selección.7
5 – Ordenamiento por mezclas. 8
6 – Método de HELLSORT 9
7 – Método rápido (quicksort) 10
8.- Teoría de complejidad computacional 12
9.-Bibliografía 16



1.- INTRODUCCION.
Se puede definir los algoritmos de ordenación en Ciencias de la Computación como un algoritmo que pone elementos de una lista, un vector o una matriz, con valores asignados arbitrariamente,en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listasordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos. Para poder ordenar una cantidad determinada de números almacenadas en un vector o matriz, existen distintos métodos (algoritmos) con distintas características y complejidad.
De una manera más formal se puede definir la ordenación de la siguiente manera:INPUT: una secuencia de n elementos .
OUTPUT: Una permutación de S (reordenamiento), tal que

Generalmente la secuencia de input la representaremos como un arreglo de n elementos, sin embargo en algunas aplicaciones puede estar representada usando cualquier otra estructura lineal, como por ejemplo una lista ligada.


Existe desde el método más simple, como el Bubblesort (o Método Burbuja), queson simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo.

Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSortfue analizado desde 1956.[1] Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, el ordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problemaproporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.



2.- Tipos de algoritmos según su función
Clasificación
Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:
La más común esclasificar según el lugar donde se realice la ordenación
Algoritmos de ordenamiento interno: en la memoria del ordenador.
Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.
Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:
Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.
Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha se reordena en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán...