Quicksort сортирует большие числа быстрее?

Я возился с Python, пытаясь практиковать мои алгоритмы сортировки и узнал что-то интересное.

У меня есть три разных фрагмента данных:

x = количество номеров для сортировки
y = диапазон чисел (все случайные сгенерированные int)
z = общее время сортировки

Когда:
x = 100000 и
y = (0,100000), затем
z = 0,94182094911 с

Когда:
x = 100000 и
y = (0,100), затем z = 12,4218382537 с

Когда:
x = 100000 и
y = (0,10), затем z = 110,267447809 сек.

Любые идеи?

код:

import time
import random
import sys

#-----Function definitions

def quickSort(array): #random pivot location quicksort. uses extra memory.
    smaller = []
    greater = []
    if len(array) <= 1:
        return array
    pivotVal = array[random.randint(0, len(array)-1)]
    array.remove(pivotVal)
    for items in array:
        if items <= pivotVal:
            smaller.append(items)
        else:
            greater.append(items)
    return concat(quickSort(smaller), pivotVal, quickSort(greater))

def concat(before, pivot, after):
    new = []
    for items in before:
        new.append(items)
    new.append(pivot)
    for things in after:
        new.append(things)
    return new

#-----Variable definitions
list = []
iter = 0
sys.setrecursionlimit(20000)
start = time.clock() #start the clock

#-----Generate the list of numbers to sort
while(iter < 100000):
    list.append(random.randint(0,10))  #modify this to change sorting speed
    iter = iter + 1
timetogenerate = time.clock() - start #current timer - last timer snapshot

#-----Sort the list of numbers
list = quickSort(list)
timetosort = time.clock() - timetogenerate #current timer - last timer snapshot

#-----Write the list of numbers
file = open("C:\output.txt", 'w')
for items in list:
    file.write(str(items))
    file.write("\n")
file.close()
timetowrite = time.clock() - timetosort #current timer - last timer snapshot

#-----Print info
print "time to start: " + str(start)
print "time to generate: " + str(timetogenerate)
print "time to sort: " + str(timetosort)
print "time to write: " + str(timetowrite)
totaltime = timetogenerate + timetosort + start
print "total time: " + str(totaltime)

------------------- пересмотренный НОВЫЙ код ------------------------- ---

def quickSort(array): #random pivot location quicksort. uses extra memory.
    smaller = []
    greater = []
    equal = []
    if len(array) <= 1:
        return array
    pivotVal = array[random.randint(0, len(array)-1)]
    array.remove(pivotVal)
    equal.append(pivotVal)
    for items in array:
        if items < pivotVal:
            smaller.append(items)
        elif items > pivotVal:
            greater.append(items)
        else:
            equal.append(items)
    return concat(quickSort(smaller), equal, quickSort(greater))

def concat(before, equal, after):
    new = []
    for items in before:
        new.append(items)
    for items in equal:
        new.append(items)
    for items in after:
        new.append(items)
    return new

Ответы

Ответ 1

Я думаю, что это связано с выбором стержня. В зависимости от того, как работает ваш шаг раздела, если у вас много повторяющихся значений, ваш алгоритм может выродиться до квадратичного поведения, когда сталкивается со многими дубликатами. Например, предположим, что вы пытаетесь быстро сортировать этот поток:

 [0 0 0 0 0 0 0 0 0 0 0 0 0]

Если вы не будете осторожны с тем, как вы делаете шаг разбиения, это может быстро выродиться. Например, предположим, что вы выбираете свой стержень как первый 0, оставляя вас с массивом

 [0 0 0 0 0 0 0 0 0 0 0 0]

для разделения. Ваш алгоритм может сказать, что меньшими значениями являются массив

 [0 0 0 0 0 0 0 0 0 0 0 0]

И большими значениями являются массив

[]

Это приводит к тому, что quicksort вырождается до O (n ²), поскольку каждый рекурсивный вызов только уменьшает размер ввода на один (а именно, вытаскивая элемент поворота).

Я заметил, что в вашем коде ваш шаг разбиения действительно делает это:

for items in array:
    if items <= pivotVal:
        smaller.append(items)
    else:
        greater.append(items)

Учитывая поток, который содержит целую кучу копий одного и того же элемента, все они будут помещены в один массив для рекурсивного сортировки.

Конечно, это похоже на нелепый случай - как это вообще связано с уменьшением числа значений в массиве? - но на самом деле это происходит, когда вы сортируете множество элементов, которые не отличаются друг от друга. В частности, после нескольких проходов раздела вы можете сгруппировать все равные элементы, что приведет вас к этому случаю.

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

Один из вариантов, который работает, состоит в разделении ввода на три группы - меньше, равно и больше. Как только вы сломали вход таким образом, вам нужно только отсортировать все более и более группы; равные группы уже отсортированы. Вышеприведенная ссылка на ток-шоу показывает, как сделать это более или менее на месте, но поскольку вы уже используете быстродействующую сортировку вне места, исправление должно быть простым. Здесь моя попытка:

for items in array:
    if items < pivotVal:
        smaller.append(items)
    elif items == pivotVal:
        equal.append(items)
    else:
        greater.append(items)

Я никогда не писал строки Python в моей жизни, BTW, так что это может быть совершенно незаконный синтаксис. Но я надеюсь, что идея понятна!: -)

Ответ 2

Что мы знаем:

Сложность времени для быстрого сортировки неупорядоченного массива - O(n*logn).
Если массив уже отсортирован, он ухудшается до O(n^2).
Первые два утверждения не являются дискретными, т.е. чем ближе массив к сортировке, тем ближе временная сложность быстрого сортировки до O(n^2), и наоборот, когда мы перемешиваем его, сложность приближается к O(n*logn)

Теперь посмотрим на ваш эксперимент:

Во всех трех случаях вы использовали одинаковое количество элементов. Итак, наш n, который вы назвали x, всегда 100000.
В вашем первом эксперименте вы использовали числа от 0 до 100000, поэтому в идеале с идеальным генератором случайных чисел вы получили бы в основном разные числа в относительно неупорядоченном списке, таким образом, в случае сложности O(n*logn).
В третьем эксперименте вы использовали числа от 0 до 10 в 100 000 элементов большого списка. Это означает, что в вашем списке было много дубликатов, что значительно приближало его к сортированному списку, чем в первом эксперименте. Итак, в этом случае временная сложность была намного ближе к O(n^2).

И с тем же достаточно большим n вы можете сказать, что n*logn > n^2, который вы фактически подтвердили в своем эксперименте.

Ответ 3

Алгоритм быстрой сортировки имеет известную слабость - он медленнее, когда данные в основном сортируются. Когда у вас есть 100000 между 0 и 10, они будут ближе к тому, чтобы быть "в основном отсортированы", чем 100000 чисел в диапазоне от 0 до 100000.