UNIVERSIDAD AUTONOMA DEL ESTADO DE
MEXICO
FACULTAD DE INGENIERIA
DIVISION DE INGENIERIA EN COMPUTACION
METODOS DE ORDENAMIENTO
(CODIGO EN PYTHON)
PROFESOR: ING ELFEGO GUTIERREZ OCAMPO
ALUMNO: EDUARDO MANUEL FLORES VERA
NO. CUENTA: 0914132
FECHA:ABRIL DE 2014
BUBBLE SORT
La Ordenación 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 el
más sencillo de implementar.
Éste algoritmo es esencialmente un algoritmo de fuerza
bruta lógica
CODIGO EN
PYTHON
#Flores
Vera Eduardo Manuel
importmath
import
os
#Definicion
de Funciones
defbubbleSort(b):
forpassnum in range(len(b)-1,0,-1):
for i in range(passnum):
if b[i]>b[i+1]:
temp = b[i]
b[i] = b[i+1]
b[i+1] = temp
#Programa Principal
b = [54,26,93,17,77,31,44,55,20]
bubbleSort(b)
print(b)
SELECTION SORT
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O
operaciones para
ordenar una lista de n elementos.
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
CODIGO EN PYTHON
#Flores
Vera Eduardo Manuel
import
os
#Definicion
de Funciones
defselectionsort(a):
for i in range(len(a)):
mini = min(a[i:])
min_index = a[i:].index(mini)
a[i + min_index] = a[i]
a[i] = mini
return a
#Programa Principal
print
'===================SELECTIONSORT================='
a=[]
x=int(raw_input("INGRESE
EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))
i=1
while (i<=x):
n=int(raw_input("INGRESE DATO:"))
a.append(n)
i+=1
a=selectionsort(a)
print a
QUICKSORT
El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el
científico británico en computación C. A. R. Hoare basado en la técnica
de divide y vencerás, que permite, en promedio, ordenar nelementos en un tiempo proporcional a n log n.
El algoritmo trabaja
de la siguiente forma:
·
Elegir un elemento de la lista 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.
CODIGO EN
PYTHON
#Flores
Vera Eduardo Manuel
import
os
importmath
#Definicion
de Funciones
defquicksort(cadena):
menor
= []
igual
= []
mayor
= []
iflen(cadena)
> 1:
pivot
= cadena[0]
for
x in cadena:
if x < pivot:
menor.append(x)
if x == pivot:
igual.append(x)
if x > pivot:
mayor.append(x)
returnquicksort(menor)+quicksort(igual)+quicksort(mayor) # se realiza la suma para juntar las
cadenas(listas)
else: # cuando queda un solo elemento en la cadena(lista) entonces hay que regresarlo
return
cadena
#Programa
principal
print
"=========================QUICKSORT========================="
cadena=[]
x=int(raw_input("INGRESE
EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))
i=1
while (i<=x):
n=int(raw_input("INGRESE DATO:"))
cadena.append(n)
i+=1
cadena
= quicksort(cadena)
print
"SU LISTA ORDENADA CON EL METODO QUICKSORT ES:", cadena
INSERTSORT
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
CODIGO EN
PYTHON
#Flores
Vera Eduardo Manuel
import
os
importmath
#Definicion
de Funciones
definsertion_sort(a):
for i in range(1, len(a)):
v = a[i]
j = i
while a[j-1] > v and j>=1:
a[j] = a[j-1]
j -=
1
a[j] = v
return a
#Programa Principal
print "=======================INSERTSORT=================="
a=[]
x=int(raw_input("INGRESE
EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))
i=1
while (i<=x):
n=int(raw_input("INGRESE DATO:"))
a.append(n)
i+=1
a=insertion_sort(a)
print
"SU LISTA ORDENADA CON EL METODO INSERTSORT ES:", a
os.system('pause')
MERGESORT
El algoritmo de ordenamiento
por mezcla (merge sort en inglés) es un algoritmo de ordenamiento
externo estable basado
en la técnica divide y vencerás. Es de complejidad O(n log n).
Conceptualmente, el ordenamiento por
mezcla funciona de la siguiente manera:
1. Si la longitud de la lista es 0 ó 1,
entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos
sublistas de aproximadamente la mitad del tamaño.
CODIGO EN PYTHON
def merge_sort(numbers):
|
|
n = len(numbers)
|
if(n == 1): return numbers
|
|
left = merge_sort(numbers[:(n/2)])
|
right = merge_sort(numbers[(n/2):])
|
|
return merge(left,
right)
|
|
def merge(left, right):
|
result = []
|
i = 0
|
j = 0
|
len_left = len(left)
|
len_right = len(right)
|
|
while(i < len_left or j < len_right):
|
if(i >=
len_left):
|
result.append(right[j])
|
j = j + 1
|
elif(j >=
len_right):
|
result.append(left[i])
|
i = i + 1
|
elif(left[i] < right[j]):
|
result.append(left[i])
|
i = i + 1
|
else:
|
result.append(right[j])
|
j = j + 1
|
|
return result
|
|
def test(expected, actual):
|
sort = merge_sort(actual)
|
assert expected ==
sort
|
print actual, "is sort
as", sort
|
|
test([1], [1])
|
test([1, 2], [2, 1])
|
test([1, 2, 3], [2, 3, 1])
|
test([1, 2, 3, 4], [2, 3, 1, 4])
|
test([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [10, 6, 2, 3, 5, 1, 7, 4, 9, 8])
BINARY TREE SORT
El ordenamiento con árbol binario es un algoritmo
de ordenamiento, el cual ordena sus elementos haciendo uso de unárbol
binario de búsqueda. Se basa en ir construyendo poco a poco el árbol binario introduciendo
cada uno de los elementos, los cuales quedarán ya ordenados. Después, se
obtiene la lista de los elementos ordenados recorriendo el árbol en inorden
CODIGO EN PYTHON
#Flores Vera Eduardo
Manuel
import math
import os
#definicion de
funciones
class Node: def __init__(self,data): self.left = None self.right = None self.data = data
class BinaryTree(Node): def __init__(self): self.root = None
def addNode(self,data): return Node(data)
def insert(self,root,data): if(root == None): root = self.addNode(data) else: if(data <= root.data): root.left = self.insert(root.left,data) else: root.right = self.insert(root.right,data) return root
def PreOrder(self,root): if root == None: pass else: print(root.data) self.PreOrder(root.left) self.PreOrder(root.right)
a = BinaryTree() root = a.addNode(2) #root = None a.insert(root,4) a.insert(root,34) a.insert(root,45) a.insert(root,46) a.insert(root,41) a.insert(root,48) a.PreOrder(root) |
No hay comentarios.:
Publicar un comentario