algotitmos de ordenamiento.
En
la entrada de esta semana se hablará sobre el tema de algoritmos de
ordenamiento, que es un algoritmo de ordenamiento, cuales son algunos de los más
conocidos y de estos cual se caracteriza por ser el más rápido y cuales son más
lentos, e ineficientes.
 |
Para iniciar este tema es importante como
lo hemos hecho en entradas anteriores, aclarar algunas definiciones para llegar
al tema central. Como nuestro tema central es algoritmos de ordenamiento pues
vamos a definir este término, ¿Que es un algoritmo? Según la RAE (Real Academia
Española) un algoritmo se define como “Conjunto ordenado y finito de
operaciones que permite hallar la solución de un problema” y el ordenamiento es
“Acción y efecto de ordenar” entonces podemos decir de un algoritmo de
ordenamiento es un conjunto finito de operaciones que nos permite ordenar
datos.
Se comentará sobre el funcionamiento de 4
algoritmos de ordenamiento los cuales son:
·
Bubble Sort.
·
Selection Sort.
·
Insertion Sort.
·
Quicksort.
Bubble
Sort
Según el artículo “Ordenar por Bubble -
Bubble Sort” de Jorge P este algoritmo “clasifica a través de toda la matriz
comparando cada uno de los elementos con el siguiente elemento e
intercambiarlos si es necesario. Al final de este proceso, el elemento más
grande se encuentra en la última posición de la disposición, mientras que todos
los elementos menores han "ascendido" a una posición. El proceso
continúa repitiendo de nuevo desde la posición de fijación inicial hasta que
cada elemento "caiga" a su posición correcta”. Entonces si hacemos un
análisis de esto podemos ver que este algo ritmo es muy ineficiente es porque
deben recorrer toda la estructura para ordenar elemento por elemento. La programación
de su código es en iteración y es la siguiente; brindada por Mauricio Avilés en
su presentación “Estructuras de datos”.
def bubble_sort(lista):
swap = True
while swap:
swap = False
i = 0
while i < len(lista)-1:
if lista[i] > lista[i+1]:
temp = lista[i]
lista[i] = lista[i+1]
lista[i+1] = temp
swap = True
i +=1
return lista
Selection
Sort
Este Algoritmo según la presentación elaborada
por Mauricio Avilés tampoco es
muy eficiente para listas grandes, funciona encontrando el menor elemento de la lista
lo intercambia con el primero
de la lista y repite lo mismo con el resto de la lista.
Este también
está programado de manera iterativa y su código es este:
def selection_sort(lista):
for i in range(0, len(lista)):
m = i+menor(lista[i:])
temp = lista[m]
lista[m] = lista[i]
lista[i] = temp
return lista
def menor(lista):
m = 0
for i in range(0, len(lista)):
if lista[i] < lista[m]:
m = i
return m
Insertion
Sort
Pascal LOEWENGUTH en si artículo “Ordenamiento
por inserción·” nos define la forma de funcionar de este algoritmo de la
siguiente manera “Este algoritmo de ordenación consiste en ir insertando un
elemento de la lista ó un arreglo en la parte ordenada de la misma, asumiendo
que el primer elemento es la parte ordenada, el algoritmo ira comparando un
elemento de la parte desordenada de la lista con los elementos de la parte
ordenada, insertando el elemento en la posición correcta dentro de la parte
ordenada, y así sucesivamente hasta obtener la lista ordenada.” Se dice que
este es el que funciona más similar a la manera natural en que los humanos
ordenamos cosas.
Tomando como referencia la presentación de
Mauricio Avilés obtenemos el código de este algoritmo en iteración:
def insertsort(lista):
for i in range(1,len(lista)):
pos = i
while pos > 0 and lista[pos-1] >
lista[i]:
pos -= 1
lista = lista[:pos] +
[lista[i]] + lista[pos:i] + lista[i+1:]
return lista
Quicksort
Este es el último de los algoritmos que
comentaremos en esta entrada. Este cuenta con la particularidad que a
diferencia de los anteriores es bastante eficiente, realizando el ordenamiento
de manera muy rápida sin importar la extensión de la estructura sobre la que se
trabaje. Este algoritmo es originalmente recursivo.
Oscar Campos en su artículo “Implementando
el algoritmo QuickSort” menciona la forma en la que funciona este algoritmo “El
algoritmo QuickSort se basa en la técnica de "divide y vencerás" por
la que, en cada recursión, el problema se divide en sub problemas de menor
tamaño y se resuelven por separado (aplicando la misma técnica) para ser unidos
de nuevo una vez resueltos.”
El código tomado de la presentación de Mauricio
Avilés es el siguiente:
def qsaux(lista):
if len(lista)==1 or len(lista)==0:
return lista
else:
pivote = lista[-1]
menores = [x for x in lista[:-1] if x
< pivote]
mayores = [x for x in lista[:-1] if x
>= pivote]
return qsaux(menores) + [pivote] +
qsaux(mayores)
Luego de
leer y analizar estos 4 algoritmos de ordenamiento podemos ver que todos a
pesar de que cumplen una misma función la cual es ordenar, todas están programadas
de distintas maneras, algunas más eficientes que otras, esto nos deja claro que
en la programación existen miles de formas de resolver un determinado problema,
y lo que siempre se busca es la mejor la más optima, eficaz y eficiente.
Fuentes:
Comentarios
Publicar un comentario