Drops: Quicksort em Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

from typing import List


def quicksort(l: List):
    """
    Recebe uma lista de elementos e devolve eles ordenados
    """

    # Caso base! Nunca se esqueça disso em funções recursivas@
    if not len(l):
        return l

    # Escolhemos um pivot, removemos ele da lista!
    # Reduzir a entrada também é essêncial!
    pivot = l.pop(0)

    # Separamos os elementos menores
    lower = [e for e in l if e <= pivot]
    # Separamos os maiores
    uppper = [e for e in l if e > pivot]

    # Os menores ficam na esquerda do pivo
    # Os maiores ficam na direita
    # Ai acontece a magia da recursão... 
    # Ordedamos os menores e os maiores com a mesma função.
    return quicksort(lower) + [pivot] + quicksort(uppper)


def main():
    elems = [3,2,3,6,7,4,2,-1]

    print(quicksort(elems))


if __name__ == '__main__':
    main()