16.7 Algoritmo de ordenación quicksort

= = =

Primero, explicándolo paso a paso...

# *-* coding: utf-8 *-*

import random

def quicksort(L, first, last):
    # definimos los índices y calculamos el pivote
    i = first
    j = last    
    pivote = (L[i] + L[j]) / 2
    print "PIVOTE: ",str(pivote)

    # iteramos hasta que i no sea menor que j
    while i < j:
        # iteramos mientras que el valor de L[i] sea menor que pivote
        while L[i] < pivote:
            # Incrementamos el índice
            i+=1
            print "i: ",str(i)
        # iteramos mientras que el valor de L[j] sea mayor que pivote
        while L[j] > pivote:
            # decrementamos el índice
            j-=1
            print "j: ",str(j)
        # si i es menor o igual que j significa que los índices se han cruzado
        print "i: ",str(i), ", j: ",str(j), " --> números: ", L
        if i<=j:
            # creamos una variable temporal para guardar el valor de L[j]
            x = L[j]
            # intercambiamos los valores de L[j] y L[i]
            L[j] = L[i]
            L[i] = x
            # incrementamos y decrementamos i y j respectivamente
            i+=1
            j-=1
        print "L cambiado: ",L,"añadidos i e j: ",str(i),",",str(j)

    # si first es menor que j mantenemos la recursividad
    # if first < j:
    #    L = quicksort(L, first, j)
    # si last es mayor que i mantenemos la recursividad
    # if last > i:
    #    L = quicksort(L, i, last)

    # devolvemos la lista ordenada
    return L
    

# Genero un vector con 100 elementos colocados en posiciones aleatorias
"""
misNumeros = []
for i in range(1,11):
    longitud = len(misNumeros)
    misNumeros.insert(random.randint(0,longitud),i)"""
    
misNumeros = [8,4,7,5,3,2,1,6]

print "Mis números: ",misNumeros
print "= = = "
print quicksort(misNumeros,0,len(misNumeros)-1)

El método quicksort completo

# *-* coding: utf-8 *-*

import random

def quicksort(L, first, last):
    # definimos los índices y calculamos el pivote
    i = first
    j = last    
    pivote = (L[i] + L[j]) / 2
    # print "PIVOTE: ",str(pivote)

    # iteramos hasta que i no sea menor que j
    while i < j:
        # iteramos mientras que el valor de L[i] sea menor que pivote
        while L[i] < pivote:
            # Incrementamos el índice
            i+=1
            # print "i: ",str(i)
        # iteramos mientras que el valor de L[j] sea mayor que pivote
        while L[j] > pivote:
            # decrementamos el índice
            j-=1
            # print "j: ",str(j)
        # si i es menor o igual que j significa que los índices se han cruzado
        # print "i: ",str(i), ", j: ",str(j), " --> números: ", L
        if i<=j:
            # creamos una variable temporal para guardar el valor de L[j]
            x = L[j]
            # intercambiamos los valores de L[j] y L[i]
            L[j] = L[i]
            L[i] = x
            # incrementamos y decrementamos i y j respectivamente
            i+=1
            j-=1
        # print "L cambiado: ",L,"añadidos i e j: ",str(i),",",str(j)
    
    # si first es menor que j mantenemos la recursividad
    if first < j:
        L = quicksort(L, first, j)
    # si last es mayor que i mantenemos la recursividad
    if last > i:
        L = quicksort(L, i, last)

    # devolvemos la lista ordenada
    return L
    

# Genero un vector con 100 elementos colocados en posiciones aleatorias

misNumeros = []
for i in range(1,11):
    longitud = len(misNumeros)
    misNumeros.insert(random.randint(0,longitud),i)

# misNumeros = [8,4,7,5,3,2,1,6]

print "Mis números: ",misNumeros
print "= = = "
print quicksort(misNumeros,0,len(misNumeros)-1)

16.6 Algoritmo de ordenación por burbuja

 = = =

# *-* coding: utf-8 *-*

import random

# =============================================================
# ALGORITMO DE ORDENACION POR INSERCIÓN DIRECTA
# =============================================================

# Genero un vector con 100 elementos colocados en posiciones aleatorias
misNumeros = []
for i in range(1,101):
    longitud = len(misNumeros)
    misNumeros.insert(random.randint(0,longitud),i)

# print misNumeros

# ================================
# Ordenacion por insercion directa
# ================================

misNumerosID = misNumeros[:] #COPIO los valores del array
indice=len(misNumerosID)-1 # corresponde a la última posición del array
pivote = 0 # corresponde al pivote, que puede ser el último elemento del array

print "ANTES: ",misNumerosID
# print "Longitud del elemento: ",str(len(misNumerosID))
# print "Rango negativo: ",str(range(len(misNumerosID),0,-1))

for i in range(indice,-1,-1): # desde el último índice, al 0 (límite inferior -1), hacia atrás, de uno en uno
    for j in range(1,i+1): # desde la segunda posición [1] hasta el último índice. Límite superior i+1
        if misNumerosID[j]<misNumerosID[j-1]:
            pivote = misNumerosID[j]
            misNumerosID[j]=misNumerosID[j-1]
            misNumerosID[j-1]=pivote
            pivote=0

print " = = = "
print "DESPUÉS: ",misNumerosID