Python


Algoritmi za sortiranje

V nadaljevanju bomo potrebovali malo bolj resne programe, ki bodo od računalnika zahtevali več dela. Spomnimo se morda številk za žreb tombole in si postavimo nalogo, da jih stresemo iz bobna in ročno uredimo po vrsti  (seveda brez oštevilčene podloge kot pripomočka).

Pred  razvrstitvijo

Po razvrstitvi


Če je številk veliko, si lahko zamislimo, da je delo zamudno. Podobno nalogo lahko damo računalniku, da na primer naključno izbrana števila, ki jih pomnimo v seznamu, razvrsti. V praksi poznamo več postopkov, ki jim računalniško rečemo algoritmi sortiranja.

Spodnji program vsebuje tri poznane algoritme in omogoča primerjavo njihove hitrosti. V tem programu smo uvedli nekaj zanimivih prijemov, ki jih bomo spoznali v nadaljevanju.

from whrandom import randint            # the standard random number module
from time import clock # for timing different algorithms

def bubble_sort(list):
l=list[:]
# create a slice-copy of the list
for i in range(len(l)): # for every element [i] in the list
for j in range(i+1,len(l)): # examine every element [j] after it
if l[i]>l[j]: # and if they are "out of order"
l[i],l[j]=l[j],l[i]
# swap them
return l

def selection_sort(list):
l=list[:]
# create a copy of the list
sorted=[]
# this new list will hold the results
while len(l): # while there are elements to sort...
lowest=l[0]
# create a variable to identify lowest
for x in l: # and check every item in the list...
if x<lowest: # to see if it might be lower.
lowest=x
sorted.append(lowest)
# add the lowest one to the new list
l.remove(lowest)
# and delete it from the old one
return sorted

def merge(a,b): # this funtion merges two pre-sorted
c=[]
# lists into one sorted list
while len(a) and len(b): # while there are items in both lists
if a[0]<b[0]: # pick whichever "top" item is lower
c.append(a[0])
# and add it to the new list
del a[0] # then delete it from the original
else:
c.append(b[0])
del b[0]
c=c+a+b
# append anything that's left over
return c

def merge_sort(l): # sort lists by sorting each half,
if len(l) > 1: # then merging the halves
return merge(merge_sort(l[len(l)/2:]),merge_sort(l[:len(l)/2]))
else:
return l

def trial(func,list): # time how long it takes
start = clock()
# get starting time...
list1 = func(list)
# try the function...
end = clock()
# get the ending time...
print " %6.2f"%(end - start,), # and print the total time it took

print " size bubble selection merge"
for size in range(50,1001,50): # we go from 50 to 1000 items to test
list=[]
for i in range(size):
list.append(randint(0,size))
# and we fill the list with random #'s
print "%5d"%(size,),
trial(bubble_sort,list)
# then we try each sort() on the list
trial(selection_sort,list)
trial(merge_sort,list)
print