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=20090115202654
 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=15958
25 
26 def qsort1(lst):
27 	if len(lst) <= 1:
28 		return lst
29 	pivot = lst.pop(0)
30 	greater_eq = qsort1([i for i in lst if i >= pivot])
31 	lesser = qsort1([i for i in lst if i < pivot])
32 	return lesser + [pivot] + greater_eq
33 
34 from random import randrange       
35 def qsort1a(list):
36     """
37     Quicksort using list comprehensions and randomized pivot
38     >>> qsort1a([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3])
39     [1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]
40 
41     >>> qsort1a(["bob","alice","barry","zoe","charlotte","fred","marvin"])
42     ['alice', 'barry', 'bob', 'charlotte', 'fred', 'marvin', 'zoe']
43 
44     """
45     def qsort(list):
46         if list == []: 
47             return []
48         else:
49             pivot = list.pop(randrange(len(list)))
50             lesser = qsort([l for l in list if l < pivot])
51             greater = qsort([l for l in list if l >= pivot])
52             return lesser + [pivot] + greater
53     return qsort(list[:])
54 
55 def partition(list, l, e, g):
56     while list != []:
57         head = list.pop(0)
58         if head < e[0]:
59             l = [head] + l
60         elif head > e[0]:
61             g = [head] + g
62         else:
63             e = [head] + e
64     return (l, e, g)
65 
66 def qsort2(list):
67     """
68     Quicksort using a partitioning function
69     >>> qsort2([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3])
70     [1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]
71 
72     >>> qsort2(["bob","alice","barry","zoe","charlotte","fred","marvin"])
73     ['alice', 'barry', 'bob', 'charlotte', 'fred', 'marvin', 'zoe']
74 
75     """
76     if list == []: 
77         return []
78     else:
79         pivot = list[0]
80         lesser, equal, greater = partition(list[1:], [], [pivot], [])
81         return qsort2(lesser) + equal + qsort2(greater)
82 
83 
84 if __name__ == "__main__":
85     import doctest
86     doctest.testmod()
87


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=20090115202654
 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=15958
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