Download code

From LiteratePrograms

Jump to: navigation, search

Back to Quicksort_(Python)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

qsort.py

 1 # Copyright (c) 2010 the authors listed at the following URL, and/or
 2 # the authors of referenced articles or incorporated external code:
 3 # http://en.literateprograms.org/Quicksort_(Python)?action=history&offset=20100705114008
 4 # 
 5 # Permission is hereby granted, free of charge, to any person obtaining
 6 # a copy of this software and associated documentation files (the
 7 # "Software"), to deal in the Software without restriction, including
 8 # without limitation the rights to use, copy, modify, merge, publish,
 9 # distribute, sublicense, and/or sell copies of the Software, and to
10 # permit persons to whom the Software is furnished to do so, subject to
11 # the following conditions:
12 # 
13 # The above copyright notice and this permission notice shall be
14 # included in all copies or substantial portions of the Software.
15 # 
16 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
20 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 # 
24 # Retrieved from: http://en.literateprograms.org/Quicksort_(Python)?oldid=16757
25 
26 def qsort1(list):
27     """
28     Quicksort using list comprehensions
29     >>> qsort1([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3])
30     [1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]
31 
32     >>> qsort1(["bob","alice","barry","zoe","charlotte","fred","marvin"])
33     ['alice', 'barry', 'bob', 'charlotte', 'fred', 'marvin', 'zoe']
34 
35     """
36     if list == []: 
37         return []
38     else:
39         pivot = list[0]
40         lesser = qsort1([x for x in list[1:] if x < pivot])
41         greater = qsort1([x for x in list[1:] if x >= pivot])
42         return lesser + [pivot] + greater
43 
44 from random import randrange       
45 def qsort1a(list):
46     """
47     Quicksort using list comprehensions and randomized pivot
48     >>> qsort1a([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3])
49     [1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]
50 
51     >>> qsort1a(["bob","alice","barry","zoe","charlotte","fred","marvin"])
52     ['alice', 'barry', 'bob', 'charlotte', 'fred', 'marvin', 'zoe']
53 
54     """
55     def qsort(list):
56         if list == []: 
57             return []
58         else:
59             pivot = list.pop(randrange(len(list)))
60             lesser = qsort([l for l in list if l < pivot])
61             greater = qsort([l for l in list if l >= pivot])
62             return lesser + [pivot] + greater
63     return qsort(list[:])
64 
65 def partition(list, l, e, g):
66     while list != []:
67         head = list.pop(0)
68         if head < e[0]:
69             l = [head] + l
70         elif head > e[0]:
71             g = [head] + g
72         else:
73             e = [head] + e
74     return (l, e, g)
75 
76 def qsort2(list):
77     """
78     Quicksort using a partitioning function
79     >>> qsort2([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3])
80     [1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]
81 
82     >>> qsort2(["bob","alice","barry","zoe","charlotte","fred","marvin"])
83     ['alice', 'barry', 'bob', 'charlotte', 'fred', 'marvin', 'zoe']
84 
85     """
86     if list == []: 
87         return []
88     else:
89         pivot = list[0]
90         lesser, equal, greater = partition(list[1:], [], [pivot], [])
91         return qsort2(lesser) + equal + qsort2(greater)
92 
93 
94 if __name__ == "__main__":
95     import doctest
96     doctest.testmod()
97


qsortr

def qsortr(list):
    return [] if list==[]  else qsortr([x for x in list[1:] if x < list[0]]) + [list[0]] + qsortr([x for x in list[1:] if x >= list[0]])


time-qsort.py

 1 # Copyright (c) 2010 the authors listed at the following URL, and/or
 2 # the authors of referenced articles or incorporated external code:
 3 # http://en.literateprograms.org/Quicksort_(Python)?action=history&offset=20100705114008
 4 # 
 5 # Permission is hereby granted, free of charge, to any person obtaining
 6 # a copy of this software and associated documentation files (the
 7 # "Software"), to deal in the Software without restriction, including
 8 # without limitation the rights to use, copy, modify, merge, publish,
 9 # distribute, sublicense, and/or sell copies of the Software, and to
10 # permit persons to whom the Software is furnished to do so, subject to
11 # the following conditions:
12 # 
13 # The above copyright notice and this permission notice shall be
14 # included in all copies or substantial portions of the Software.
15 # 
16 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
20 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 # 
24 # Retrieved from: http://en.literateprograms.org/Quicksort_(Python)?oldid=16757
25 
26 import sys
27 import random
28 import timing
29 import qsort
30 
31 def checkSorted(a):
32     for i in xrange(1, len(a) - 1):
33         if a[i] < a[i-1]:
34             return False
35     return True
36     
37 numElements = int(sys.argv[1])    
38 testlist = random.sample(xrange(999999999), numElements)
39 print "# elements: %d"%numElements
40 for q in qsort.qsort1, qsort.qsort1a, qsort.qsort2:
41     print "%s"%q.__name__,
42     list = testlist[:]
43     timing.start()
44     result = q(list)
45     timing.finish()
46     print "- %.3f secs"%(float(timing.micro()) / 1000000),
47     if checkSorted(result):
48         print "- passed"
49     else:
50         print "- failed"
51


Retrieved from "http://en.literateprograms.org/Special:Downloadcode"
Views
Personal tools