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)
0 comentarios: