Algoritmos de Ordenamiento y Ejemplos Prácticos en Python

Merge Sort

def mergesort(x, ip, iu):
    if ip >= iu:
        return
    im = (ip + iu) // 2
    mergesort(x, ip, im)  # Ordenar 1a mitad
    mergesort(x, im + 1, iu)  # Ordenar 2a mitad
    merge(x, ip, im, iu)

Dibujar Árbol (Recursividad)

def dibujar_arbol(t, largo, n):
    if n == 0:
        return
    t.forward(largo)
    t.left(30)
    dibujar_arbol(t, largo // 1.5, n - 1)
    t.right(60)
    dibujar_arbol(t, largo // 1.5, n - 1)
    t.left(30)
    t.back(largo)

Métodos de Ordenamiento

Insertion Sort (Versión 1)

def piolainsertion_sort(lista):
    for i in range(len(lista)):
        for j in range(i, len(lista)):
            if int(lista[j]) < int(lista[i]):
                value = int(lista[i])
                lista[i] = lista[j]
                lista[j] = value
    return lista


print(piolainsertion_sort([6, 3, 8, 2, 5]))

Insertion Sort (Versión 2)

def insertion_sort(x):
    for i in range(1, len(x)):
        aux = x.pop(i)
        j = i
        while j > 0 and x[j - 1] > aux:
            j -= 1

Backtracking: Ubicar Reinas

def ubicarReina(tablero, col):  # reinas
    if col == len(tablero):
        return True  # listo!
    for i in range(0, len(tablero)):
        tablero[i][col] = True
        if valido(tablero):
            if ubicarReina(tablero, col + 1):
                return True
        tablero[i][col] = False
    return False

Selection Sort

def selection_sort(x):
    for ip in range(len(x)):
        minimo = min(x[ip:])
        m = x.index(minimo, ip)
        x[m], x[ip] = x[ip], x[m]


lista = [3, 4, 2, 8, 5, 1, 6, 9, 0]
selection_sort(lista)
print(lista)

Pintar Región (Recursividad)

"""tablero es representado como una listas de listas#solp4
pos es una tupla (i,j), donde i indica la fila y j la columna
color_antiguo y color_nuevo están representados por
numeros enteros"""

def pintar_region(tablero, pos, color_nuevo):
    color_antiguo = tablero[pos[0]][pos[1]]
    # Caso Base
    if tablero[pos[0]][pos[1]] == color_antiguo:
        tablero[pos[0]][pos[1]] = color_nuevo
    else:
        return
    # LLamadas recursivas
    if pos[0] > 0:  # Condicion de los bordes 1
        pos_a = (pos[0] - 1, pos[1])
        pintar_region(tablero, pos_a, color_nuevo)
    if pos[0] < len(tablero) - 1:  # Condicion de los bordes 2
        pos_b = (pos[0] + 1, pos[1])
        pintar_region(tablero, pos_b, color_nuevo)
    if pos[1] > 0:  # Condicion de los bordes 3
        pos_c = (pos[0], pos[1] - 1)
        pintar_region(tablero, pos_c, color_nuevo)
    if pos[1] < len(tablero) - 1:  # Condicion de los bordes 4
        pos_d = (pos[0], pos[1] + 1)
        pintar_region(tablero, pos_d, color_nuevo)
    return tablero


tablero = [
    [1, 0, 0, 0, 1, 0, 1, 1],
    [1, 1, 0, 1, 1, 0, 1, 0],
    [1, 0, 0, 0, 1, 0, 1, 1],
    [1, 0, 0, 1, 1, 0, 1, 1],
    [1, 1, 0, 0, 1, 0, 0, 0],
    [1, 1, 1, 1, 1, 0, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 0, 1, 1]
]
print(pintar_region(tablero, (3, 2), 3))

Blackjack

import random


class Carta():
    def __init__(self, pinta, valor):
        self.pinta = pinta
        self.valor = valor

    def obtener_valor(self):
        if self.valor in ["J", "Q", "K"]:
            return 10
        return self.valor


class Mazo():
    def __init__(self):
        self.mazo = []
        for pinta in ["P", "D", "T", "C"]:
            for valor in range(2, 11):
                c = Carta(pinta, valor)
                self.mazo.append(c)
            for valor in ["J", "Q", "K", "A"]:
                c = Carta(pinta, valor)
                self.mazo.append(c)
        random.shuffle(self.mazo)

    def mostrar_mazo(self):
        for c in m.mazo:
            print(str(c.valor) + str(c.pinta))

    def dar_una_carta(self, jugador):
        jugador.recibir_carta(self.mazo[0])
        self.mazo.remove(self.mazo[0])


class Jugador():
    def __init__(self, nombre):
        self.nombre = nombre
        self.mano = []

    def recibir_carta(self, carta):
        self.mano.append(carta)

    def mostrar_mano(self):
        for c in self.mano:
            print(str(c.valor) + str(c.pinta), end=" ")
        print("-->" + str(self.contar_mano()))

    def contar_mano(self):
        contador = 0
        ases = 0
        for c in self.mano:
            if c.obtener_valor == "A":
                ases += 1
            else:
                contador += c.obtener_valor()
        contador += ases
        ases_usados = 0
        while contador <= 11 and ases_usados < ases:
            contador += 10
            ases_usados += 1
        return contador


m = Mazo()
jugador = Jugador("benja")
PC = Jugador("PC")
m.dar_una_carta(jugador)
m.dar_una_carta(jugador)
m.dar_una_carta(PC)
m.dar_una_carta(PC)
jugador.mostrar_mano()
while jugador.contar_mano() < 21:
    print("¿Qué desea hacer?")
    print("1- Pedir Carta")
    print("2- Plantarse")
    r = int(input())
    if r == 1:
        m.dar_una_carta(jugador)
    if r == 2:
        break
    jugador.mostrar_mano()

Anagramas (Recursividad)

def anagramas(pal, prefijo=""):
    if len(pal) <= 1:
        print(prefijo + pal)
    else:
        for i in range(len(pal)):
            antes = pal[0:i]
            despues = pal[i + 1:]
            anagramas(antes + despues, prefijo + pal[i])


anagramas("primavera")