Algoritmodeordenamientoporinsercion
Páginas: 10 (2433 palabras)
Publicado: 6 de mayo de 2015
UNIVERSIDAD NACIONAL DEL CAAGUAZU
FACULTAD DE CIENCIAS Y TECNOLOGIA
CRISTHIAN EDUARDO VELAZQUEZ CORONEL
INTRODUCCION
En la Informática, específicamente dentro de la programación se encuentran los algoritmos de ordenamiento. Existen varios algoritmos de ordenamiento, pero nos centraremos solamente en uno, por inserción. Este algoritmo nos servirá para ordenar vectores o matricescon valores asignados aleatoriamente
En este trabajo trataremos de explicar dicho algoritmo, analizando la cantidad de comparaciones que suceden, algunas características, ventajas, desventajas y revisando el código, escrito en pseudocódigo del algoritmo.
ALGORITMO DE ORDENAMIENTO POR INSERCION:
Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación sonimprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no.
Es un algoritmo estable de ordenación interna y su complejidad temporal en el peor caso es de O(n2) y en el mejor caso -que el array ya esté totalmente ordenado- puede llegar a Ω(n) siendo n el tamaño del array aordenar.
El algoritmo consiste en realizar varias pasadas sobre el array. En cada pasada se analiza un elemento, y se intenta encontrar su orden relativo entre los analizados en pasadas anteriores. Con esto se logra ir manteniendo una lista ordenada constantemente. Cada elemento a analizar se desplaza por esa lista hasta encontrar su lugar. Cuando todos los elementos del array han sido analizados, lalista está completamente ordenada. En InsertionSort, el array no está totalmente ordenado hasta que el algoritmo termina.
Por otro lado, en cada pasada no se recorre todo el array, sino solo los elementos analizados y ordenados en pasadas anteriores. Eso convierte a InsertionSort en un Algoritmo en línea (online), es decir, un algoritmo que no necesita disponer de todos los elementos a ordenar desdeel principio, sino que puede aceptarlos de uno en uno y procesarlos a medida que los recibe.
Vamos a intentar ver informalmente el funcionamiento del algoritmo. Supondremos que el array 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 yno n es que empezamos por el segundo elemento. Si analizásemos 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 lasegunda el tercero.... en la n-1 el n) y recorreremos el array 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.
Un ejemplo
Vemos un ejemplo sencillo. Supongamos que queremos ordenar estos valores con el algoritmo deselección directa: 45, 52, 21, 37, 49, 72, 14. Así pues, n=7
Empezamos a analizar el segundo elemento. El primero está en orden con respecto a sí mismo. Forma él solo una lista ordenada. Intentaremos mantener una lista ordenada al principio del array. Vamos a marcar el elemento a analizar en rojo y la lista ordenada en azul.
1ª pasada: El primer elemento forma la lista ordenada, y vamos a ver qué hacemoscon el segundo.
45, 52, 21, 37, 49, 72, 14 → Comparamos 52 con el anterior. Como está en orden, paramos.
45, 52, 21, 37, 49, 72, 14 → 45 y 52 forman la lista ordenada ahora. (Sí, sí... están en orden entre ellos 45<52)
2ª pasada: Hay dos elementos en orden relativo entre ellos y vamos a ver qué hacemos con el tercero.
45, 52, 21, 37, 49, 72, 14 → Comparamos el 21 con el anterior (52). No están...
UNIVERSIDAD NACIONAL DEL CAAGUAZU
FACULTAD DE CIENCIAS Y TECNOLOGIA
CRISTHIAN EDUARDO VELAZQUEZ CORONEL
INTRODUCCION
En la Informática, específicamente dentro de la programación se encuentran los algoritmos de ordenamiento. Existen varios algoritmos de ordenamiento, pero nos centraremos solamente en uno, por inserción. Este algoritmo nos servirá para ordenar vectores o matricescon valores asignados aleatoriamente
En este trabajo trataremos de explicar dicho algoritmo, analizando la cantidad de comparaciones que suceden, algunas características, ventajas, desventajas y revisando el código, escrito en pseudocódigo del algoritmo.
ALGORITMO DE ORDENAMIENTO POR INSERCION:
Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación sonimprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no.
Es un algoritmo estable de ordenación interna y su complejidad temporal en el peor caso es de O(n2) y en el mejor caso -que el array ya esté totalmente ordenado- puede llegar a Ω(n) siendo n el tamaño del array aordenar.
El algoritmo consiste en realizar varias pasadas sobre el array. En cada pasada se analiza un elemento, y se intenta encontrar su orden relativo entre los analizados en pasadas anteriores. Con esto se logra ir manteniendo una lista ordenada constantemente. Cada elemento a analizar se desplaza por esa lista hasta encontrar su lugar. Cuando todos los elementos del array han sido analizados, lalista está completamente ordenada. En InsertionSort, el array no está totalmente ordenado hasta que el algoritmo termina.
Por otro lado, en cada pasada no se recorre todo el array, sino solo los elementos analizados y ordenados en pasadas anteriores. Eso convierte a InsertionSort en un Algoritmo en línea (online), es decir, un algoritmo que no necesita disponer de todos los elementos a ordenar desdeel principio, sino que puede aceptarlos de uno en uno y procesarlos a medida que los recibe.
Vamos a intentar ver informalmente el funcionamiento del algoritmo. Supondremos que el array 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 yno n es que empezamos por el segundo elemento. Si analizásemos 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 lasegunda el tercero.... en la n-1 el n) y recorreremos el array 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.
Un ejemplo
Vemos un ejemplo sencillo. Supongamos que queremos ordenar estos valores con el algoritmo deselección directa: 45, 52, 21, 37, 49, 72, 14. Así pues, n=7
Empezamos a analizar el segundo elemento. El primero está en orden con respecto a sí mismo. Forma él solo una lista ordenada. Intentaremos mantener una lista ordenada al principio del array. Vamos a marcar el elemento a analizar en rojo y la lista ordenada en azul.
1ª pasada: El primer elemento forma la lista ordenada, y vamos a ver qué hacemoscon el segundo.
45, 52, 21, 37, 49, 72, 14 → Comparamos 52 con el anterior. Como está en orden, paramos.
45, 52, 21, 37, 49, 72, 14 → 45 y 52 forman la lista ordenada ahora. (Sí, sí... están en orden entre ellos 45<52)
2ª pasada: Hay dos elementos en orden relativo entre ellos y vamos a ver qué hacemos con el tercero.
45, 52, 21, 37, 49, 72, 14 → Comparamos el 21 con el anterior (52). No están...
Leer documento completo
Regístrate para leer el documento completo.