Проблема с quicksort и python

Question

Я пишу программу python, которая играет в покер для класса, и мне нужно отсортировать список из пяти карточных рук. У меня есть функция wins(), которая берет две руки и возвращает True, если первый из них бьет второй, False, если это не так. Я написал реализацию quicksort, чтобы отсортировать список рук, и я заметил, что это занимает гораздо больше времени, чем ожидалось, поэтому я запрограммировал его для печати длины каждого сортируемого списка. Функция выглядит следующим образом:

def sort(l): 
    if len(l) <= 1: 
     return l 
    print len(l) 
    pivot = choice(l) 
    l.remove(pivot) 
    left = [] 
    right = [] 
    for i in l: 
     if wins(i, pivot) == True: 
      right.append(i) 
     else: 
      left.append(i) 
    return sort(left) + [pivot] + sort(right) 

и когда у меня было это сортирует 64 руки, он напечатал: 64, 53, 39, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 12, 7, 3, 2, 3, 2, 4, 3 , 2, 13, 9, 6, 2, 3 , 2, 2, 3 , 10, 8, 2, 5, 4, 3, 2. Обратите внимание на последовательную последовательность посередине? Я не могу понять, почему это так, но это приводит к тому, что quicksort ведет себя как O (n^2). Для него не имеет смысла выбирать самую сильную руку в качестве стержня на каждой итерации, но это то, что, похоже, происходит. Что я не замечаю?

Answer 1

Edited ответ после комментариев:

Не могли бы вы попробовать следующий код и поделиться своими результатами. Он вводит класс эквивалентности для сокращения населения в группе «потерять или связывать» (или «меньше или равно»), образуя ответ через рекурсию.

# modified quicksort with equivalence class. 
def sort(l): 
    if len(l) <= 1: 
     return l 
    print len(l) 
    pivot = choice(l) 
    l.remove(pivot) 
    left = [] 
    right = [] 

    # I added an equivalence class 
    pivotEquivalence = [pivot] 

    # and an equivalence partitioning 
    # to reduce number of elements 
    # in the upcoming recursive calls 
    for i in l: 
     if wins(i, pivot) == True: 
      right.append(i) 
     elif wins(pivot,i) == True: 
      left.append(i) 
     else 
      pivotEquivalence.append(i) 
    return sort(left) + pivotEquivalence + sort(right) 

======

Вместо того чтобы выбрать стержень случайно, попытайтесь брать средний индексированный элемент. в среднем это гарантирует O (N log N).

Также для обозначения O вы должны сделать много симуляций для сбора эмпирических данных. Только один пример может быть очень обманчивым.

Попробуйте распечатать стержень, и это также индекс. Перетасуйте свой список с помощью random.shuffle (list) и повторите попытку, чтобы увидеть дистрибутив. Просто обеспечьте время посева системы.

Не могли бы вы отправить полный код и ваши данные для сообщества, чтобы повторить проблему?

С уважением, Умут