Quicksort avec Python

Question

Je suis totalement novice en python et j'essaie d'y implémenter quicksort. Quelqu'un pourrait-il m'aider à compléter mon code ?

Je ne sais pas comment concaténer les trois tableaux et les imprimer.

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
            sort(less)
            sort(pivot)
            sort(greater)

Answer 1

Il existe déjà de nombreuses réponses à cette question, mais je pense que cette approche est la mise en œuvre la plus propre :

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    pivots = [x for x in arr if x == arr[0]]
    lesser = quicksort([x for x in arr if x < arr[0]])
    greater = quicksort([x for x in arr if x > arr[0]])

    return lesser + pivots + greater

Vous pouvez bien sûr éviter de tout stocker dans des variables et les retourner directement comme ceci :

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    return quicksort([x for x in arr if x < arr[0]]) \
        + [x for x in arr if x == arr[0]] \
        + quicksort([x for x in arr if x > arr[0]])

Answer 2

L'approche fonctionnelle :

def qsort(lst):
    if len(lst) < 2:
        return lst

    pivot = lst[0]
    left = list(filter(lambda x: x <= pivot, lst[1:]))
    right = list(filter(lambda x: x > pivot, lst[1:]))

    return qsort(left) + [pivot] + qsort(right)

Answer 3

Voici une version du quicksort utilisant le schéma de partition de Hoare et avec moins d'échanges et de variables locales.

def quicksort(array):
    qsort(array, 0, len(array)-1)

def qsort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        qsort(A, lo, p)
        qsort(A, p + 1, hi)

def partition(A, lo, hi):
    pivot = A[lo]
    i, j = lo-1, hi+1
    while True:
      i += 1
      j -= 1
      while(A[i] < pivot): i+= 1
      while(A[j] > pivot ): j-= 1

      if i >= j: 
          return j

      A[i], A[j] = A[j], A[i]

test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)

Answer 4

Mise en œuvre facile à partir d'algorithmes de grokking

def quicksort(arr):
    if len(arr) < 2:
        return arr #base case
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot] 
        more = [i for i in arr[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(more)

Answer 5

Approche de la programmation fonctionnelle

smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []

print qsort([3,1,4,2,5]) == [1,2,3,4,5]