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

Question

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

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

• х = количество чисел для сортировки
• у = диапазон числа в (всех случайных сгенерированных целых чисел)
• г = общее время, необходимое для сортировать по

Когда:
х = 100000 и
у = (0,100000), то
г = +0,94182094911 сек

Когда:
х = 100000 и
у = (0100), то
г = +12,4218382537 сек

Когда:
х = 100000 и
у = (0, 10) затем
z = 110.267447809 sec

Любые идеи?

Код:

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

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

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

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

[] 

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

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

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

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

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

Для обсуждения того, как этого избежать, есть действительно замечательный разговор by Bob Sedgewick and Jon Bentley о том, как изменить шаг раздела, чтобы работать быстро, когда в присутствии повторяющихся элементов. Он связан с Dutch national flag problem Dijkstra, и их решения действительно умны.

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

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 в 100 000 элементов большого списка. Это означает, что в вашем списке было много дубликатов, что значительно приближало его к сортированному списку, чем в первом эксперименте. Итак, в этом случае временная сложность была намного ближе к O(n^2).

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

Answer 3

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