Implementación de QuickSort en Python

Amigos programadores, por si alguien para consultar, para realizar un ejercicio o para retarse continuamente, os dejo una implementación de QuickSort en Python. Esta función recibe una lista y desordenada y la deja ordenada. La función devuelve un número que es el total de comparaciones que realiza QuickSort (Este varia segun el pivote usado)

Aqui una descripción en inglés del conocido algoritmo de ordenación : http://en.wikipedia.org/wiki/Quicksort

Se le puede cambiar la función que elige el pivote, ya que esta se pasa como parametro. Os aporto 3 funciones distintas de selección de pivote, asi como ejemplos de uso (Primer elemento, Ultimo elemento, Mediana entre primero, ultimo y el de enmedio)

Algoritmo QuickSort (El parametro funcionPivote se le pasa el nombre de la funcion para elegir pivote)

def qsort(array,ini,fin,nivel,funcionPivote=elegirPivote1):
    if fin-ini <1:
        return 0
    pivote=funcionPivote(array,ini,fin)
    #print "elegimos de pivote el " + str(pivote) + " "+ str(array[pivote])
    j=ini+1
    p=array[pivote]
    array[ini],array[pivote]=array[pivote],array[ini]
    for i in range(ini+1,fin+1):
# no hace falta esto pq siempre es menor que el pivote  if(i!=pivote)):
        if p>array[i]:
            array[i],array[j]=array[j],array[i]
            j=j+1
    array[ini],array[j-1]=array[j-1],array[ini]
    pivote=j-1
    #print j,nivel, array[ini:fin+1]
    comparaciones=fin-ini
    #print nivel, comparaciones, "Pivote nuevo",pivote
    res1=qsort(array,ini,pivote-1,nivel+1,funcionPivote)
    res2=qsort(array,pivote+1,fin,nivel+1,funcionPivote)
    return comparaciones + res1+res2

Tres funciones para elegir pivote :

def elegirPivote1(array,ini,fin):
    return ini

def elegirPivote2(array,ini,fin):
    return fin

def elegirPivote3(array,ini,fin):
    pos1=ini
    pos2=fin

    if((fin+1-ini)%2==0):
        pos3=ini+int((fin+1-ini)/2)-1
    else:
        pos3=ini+int((fin+1-ini)/2)

    if( array[pos1]>= array[pos2] and array[pos1]=array[pos3]):
        return pos1

    if( array[pos2]>= array[pos1] and array[pos2]=array[pos3]):
        return pos2

    if( array[pos3]>= array[pos1] and array[pos3]=array[pos2]):
        return pos3

    return pos1

Ejemplo de uso :

a=[3,4,1,5,6,7,11,2,5,3]
b=[3,4,1,5,6,7,11,2,5,3]
c=[3,4,1,5,6,7,11,2,5,3]

print "Antes de ordenar"
print a
res=qsort(x,0,len(x)-1,1,elegirPivote1)
print "Comparaciones totales pivote 1",res
print a
print "Antes de ordenar"
print b
res=qsort(x,0,len(x)-1,1,elegirPivote1)
print "Comparaciones totales pivote 2",res
print b
print "Antes de ordenar"
print c
res=qsort(x,0,len(x)-1,1,elegirPivote1)
print "Comparaciones totales pivote 3",res
print c

Post to Twitter

This entry was posted in Programacion, Tutoriales / Manuales, Webmaster and tagged , , , , , , , , , . Bookmark the permalink.

One Response to Implementación de QuickSort en Python

  1. meilleur voeux pour 2013, j’espère que sissi va mieux et que l’infirmière n’a pas pris le relais (ce qui arrive souvent ici).

Deja un comentario

Tu dirección de correo electrónico no será publicada.