IMPLEMENTACIÓN DE LOS MÉTODOS DE ORDENACIÓN EN PYTHON

Share:



Hola amigos tiempo atrás realice un post acerca delos diferentes métodos de ordenación  y su respectivo análisis de complejidad con su implementacion en java, si desean verlo pueden pasarse por la siguiente publicación:

En la presente publicación comparto con ustedes la implementación de estos métodos pero en python, un lenguaje de programación con el cual comencé a trabajar y me vi con la necesidad de implementar estos métodos 

Método de ordenamiento  Burbuja:

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))


Método de ordenamiento  Shell Sort:
def ordenShell(lista,tam):
    inc=1
    for inc in range(1,tam,inc*3+1):
        while inc>0:
            for i in range(inc,tam):
                j=i
                temp=lista[i]
                while j>=inc and lista[j-inc]>temp:
                    lista[j]=lista[j-inc]
                    j=j-inc
                lista[j]=temp
            inc=inc/2
 
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

Método de ordenamiento  QuickSort:
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 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()
quicksort(A,0,len(A)-1)
imprimeLista(A,len(A))

Método de ordenamiento  QuickSort:
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 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()
quicksort(A,0,len(A)-1)
imprimeLista(A,len(A))

Método de ordenamiento  Insercion:
def insercion(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 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()
insercion(A,len(A))
imprimeLista(A,len(A))

Método de ordenamiento  HeapSort:
def heapsort(lista,tam):
    for k in range(tam-1,-1,-1):
        for i in range(0,k):
            item=lista[i]
            j=(i+1)/2
            while j>=0 and lista[j]< item:
                lista[i]=lista[j]
                i=j
                j=j/2
            lista[i]=item
        temp=lista[0];
    lista[0]=lista[k];
    lista[k]=temp;
 
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()
heapsort(A,len(A))
imprimeLista(A,len(A))

Método de ordenamiento  MergeSort:
def merge_sort(lista): 
    n = len(lista) 
    if(n == 1): return lista 
    izquierda = merge_sort(lista[:(n/2)]) 
    derecha = merge_sort(lista[(n/2):]) 
    return merge(izquierda, derecha) 
 
def merge(izquierda, derecha): 
    resultado = [] 
    i = 0 
    j = 0 
    len_izquierda = len(izquierda) 
    len_derecha = len(derecha) 
 
    while(i < len_izquierda or j < len_derecha): 
        if(i >= len_izquierda): 
            resultado.append(derecha[j]) 
            j = j + 1 
        elif(j >= len_derecha): 
            resultado.append(izquierda[i]) 
            i = i + 1 
        elif(izquierda[i] < derecha[j]): 
            resultado.append(izquierda[i]) 
            i = i + 1 
        else: 
            resultado.append(derecha[j]) 
            j = j + 1 
    return resultado 

def imprimeLista(lista):
    for i in range(0,len(lista)):
        print (str(lista[i]))
 
def leeLista():
    lista=[]
    cn=int(input("Cantidad de numeros a ingresar: "))
    for i in range(0,cn):
        lista.append(int(input("Ingrese numero %d : " % i)))
    return lista
 
A=leeLista()
merge_sort(A)
imprimeLista(A)

No hay comentarios