Algoritmos de Ordenamiento con Python

Bubble  sort

Este método consiste en verificando 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.

#Bubble Sort

elementos = [1,3,5,4,7,9,8,6]

numero = len(elementos)

i= 0

while (i < numero):

    j = i

    while (j < numero):

        if(elementos[i] > elementos[j]):

            temp = elementos[i]

            elementos[i] = elementos[j]

            elementos[j] = temp

        j= j+1

    i=i+1

for elemento in elementos:

    print elemento

Selection sort

Consiste en encontrar el menor de todos los elementos de la lista e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenar toda la lista.

#Selection Sort

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

selectionsort(A,len(A))

imprimeLista(A,len(A))

Insertion sort

Paso 0: Partimos de la siguiente lista.3 2 -1 5 0 2

Paso 1: Considerar el segundo elemento de la lista, y ordenarlo respecto al primero, desplazándolo hasta la posición correcta, si corresponde.

2 3 -1 5 0 2          Se desplaza el valor 2 antes de 3. 

Paso 2: considerar el tercer elemento de la lista, y ordenarlo respecto del primero y el segundo, desplazándolo hasta la posición correcta, si corresponde.

-1 2 3 5 0 2          Se desplaza el valor -1 antes de 2 y de 3

Paso 3: Considerar el cuarto elemento de la lista, y ordenarlo respecto del primero, el segundo y el tercero, desplazándolo hasta la posición correcta, si corresponde.

-1 2 3 5 0 2

El 5 está correctamente ubicado respecto de -1, 2 y 3 (como el segmento hasta la tercera posición esta ordenado, basta con comparar con el tercer elemento del segmento para verificarlo).  

Paso N-1:

-1 0 2 3 5 2 Todos los elementos excepto el ante-último ya se encuentran ordenados.

Paso N: Considerar el N–ésimo elemento de la lista, y ordenarlo respecto del segmento formado por el primero hasta N - 1-ésim, desplazándolo hasta la posición correcta, si corresponde.

-1 0 2 2 3 5           Se dezplaza el valor 2 antes de 3 y de 5.

#Insertion Sort

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 imprimeLista(lista,tam):

    for i in range(0,tam):

        print lista[i]

def leeLista():

    lista=[]

    cn=int(raw_input("Dame la cantidad de numeros a ingresar: "))

    for i in range(0,cn):

        lista.append(int(raw_input("Ingrese numero %d : " % i)))

    return lista

A=leeLista()

insercionDirecta(A,len(A))

imprimeLista(A,len(A))

Merge sort

       I.    Si la lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer. De lo contrario hacer lo siguiente:

      II.    Dividir la lista al medio, formando dos sublistas de (aproximadamente) el mismo tamaño cada una.

     III.    Ordenar cada una de esas dos sublistas (usando este mismo método).

     IV.    Una vez que se ordenaron ambas sublistas, intercalarlas de manera ordenada.

#Merge Sort

def merge_sort(lista):

      if len(lista) < 2:

          return lista

      medio = len(lista) / 2

      izq = merge_sort(lista[:medio])

     der = merge_sort(lista[medio:])

     return merge(izq, der)

def merge(lista1, lista2):

      i, j = 0, 0

      resultado = []

      while(i < len(lista1) and j < len(lista2)):

             if (lista1[i] < lista2[j]):

                 resultado.append(lista1[i])

                 i += 1

                 else:

                       resultado.append(lista2[j]) 

                       j += 1

     resultado += lista1[i:]

     resultado += lista2[j:]

     return resultado

print "=============MERGESORT============="

lista=[]

x=int(raw_input("INGRESE EL NUMERO DE DATOS QUE DESEA ORDENAR:"))

i=1

while (i<=x):

       n=int(raw_input("INGRESE DATO:"))

       lista.append(n)

       i += 1

       lista = merge_sort(lista)

       

print "SU LISTA ORDENADA CON EL METODO MERGE SORT ES:",  lista

Quick sort

      I.    Si la lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer. De lo contrario hacer lo siguiente:

     II.   Tomar un elemento de la lista (por ejemplo el primero) al que llamaremos pivote y armar a partir de esa lista tres sublistas: la de todos los elementos de la lista menores al pivote, la formada sólo por el pivote, y la de los elementos mayores o iguales al pivote, pero sin contarlo al pivote.

     III.   Ordenar cada una de esas tres sublistas (usando este mismo método).

     IV. Concatenar las tres sublistas ya ordenadas.

#Quick Sort

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("Cuantos elementos desea Ordenar: "))

for i in range(0,cn):

     lista.append(int(raw_input("Ingrese numero %d : " % i)))

return lista

D=leeLista()

quicksort(D,0,len(D)-1)

imprimeLista(D,len(D))