Metodos de Ordenacion Practica #1

#Jaqueline Ventura Salinas
#Programacion Paralela
#MetodoS de Ordenación

def Burbuja(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 selectionsort(lista,tam):
    for i in range(0,tam-1):
        min=i
        for j in range(i+1,tam):
            if lista[min] > lista[j]:
                min=j
        aux=lista[min]
        lista[min]=lista[i]
        lista[i]=aux
               
def insercionDirecta(lista,tam):
    for i in range(1,tam):
        v=lista[i]
        j=i-1
        while j >= 0 and lista[j] > v:
            lista[j+1] = lista[j]
            j=j-1
        lista[j+1]=v
       


def quicksort(lista,izq,der):
    i=izq
    j=der
    x=lista[(izq + der)/2]

    while( i <= j ):
        while lista[i]<x and j<=der:
            i=i+1
        while x<lista[j] and j>izq:
            j=j-1
        if i<=j:
            aux = lista[i]; lista[i] = lista[j]; lista[j] = aux;
            i=i+1;  j=j-1;

        if izq < j:
            quicksort( lista, izq, j );
    if i < der:
        quicksort( lista, i, der );

def mergeSort(lista):
    print("Splitting ",lista)
    if len(lista)>1:
        mid = len(lista)//2
        lefthalf = lista[:mid]
        righthalf = lista[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                lista[k]=lefthalf[i]
                i=i+1
            else:
                lista[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            lista[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            lista[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",lista)




       
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()
print "Metodo Burbuja"
Burbuja(A,len(A))
imprimeLista(A,len(A))
print "Metodo Selección"
selectionsort(A,len(A))
imprimeLista(A,len(A))
print "Metodo Inserción"
insercionDirecta(A,len(A))
imprimeLista(A,len(A))
print "Metodo Quick sort"
quicksort(A,0,len(A)-1)
imprimeLista(A,len(A))
print "Metodo Merge sort"
mergeSort(A)
print(A)


# basado en :
#https://saforas.wordpress.com/2011/01/24/metodos-de-ordenamiento-hechos-en-python/
#http://ict.udlap.mx/people/ingrid/Clases/IS211/Ordenar.html