Самый быстрый способ сортировки в Python

Ответ 1

Если вас интересует асимптотическое время, то подсчет сортировки или сортировки счисления обеспечивает хорошую производительность.

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

def qsort(inlist):
    if inlist == []: 
        return []
    else:
        pivot = inlist[0]
        lesser = qsort([x for x in inlist[1:] if x < pivot])
        greater = qsort([x for x in inlist[1:] if x >= pivot])
        return lesser + [pivot] + greater

Источник: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python

Ответ 2

Поскольку вы знаете диапазон чисел, вы можете использовать Counting Sort, который будет линейным во времени.

Ответ 3

Сортировка Radix теоретически выполняется в линейном времени (время сортировки растет примерно пропорционально размеру массива), но на практике Quicksort, вероятно, более подходит, если вы не сортируете абсолютно массивные массивы.

Если вы хотите быстро выполнить quicksort, вы можете использовать сортировку вставки], когда размер массива станет небольшим.

Вероятно, было бы полезно понять понятия алгоритмической сложности и нотации Big-O.

Ответ 4

В ранних версиях Python использовался гибрид samplesort (вариант быстрой сортировки с большим размером выборки) и сортировка двоичной вставки как встроенный алгоритм сортировки. Это оказалось несколько неустойчивым. S0, из python 2.3 onward использует алгоритм adaptive mergesort.

Порядок слияния (средний) = O(nlogn). Порядок слияния (худший) = O(nlogn). Но порядок быстрого сортировки (худший) = n * 2

если вы используете list=[ .............. ]

list.sort() использует mergesort algorithm.

Для сравнения между алгоритмом сортировки вы можете читать wiki

Для сравнения деталей comp

Ответ 5

Мы можем использовать сортировку count с помощью словаря, чтобы свести к минимуму использование дополнительного пространства, а также сократить время работы. Сортировка count намного медленнее для небольших размеров входного массива из-за накладных расходов на реализацию python vs C. Сортировка count начинает обходить обычную сортировку, когда размер массива (COUNT) составляет около 1 миллиона.

Если вам действительно нужны огромные ускорения для входов меньшего размера, выполните сортировку count в C и вызовите ее из Python.

(Исправлена ​​ошибка, которую Аарон (+1) помог поймать...) В приведенной ниже реализации python сравниваются два подхода...

import random
import time

COUNT = 3000000

array = [random.randint(1,100000) for i in range(COUNT)]
random.shuffle(array)

array1 = array[:]

start = time.time()
array1.sort()
end = time.time()
time1 = (end-start)
print 'Time to sort = ', time1*1000, 'ms'

array2 = array[:]

start = time.time()
ardict = {}
for a in array2:
    try:
        ardict[a] += 1
    except:
        ardict[a] = 1

indx = 0
for a in sorted(ardict.keys()):
    b = ardict[a]
    array2[indx:indx+b] = [a for i in xrange(b)]
    indx += b

end = time.time()
time2 = (end-start)
print 'Time to count sort = ', time2*1000, 'ms'

print 'Ratio =', time2/time1

Ответ 6

Возможно, я немного опоздал на шоу, но есть интересная статья, в которой сравниваются разные типы в https://www.linkedin.com/pulse/sorting-efficiently-python-lakshmi-prakash

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

Здесь ссылка на репозиторий Github: https://github.com/lprakash/Sorting-Algorithms/blob/master/sorts.ipynb

Ответ 7

Встроенные функции лучше всего, но поскольку вы не можете их использовать, посмотрите на это:

http://en.wikipedia.org/wiki/Quicksort

Ответ 8

def sort(l):
    p = 0
    while(p<len(l)-1):
        if(l[p]>l[p+1]):
            l[p],l[p+1] = l[p+1],l[p]
            if(not(p==0)):
                p = p-1
        else:
            p += 1
    return l

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

Ответ 9

@fmark Некоторое сравнение производительности python-merge-sort я написал против quicksorts python от http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python и от верхнего ответа.

• Размер списка и размер номеров в списке неактуальны

merge sort выигрывает, однако использует встроенный метод int() для заполнения

import numpy as np
x = list(np.random.rand(100))


# TEST 1, merge_sort 
def merge(l, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    left = l[p : p + n1]
    right = l[q + 1 : q + 1 + n2]

    i = 0
    j = 0
    k = p
    while k < r + 1:
        if i == n1:
            l[k] = right[j]
            j += 1
        elif j == n2:
            l[k] = left[i]
            i += 1
        elif  left[i] <= right[j]:
            l[k] = left[i]
            i += 1
        else:
            l[k] = right[j]
            j += 1
        k += 1

def _merge_sort(l, p, r):
    if p < r:
        q = int((p + r)/2)
        _merge_sort(l, p, q)
        _merge_sort(l, q+1, r)
        merge(l, p, q, r)

def merge_sort(l):
    _merge_sort(l, 0, len(l)-1)

# TEST 2
def quicksort(array):
    _quicksort(array, 0, len(array) - 1)

def _quicksort(array, start, stop):
    if stop - start > 0:
        pivot, left, right = array[start], start, stop
        while left <= right:
            while array[left] < pivot:
                left += 1
            while array[right] > pivot:
                right -= 1
            if left <= right:
                array[left], array[right] = array[right], array[left]
                left += 1
                right -= 1
        _quicksort(array, start, right)
        _quicksort(array, left, stop)

# TEST 3
def qsort(inlist):
    if inlist == []: 
        return []
    else:
        pivot = inlist[0]
        lesser = qsort([x for x in inlist[1:] if x < pivot])
        greater = qsort([x for x in inlist[1:] if x >= pivot])
        return lesser + [pivot] + greater

def test1():
    merge_sort(x)

def test2():
    quicksort(x)

def test3():
    qsort(x)

if __name__ == '__main__':
    import timeit
    print('merge_sort:', timeit.timeit("test1()", setup="from __main__ import test1, x;", number=10000))
    print('quicksort:', timeit.timeit("test2()", setup="from __main__ import test2, x;", number=10000))
    print('qsort:', timeit.timeit("test3()", setup="from __main__ import test3, x;", number=10000))