python sort
September 20, 2008 Python — Tags: bubble sort, Python, python sort, quick sort — 52coding
The principle is quick to sort out the first number, the entire array will be divided into two groups, one group is greater than the number of the other group are less than this number, and then recursive in the same way in the first set of figures and Second set of figures. That is “fast sort,” affirmed the efficiency of the general than other high-ranking algorithm, we have the following to verify, and compare the so-called “quick sort” and the “bubble sort of” performance differences.
1.qurick sort
def quicksort(data, low = 0, high = None):
if high == None:
high = len(data) - 1
if low < high:
s, i, j = data[low], low, high
while i < j:
while i < j and data[j] >= s:
j = j - 1
if i < j:
data[i] = data[j]
i = i + 1
while i < j and data[i] <= s:
i = i + 1
if i < j:
data[j] = data[i]
j = j - 1
data[i] = s
quicksort(data, low, i - 1)
quicksort(data, i + 1, high)
if high == None:
high = len(data) - 1
if low < high:
s, i, j = data[low], low, high
while i < j:
while i < j and data[j] >= s:
j = j - 1
if i < j:
data[i] = data[j]
i = i + 1
while i < j and data[i] <= s:
i = i + 1
if i < j:
data[j] = data[i]
j = j - 1
data[i] = s
quicksort(data, low, i - 1)
quicksort(data, i + 1, high)
2.bubble sort
def bubblesort(data):
for i in range(len(data) - 1, 1, -1):
for j in range(0, i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
for i in range(len(data) - 1, 1, -1):
for j in range(0, i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
3.performance comparison
import random
import datetime
import copy
def sort_perfmon(sortfunc, data):
sort_data = copy.deepcopy(data)
t1 = datetime.datetime.now()
sortfunc(sort_data)
t2 = datetime.datetime.now()
print sortfunc.__name__, t2 - t1
#print sort_data
data = [random.randint(0, 65536) for i in range(2000)]
#print data
sort_perfmon(quicksort, data)
sort_perfmon(bubblesort, data)
import datetime
import copy
def sort_perfmon(sortfunc, data):
sort_data = copy.deepcopy(data)
t1 = datetime.datetime.now()
sortfunc(sort_data)
t2 = datetime.datetime.now()
print sortfunc.__name__, t2 - t1
#print sort_data
data = [random.randint(0, 65536) for i in range(2000)]
#print data
sort_perfmon(quicksort, data)
sort_perfmon(bubblesort, data)
4.result:
quicksort 0:00:00.062000
bubblesort 0:00:03.563000
