19
Tôi đã rối tung xung quanh với Python đang cố gắng thực hành các thuật toán sắp xếp của tôi và phát hiện ra điều gì đó thú vị.Quicksort sắp xếp các số lớn hơn nhanh hơn?
tôi có ba phần khác nhau của dữ liệu:
- x = số lượng các số để sắp xếp
- y = phạm vi các số là (tất cả ints tạo ra ngẫu nhiên)
- z = tổng thời gian thực hiện để loại
Thời gian:
x = 100000 và
y = (0,100000) sau đó
z = ,94182094911 giây
Thời gian:
x = 100000 và
y = (0100) sau đó
z = 12,4218382537 giây
Thời gian:
x = 100000 và
y = (0, 10) sau đó
z = 110.267447809 giây
Bất kỳ ý tưởng nào?
Code:
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)
------------------- sửa đổi mã mới --------------- -------------
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
Bạn có gặp phải hành vi này sau khi bạn chạy từng cài đặt nhiều lần và lấy trung bình kết quả không? – Davidann
Ngoài ra: không nên mở ("C: \ output.txt", 'w') 'be' mở ("C: \\ output.txt", 'w') '? – Mikel
@David Kết quả khá nhất quán.Điều này áp dụng cho các phạm vi (0,10) (0,100) (0,10000) – anon58192932