Проблемы с пониманием того, что включается при использовании "больше или равно" (> =) - PullRequest
Новая
       72

Проблемы с пониманием того, что включается при использовании "больше или равно" (> =)

0 голосов
/ 09 мая 2020

Мне нужно написать функцию быстрой сортировки для моего курса. Одно из возможных решений, приведенное позже, было следующим: 

def quicksort(s):
    if len(s) <= 1:
        return s
    else:
        return quicksort([x for x in s[1:] if x < s[0]]) \
        +[s[0]] \
        + quicksort([y for y in s[1:] if y >= s[0]])


list = [5, 6, 8, 2, 7, 1] #any numbers you want
print(quicksort(list))

Зачем нужен +[s[0]]? разве он уже не включен в y >= s[0]?

1 Ответ

3 голосов
/ 09 мая 2020

В вашем списке может быть несколько одинаковых элементов, и вы не должны терять их в процессе их сортировки.

Обратите внимание, что оба понимания (которые собирают элементы «до» и «после» стержень с точки зрения сортировки) работают с s[1:], то есть с каждым элементом после s[0]. Следовательно, они никогда не будут включать сам s[0], независимо от того, какие другие предикаты вы применяете.

>= присутствует, потому что, если вы включите только > s[0] с одной стороны и < s[0] с другой, вы потеряете любые другие элементы, которые == s[0] в процессе сортировки.

Например: 

# don't give variables the same name as built-in types/functions!
numbers = [5, 5, 5, 6, 8, 2, 7, 1]
print(quicksort(numbers))

[1, 2, 5, 5, 5, 6, 7, 8]

Что, если мы сделаем это y > s[0] вместо этого? 

def quicksort(s):
    if len(s) <= 1:
        return s
    else:
        return (
            quicksort([x for x in s[1:] if x < s[0]])
            + [s[0]]
            + quicksort([y for y in s[1:] if y > s[0]])
        )


# don't give variables the same name as built-in types/functions!
numbers = [5, 5, 5, 6, 8, 2, 7, 1]  # any numbers you want
print(quicksort(numbers))

[1, 2, 5, 6, 7, 8]

Упс!

Использование >= не обязательно единственный способ исправить это. Мы могли бы явно иметь среднюю часть нашего списка будет все элементы равны к оси (в том числе поворота), например: 

def quicksort(s):
    if len(s) <= 1:
        return s
    p = s[0]  # could be any arbitrary element!
    return (
        quicksort([x for x in s if x < p])
        + [x for x in s if x == p]
        + quicksort([x for x in s if x > p])
    )

Это может быть немного медленнее, потому что вы сейчас делаете дополнительную итерация по списку (возможно, тот факт, что вы передаете второй quicksort более короткий список, хотя?), но, возможно, делает концепцию немного более ясной, что все элементы «меньше чем» идут перед «равным» «элементы, которые предшествуют элементам« больше ».

Этот подход также упрощает эксперименты с выбором различных точек поворота; если вам посчастливилось начать со списка, который уже отсортирован (или в основном отсортирован), например, выбор точки поворота в середине, а не в начале может быть немного быстрее, потому что ваше дерево рекурсивных вызовов более широкое и менее глубокое.

...