Python

import collections

def encontrar_lugar_para_inserir(numero, listas):
    for nome, lista in listas.items():
        if not lista:
            return nome, 'fim'
        if numero < lista[0]:
            return nome, 'inicio'
        if numero > lista[-1]:
            return nome, 'fim'
    return None, None

def mover_entre_listas_para_abrir_espaco(listas, historico):
    listas_ativas = {k: v for k, v in listas.items() if v}
    if len(listas_ativas) < 2:
        return False
    nome_destino = max(listas_ativas, key=lambda k: listas_ativas[k][0])
    lista_destino = listas_ativas[nome_destino]
    candidatos = []
    for nome_origem, lista_origem in listas_ativas.items():
        if nome_origem == nome_destino:
            continue
        num = lista_origem[0]
        if num < lista_destino[0] and (nome_destino, nome_origem, num) not in historico:
            candidatos.append((nome_origem, num, 'inicio'))
        elif num > lista_destino[-1] and (nome_destino, nome_origem, num) not in historico:
            candidatos.append((nome_origem, num, 'fim'))
    if not candidatos:
        return False
    origem, num, pos = min(candidatos, key=lambda c: abs(c[1] - lista_destino[0]))
    listas[origem].pop(0)
    if pos == 'inicio':
        lista_destino.insert(0, num)
    else:
        lista_destino.append(num)
    historico.add((origem, nome_destino, num))
    return True

def consolidar_listas(listas):
    historico = set()
    while sum(1 for l in listas.values() if l) > 1:
        if not mover_entre_listas_para_abrir_espaco(listas, historico):
            break
    for l in listas.values():
        if l: return l
    return []

# Demonstração
A = [3, 5, 6, 2, 4, 7, 8, 9, 13, 1, 12, 11, 10]
listas = collections.OrderedDict([('B', []), ('C', []), ('D', [])])
while A:
    num = A.pop(0)
    nome, pos = encontrar_lugar_para_inserir(num, listas)
    if nome:
        if pos == 'inicio': listas[nome].insert(0, num)
        else: listas[nome].append(num)
    else:
        mover_entre_listas_para_abrir_espaco(listas, set())

resultado = consolidar_listas(listas)
print("Lista final ordenada:", resultado)

# Supondo que a função está dentro de uma classe com self._a (o array)
# e self.swap(i, j) como no exercício original.

def bidirectionalBubbleSort(self):
    left_index = 0
    right_index = len(self._a) - 1
    swapped = True

    while swapped:
        # Primeiro, passamos da esquerda para a direita (Bubble Sort padrão)
        swapped = False
        for i in range(left_index, right_index):
            if self._a[i] > self._a[i+1]:
                self.swap(i, i+1)
                swapped = True
        
        # Se nenhuma troca ocorreu, o array está ordenado.
        if not swapped:
            break

        # O elemento na `right_index` agora é o maior, então podemos diminuir o limite
        right_index = right_index - 1

        # Agora, passamos da direita para a esquerda, movendo o menor para o início
        swapped = False
        for i in range(right_index, left_index, -1):
            if self._a[i] < self._a[i-1]:
                self.swap(i, i-1)
                swapped = True
        
        # O elemento na `left_index` agora é o menor, podemos aumentar o limite
        left_index = left_index + 1

# Exemplo de como a classe poderia ser para teste:
class Sorter:
    def __init__(self, arr):
        self._a = arr

    def swap(self, i, j):
        self._a[i], self._a[j] = self._a[j], self._a[i]
        
    bidirectionalBubbleSort = bidirectionalBubbleSort # Atribui a função à classe

# Teste
my_array = [5, 1, 4, 2, 8, 0, 3, 9, 6, 7]
sorter = Sorter(my_array)
sorter.bidirectionalBubbleSort()
print(sorter._a)

def bubble_sort_numeros(lista):
    n = len(lista)
    # Percorre todos os elementos da lista
    for i in range(n):
        # A flag `trocou` otimiza o algoritmo. Se não houver trocas em uma passagem,
        # a lista já está ordenada e podemos parar.
        trocou = False
        
        # A última i posições já estão no lugar certo
        for j in range(0, n-i-1):
            # Percorre a lista da esquerda para a direita
            # Troca se o elemento encontrado for maior que o próximo
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]
                trocou = True
        
        if not trocou:
            break
    return lista

# --- Testes da Função ---
lista1 = [64, 34, 25, 12, 22, 11, 90]
lista2 = [5, 1, 4, 2, 8]
lista3 = [1, 2, 3, 4, 5] # Já ordenada
lista4 = [9, 8, 7, 6, 5] # Ordem reversa
lista5 = [] # Lista vazia

print(f"Lista original 1: {lista1}")
print(f"Lista ordenada 1: {bubble_sort_numeros(lista1.copy())}\n")

print(f"Lista original 2: {lista2}")
print(f"Lista ordenada 2: {bubble_sort_numeros(lista2.copy())}\n")

print(f"Lista original 3: {lista3}")
print(f"Lista ordenada 3: {bubble_sort_numeros(lista3.copy())}\n")

print(f"Lista original 4: {lista4}")
print(f"Lista ordenada 4: {bubble_sort_numeros(lista4.copy())}\n")

print(f"Lista original 5: {lista5}")
print(f"Lista ordenada 5: {bubble_sort_numeros(lista5.copy())}\n")

# A função é exatamente a mesma do exercício anterior.
# Vamos renomeá-la para clareza.
def bubble_sort_strings(lista):
    n = len(lista)
    for i in range(n):
        trocou = False
        for j in range(0, n-i-1):
            # A única linha que importa: a comparação.
            # Em Python, `>` funciona para strings alfabeticamente.
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]
                trocou = True
        
        if not trocou:
            break
    return lista

# --- Testes da Função com Strings ---
lista_frutas = ["banana", "maçã", "uva", "abacaxi", "laranja"]
lista_nomes = ["Carlos", "Beatriz", "Ana", "Daniel"]
lista_mista = ["Python", "java", "C++", "python"] # 'p' minúsculo vem depois de 'J' maiúsculo

print(f"Lista original de frutas: {lista_frutas}")
print(f"Lista ordenada de frutas: {bubble_sort_strings(lista_frutas.copy())}\n")

print(f"Lista original de nomes: {lista_nomes}")
print(f"Lista ordenada de nomes: {bubble_sort_strings(lista_nomes.copy())}\n")

print(f"Lista original mista: {lista_mista}")
print(f"Lista ordenada mista: {bubble_sort_strings(lista_mista.copy())}\n")