lunes, 23 de febrero de 2015

Métodos de Ordenamiento (Quick Sort, Insertion Sort, Bubble Sort, Merge Sort, Selection Sort) y Búsqueda Binaria - Código en Python

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).
Fue desarrollado en 1945 por John von Neumann .
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.
3.   Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
4.   Mezclar las dos sublistas en una sola lista ordenada

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