quick sortの簡略化の実現
15015 ワード
Pivotランダム選択はあまり意味がありません
第1の方法はランダムpivotを用いて、可能な限り二分配列を平均するが、実際には一般的に並べ替えが必要な集合は往々にして乱順であり、ランダム数をpivotとして再生成する必要がなく、固定位置の数をpivotとして大きく使用することができ、このようにほとんどの状況に適応することができ、論理を簡略化することができ、第2のsimple quick Sortがある.
演算結果からランダムpivotを用いても用いなくても性能はほぼ同じである.
大量の繰返し元素が存在する場合,時間的複雑度はO(n 2)に劣化する
多くの教材では,入力が秩序化されているなどの特定の場合,クイックソート(quicksort)の時間的複雑さはO(n 2)に劣化すると述べている.実際には,並べ替え対象の集合に同じ要素が多く含まれる限り,ほとんどの教材での実装はO(n 2)に劣化する.多くの実装のpartition実装方法はpivotに等しい要素をpivotの同一辺に分けることが問題である.
第3の実装quick_sort_quickはこの問題を解決するためである(大量の重複要素が存在する場合、n*10倍の性能向上がある).
第1の方法はランダムpivotを用いて、可能な限り二分配列を平均するが、実際には一般的に並べ替えが必要な集合は往々にして乱順であり、ランダム数をpivotとして再生成する必要がなく、固定位置の数をpivotとして大きく使用することができ、このようにほとんどの状況に適応することができ、論理を簡略化することができ、第2のsimple quick Sortがある.
演算結果からランダムpivotを用いても用いなくても性能はほぼ同じである.
大量の繰返し元素が存在する場合,時間的複雑度はO(n 2)に劣化する
多くの教材では,入力が秩序化されているなどの特定の場合,クイックソート(quicksort)の時間的複雑さはO(n 2)に劣化すると述べている.実際には,並べ替え対象の集合に同じ要素が多く含まれる限り,ほとんどの教材での実装はO(n 2)に劣化する.多くの実装のpartition実装方法はpivotに等しい要素をpivotの同一辺に分けることが問題である.
第3の実装quick_sort_quickはこの問題を解決するためである(大量の重複要素が存在する場合、n*10倍の性能向上がある).
====== sort 80*500 numbers ======
quick QS: 2014-11-18 10:08:34.281000
my_quick_sort: 2014-11-18 10:08:35.425000
default sort: 2014-11-18 10:08:36.576000
after sort: 2014-11-18 10:08:36.579000
====== sort 21*300 numbers with many duplicated ======
quick QS: 2014-11-18 10:08:36.579000 37ms # ，
my_quick_sort: 2014-11-18 10:08:36.616000 994ms
default sort: 2014-11-18 10:08:37.610000 1ms
after sort: 2014-11-18 10:08:37.611000
====== compare with random or without random ======
simple QS: 2014-11-18 10:08:37.611000
my_quick_sort: 2014-11-18 10:08:38.758000
default sort: 2014-11-18 10:08:39.908000
after sort: 2014-11-18 10:08:39.909000
====== sort 90000 numbers without duplicated ======
qucik QS: 2014-11-18 10:08:39.916000
simple QS: 2014-11-18 10:08:40.285000
my_quick_sort: 2014-11-18 10:08:40.661000
default sort: 2014-11-18 10:08:41.016000
after sort: 2014-11-18 10:08:41.018000
# 1 ：
simple QS: 2014-11-17 16:53:03.450000 38ms
my_quick_sort: 2014-11-17 16:53:03.488000 35ms
default sort: 2014-11-17 16:53:03.523000
after sort: 2014-11-17 16:53:03.524000
2014-11-17 16:53:03.524000
# 1 ：
simple QS: 2014-11-17 16:53:03.524000 35ms
my_quick_sort: 2014-11-17 16:53:03.559000 35ms
default sort: 2014-11-17 16:53:03.594000
after sort: 2014-11-17 16:53:03.594000
#9 ：simple QS: 2014-11-17 16:57:12.885000 367ms
my_quick_sort: 2014-11-17 16:57:13.252000 352ms
default sort: 2014-11-17 16:57:13.604000 1ms
after sort: 2014-11-17 16:57:13.605000#-------------------------------------------------------------------------------
# Name: quick sort
# Purpose:
#
# Author: ScottGu<[email protected], [email protected]>
#
# Created: 04/09/2013
# Copyright: (c) ScottGu<[email protected], [email protected]> 2013
# Licence: <your licence>
#-------------------------------------------------------------------------------
from datetime import datetime
from random import randint
import sys
sys.setrecursionlimit(10000)
def quick_sort(lst):
if len(lst)==0:
return lst
else:
pivot_idx = randint(0, len(lst) - 1)
pivot = lst[pivot_idx]
lesser=quick_sort([val for idx, val in enumerate(lst)
if val <= pivot and idx!=pivot_idx])
greater=quick_sort([x for x in lst if x > pivot])
return lesser+[pivot]+greater
def quick_sort_simple(lst):
if len(lst)==0:
return lst
else:
pivot = lst[0]
lesser=quick_sort([x for x in lst[1:] if x <= pivot])
greater=quick_sort([x for x in lst[1:] if x > pivot])
return lesser+[pivot]+greater
def quick_sort_quick(lst):
if len(lst)==0:
return lst
else:
pivot = lst[0]
lesser=quick_sort([x for x in lst[1:] if x < pivot])
greater=quick_sort([x for x in lst[1:] if x > pivot])
return lesser+[pivot]+[x for x in lst[1:] if x == pivot]+greater
def main():
lst=[20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
lst=lst*500
ls2=[1,2,1,1,1,3,4,7,9,11,12,1,1,1,1,1,1,1,1,1,1]
ls2=ls2*300
print '====== sort 80*500 numbers ====== '
print 'quick QS: '+str(datetime.now())
quick_sort_quick(lst)
print 'my_quick_sort: '+str(datetime.now())
quick_sort_simple(lst)
print 'default sort: '+str(datetime.now())
lst.sort()
print 'after sort: '+str(datetime.now())
print '====== sort 21*300 numbers with many duplicated ====== '
print 'quick QS: '+str(datetime.now())
quick_sort_quick(ls2)
print 'my_quick_sort: '+str(datetime.now())
quick_sort_simple(ls2)
print 'default sort: '+str(datetime.now())
ls2.sort()
print 'after sort: '+str(datetime.now())
print '====== compare with random or without random ====== '
print 'simple QS: '+str(datetime.now())
quick_sort_simple(lst)
print 'my_quick_sort: '+str(datetime.now())
quick_sort(lst)
print 'default sort: '+str(datetime.now())
lst.sort()
print 'after sort: '+str(datetime.now())
print '====== sort 90000 numbers without duplicated ====== '
lst=[]
for x in range(90000):
lst.append(x)
print 'qucik QS: '+str(datetime.now())
quick_sort_quick(lst)
print 'simple QS: '+str(datetime.now())
quick_sort_simple(lst)
print 'my_quick_sort: '+str(datetime.now())
quick_sort(lst)
print 'default sort: '+str(datetime.now())
lst.sort()
print 'after sort: '+str(datetime.now())
if __name__ == '__main__':
main()