¿Qué es ordenamiento?
Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.
A continuación se mostrarán los algoritmos de ordenamiento de los elementos de un vector.
QUICKSORT
Es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición.
Recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.
Código en Python:
def partition(list2, first, last):
sred = (first + last)/2
if list2[first] > list2 [sred]:
list2[first], list2[sred] = list2[sred], list2[first]
if list2[first] > list2 [last]:
list2[first], list2[last] = list2[last], list2[first]
if list2[sred] > list2[last]:
list2[sred], list2[last] = list2[last], list2[sred]
list2 [sred], list2 [first] = list2[first], list2[sred]
pivot = first
i = first + 1
j = last
while True:
while i <= last and list2[i] <= list2[pivot]:
i += 1
while j >= first and list2[j] > list2[pivot]:
j -= 1
if i >= j:
break
else:
list2[i], list2[j] = list2[j], list2[i] # swap
list2[j], list2[pivot] = list2[pivot], list2[j] # swap
return j
def quick_sort(list2):
quick_sort_r(list2, 0, len(list2) - 1)
def quick_sort_r(list2 , first, last):
if last > first:
pivot = partition(list2, first, last)
quick_sort_r(list2, first, pivot - 1)
quick_sort_r(list2, pivot + 1, last)
def imprimeLista(lista,tam):
for i in range(0,tam):
print lista[i]
lista=[]
cn=int(raw_input("Cantidad de numeros a ingresar: "))
for i in range(0,cn):
lista.append(int(raw_input("Ingrese numero %d : " % i)))
quick_sort(lista)
imprimeLista(lista,len(lista))
MÉTODO DE LA BURBUJA
Este método consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande el la última posición, una vez acomodado el más grande, prosigue a encontrar y acomodar el siguiente más grande comparando de nuevo los números desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo.
Código en Python
def ordenamientoBurbuja(lista,tam):
for i in range(1,tam):
for j in range(0,tam-i):
if(lista[j] > lista[j+1]):
k = lista[j+1]
lista[j+1] = lista[j]
lista[j] = k;
def imprimeLista(lista,tam):
for i in range(0,tam):
print lista[i]
def leeLista():
lista=[]
cn=int(raw_input("Cantidad de numeros a ingresar: "))
for i in range(0,cn):
lista.append(int(raw_input("Ingrese numero %d : " % i)))
return lista
A=leeLista()
ordenamientoBurbuja(A,len(A))
imprimeLista(A,len(A))
SELECTION SORT
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
Código en Python
def print_lista(lista,tam):
for i in range(0,tam):
print lista[i]
# Ordenamiento por selección
def ordenamiento_porseleccion(lista):
# Itera por todo el array
for posActual in range( len(lista) ):
# Encuentra la posición del valor más pequeño
# Empieza por la posición actual
posMin = posActual
# Escanea de izquierda a derecha (hasta el final de la lista)
for escanPos in range(posActual+1, len(lista) ):
# Es ésta la posición más pequeña?
if lista[escanPos] < lista[posMin]:
# Si lo es, la marcamos como la más pequeña
posMin = escanPos
# intercambia los dos valores
temp = lista[posMin]
lista[posMin] = lista[posActual]
lista[posActual] = temp
# Creamos una lista con números aleatorios
lista=[]
cn=int(raw_input("Cantidad de numeros a ingresar: "))
for i in range(0,cn):
lista.append(int(raw_input("Ingrese numero %d : " % i)))
ordenamiento_porseleccion(lista)
print_lista(lista,len(lista))
INSERTION SORT
La idea de 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. Para explicarlo mejor nos basaremos en el siguiente enunciado:
“Para cada elemento de la lista después del primero, comparar los elementos con los anteriores desplazando una posición a la derecha a todos los elementos anteriores que cumplan con la comparación y luego colocar el elemento en la posición del último elemento anterior desplazado.”
Ahora veamos un ejemplo ordenando de menor a mayor (ascendentemente) la siguiente lista de números:
7, 3, 10, 1, 9
La lista tiene 5 elementos, con lo cual tendremos que recorrer la lista 4 veces. Ya que la comparación se hará desde el segundo elemento de la lista, es decir recorremos la lista después del primer elemento hasta el último.
1er. recorrido: Se toma 3 para comparar con los elementos anteriores. Los elementos anteriores son: 7
3
| ||||
7
|
10
|
1
|
9
|
La comparación 3<7, es verdadera, entonces desplazamos el 7 una posición a la derecha.
3
| ||||
7
|
10
|
1
|
9
|
Al no haber más elementos a comparar colocamos el 3 en la posición del último elemento desplazado.
3
|
7
|
10
|
1
|
9
|
2do. recorrido: Se toma 10 para comparar con los elementos anteriores. Los elementos anteriores son: 3, 7
10
| ||||
3
|
7
|
1
|
9
|
La comparación 10<7, es falsa, entonces no desplazamos nada y se termina este recorrido.
3
|
7
|
10
|
1
|
9
|
3er. recorrido: Se toma 1 para comparar con los elementos anteriores. Los elementos anteriores son: 3, 7, 10
1
| ||||
3
|
7
|
10
|
9
|
La comparación 1<10, es verdadera, entonces desplazamos el 10 una posición a la derecha.
1
| ||||
3
|
7
|
10
|
9
|
La comparación 1<7, es verdadera, entonces desplazamos el 7 una posición a la derecha.
1
| ||||
3
|
7
|
10
|
9
|
La comparación 1<3, es verdadera, entonces desplazamos el 3 una posición a la derecha.
1
| ||||
3
|
7
|
10
|
9
|
Al no haber más elementos a comparar colocamos el 1 en la posición del último elemento desplazado.
1
|
3
|
7
|
10
|
9
|
4to. recorrido: Se toma 9 para comparar con los elementos anteriores. Los elementos anteriores son: 1, 3, 7, 10
9
| ||||
1
|
3
|
7
|
10
|
La comparación 9<10 es verdadera, entonces desplazamos el 10 una posición a la derecha.
9
| ||||
1
|
3
|
7
|
10
|
La comparación 9<7 es falsa, entonces no desplazamos nada y se termina este recorrido, colocando el 9 en la posición del último elemento desplazado.
1
|
3
|
7
|
9
|
10
|
Código Python
def insertion_sort(list2):
for i in range(1, len(list2)):
save = list2[i]
j = i
while j > 0 and list2[j - 1] > save:
list2[j] = list2[j - 1]
j -= 1
list2[j] = save
def imprimeLista(lista,tam):
for i in range(0,tam):
print lista[i]
lista=[]
cn=int(raw_input("Cantidad de numeros a ingresar: "))
for i in range(0,cn):
lista.append(int(raw_input("Ingrese numero %d : " % i)))
insertion_sort(lista)
imprimeLista(lista,len(lista))
Merge Sort
El algoritmo de ordenamiento por mezcla es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás
Si el vector tiene más de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace una intercalación de las dos mitades ordenadas.
Código Python:
def merge_sort(list2):
merge_sort_r(list2, 0, len(list2) -1)
# merge sort recursive (used by merge_sort)
def merge_sort_r(list2, first, last):
if first < last:
sred = (first + last)/2
merge_sort_r(list2, first, sred)
merge_sort_r(list2, sred + 1, last)
merge(list2, first, last, sred)
# merge (used by merge_sort_r)
def merge(list2, first, last, sred):
helper_list = []
i = first
j = sred + 1
while i <= sred and j <= last:
if list2 [i] <= list2 [j]:
helper_list.append(list2[i])
i += 1
else:
helper_list.append(list2 [j])
j += 1
while i <= sred:
helper_list.append(list2[i])
i +=1
while j <= last:
helper_list.append(list2[j])
j += 1
for k in range(0, last - first + 1):
list2[first + k] = helper_list [k]
def imprimeLista(lista,tam):
for i in range(0,tam):
print lista[i]
lista=[]
cn=int(raw_input("Cantidad de numeros a ingresar: "))
for i in range(0,cn):
lista.append(int(raw_input("Ingrese numero %d : " % i)))
merge_sort(lista)
imprimeLista(lista,len(lista))
Referencias
http://adrorodri.blogspot.mx/2012/09/metodo-de-ordenacion-merge-sort.html
http://www.conoce3000.com/html/espaniol/Libros/PascalConFreePascal/Cap08-02-Ordenamiento%20por%20insercion%20%28Insertion%20sort%29.php
http://es.wikipedia.org/wiki/Ordenamiento_por_selecci%C3%B3n
http://www.estructuradedatos.galeon.com/burbujatext.htm
http://www.angelfire.com/wy2/est_info/quicksort.html
https://www.daniweb.com/software-development/python/code/216689/sorting-algorithms-in-python
https://saforas.wordpress.com/2011/01/24/codigo-python-ordenamiento-burbuja/
http://www.monografias.com/trabajos/algordenam/algordenam.shtml#ixzz3Sd09L7N6
No hay comentarios.:
Publicar un comentario