Быстрая сортировка больших чисел быстрее?

Question

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

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

• x = количество чисел дляsort
• y = диапазон, в котором находятся числа (все случайные сгенерированные числа)
• 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

Answer 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]

А большие значения - это массив

 []

. Это тот случай, когда быстрая сортировка вырождается в O (n *).1013 * 2 ), так как каждый рекурсивный вызов только уменьшает размер ввода на единицу (а именно, вытягивая элемент pivot).

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

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

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

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

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

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

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

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

Answer 2

Вещи, которые мы знаем:

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

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

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

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

Answer 3

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