Algoritmos

Trabajo de Algoritmización
Nombre: Kevin Francisco González Salmeron
Carrera: Ing. Sistemas
Año: 2
Prof: Ing. Jairo Carrillo
Fecha: 30-06-22
Algoritmo de ordenamiento
Es un algoritmo que pone elementos de una lista o un vector 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 listas ordenadas para una ejecución rápida. También es
útil para poner datos en forma canónica y para generar resultados legibles por humanos.
Los algoritmos de ordenamiento se pueden clasificar en las siguientes maneras:
 La más común es clasificar 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 en orden de fecha. Otro
caso sería cuando no interesan las mayúsculas y minúsculas, pero se quiere que si
una clave aBC estaba antes que AbC, en el resultado ambas claves aparezcan
juntas y en el orden original: aBC, AbC. Cuando los elementos son indistinguibles
(porque cada elemento se ordena por la clave completa) la estabilidad no interesa.
Los algoritmos de ordenamiento que no son estables se pueden implementar para
que sí lo sean. Una manera de hacer esto es modificar artificialmente la clave de
ordenamiento de modo que la posición original en la lista participe del
ordenamiento en caso de coincidencia.
Los algoritmos se distinguen por las siguientes características:
 Complejidad computacional (peor caso, caso promedio y mejor caso) en términos
de n, el tamaño de la lista o arreglo. Para esto se usa el concepto de orden de una
función y se usa la notación O(n). El mejor comportamiento para ordenar (si no se
aprovecha la estructura de las claves) es O(n log n). Los algoritmos más simples son
cuadráticos, es decir O(n²). Los algoritmos que aprovechan la estructura de las
claves de ordenamiento (p. ej. Bucket sort) pueden ordenar en O(kn) donde k es el
tamaño del espacio de claves. Como dicho tamaño es conocido a priori, se puede
decir que estos algoritmos tienen un desempeño lineal, es decir O(n).
 Uso de memoria y otros recursos computacionales. También se usa la notación
O(n).
Ordenamiento de burbuja (Bubble Sort en inglés)
Es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista
que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden
equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más
intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su
nombre de la forma con la que suben por la lista los elementos durante los intercambios,
como si fueran pequeñas “burbujas”. También es conocido como el método del
intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo
considera un algoritmo de comparación, siendo uno de los más sencillos de implementar.
El ordenamiento por selección (Selection Sort en inglés)

Es un algoritmo de ordenamiento que requiere O(n²) operaciones para ordenar una lista
de n elementos.Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso
de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero
cuando hay que ordenar un vector de estructuras más complejas, la operación
intercambiar() sería más costosa en este caso. Este algoritmo realiza muchas menos
operaciones intercambiar() que el de la burbuja, por lo que lo mejora en algo. Si la línea
comentada con (¡) se sustituyera por intercambiar(lista[i], lista[j]) tendríamos una versión
del algoritmo de la burbuja (naturalmente eliminando el orden intercambiar del final).
Su funcionamiento es el siguiente:
 Buscar el mínimo elemento de la lista
 Intercambiarlo con el primero
 Buscar el siguiente mínimo en el resto de la lista
 Intercambiarlo con el segundo Y en general:
 Buscar el mínimo elemento entre una posición i y el final de la lista
 Intercambiar el mínimo con el elemento de la posición i
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.
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) o cuando ya no se encuentran elementos (todos los elementos
fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1
debiendo desplazarse los demás elementos.
El ordenamiento Shell (Shell sort en inglés)
Es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor
Donald Shell. Su implementación original, requiere O(n²) comparaciones e intercambios
en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una
implementación con un rendimiento de O(n log² n) en el peor caso. Esto es mejor que las
O(n²) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log
n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es
muy difícil analizar su tiempo de ejecución.
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos
observaciones:
 El ordenamiento por inserción es eficiente si la entrada está “casi ordenada”.
 El ordenamiento por inserción es ineficiente, en general, porque mueve los valores
solo una posición cada vez.
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos
separados por un espacio de varias posiciones. Esto permite que un elemento haga “pasos
más grandes” hacia su posición esperada. Los pasos múltiples sobre los datos se hacen
con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple
ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del
vector están casi ordenados.
El ordenamiento rápido (quicksort en inglés)

Es un algoritmo de ordenación creado por el científico británico en computación C. A. R.
Hoare.
El algoritmo trabaja de la siguiente forma:
 Elegir un elemento del conjunto de elementos a ordenar, al que llamaremos
pivote.
 Resituar los demás elementos de la lista a cada lado del pivote, de manera que a
un lado queden todos los menores que él, y al otro los mayores. Los elementos
iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda,
dependiendo de la implementación deseada. En este momento, el pivote ocupa
exactamente el lugar que le corresponderá en la lista ordenada.
 La lista queda separada en dos sublistas, una formada por los elementos a la
izquierda del pivote, y otra por los elementos a su derecha.
 Repetir este proceso de forma recursiva para cada sublista mientras éstas
contengan más de un elemento. Una vez terminado este proceso todos los
elementos estarán ordenados
Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que
termine el pivote elegido.
 En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos
sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es
O(n·log n).
 En el peor caso, el pivote termina en un extremo de la lista. El orden de
complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la
implementación del algoritmo, aunque habitualmente ocurre en listas que se
encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote,
si por ejemplo el algoritmo implementado toma como pivote siempre el primer
elemento del array, y el array que le pasamos está ordenado, siempre va a generar
a su izquierda un array vacío, lo que es ineficiente.
 En el caso promedio, el orden es O(n·log n).
 No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo
se centren en la elección del pivote.

Algoritmos

Cargado por

Copyright:

Formatos disponibles

Algoritmos

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Algoritmos

Cargado por

Copyright:

Formatos disponibles

Trabajo de Algoritmización

Nombre: Kevin Francisco González Salmeron

Carrera: Ing. Sistemas

Prof: Ing. Jairo Carrillo

El ordenamiento por selección (Selection Sort en inglés)

El ordenamiento rápido (quicksort en inglés)

También podría gustarte