AndreiL
Welcome to AndreiL.
Enjoy your time.
Please log in.

Quick-Sort vs Gnome-Sort - Python

Go down

Quick-Sort vs Gnome-Sort - Python

Post by Lucaci Andrei on Mon Feb 13, 2012 5:30 am

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
'''
Created on Jan 13, 2012

@author: sin
'''
"""4. a. Quick Sort
b. Gnome Sort
"""
n = 500

def cmps(a, b):
if a < b: return True
return False

def cmpse(a, b):
if a <= b:return True
return False

def cmpb(a, b):
if a > b:return True
return False

def cmpe(a, b):
if a == b:return True
return False

k = []
import random
for i in range(0, n - 1):
k.append(random.randint(0, n - 1))
s = k[:]
print k
def Partition(A, i, j):
x = A[i]
h = i
for k in range(i + 1, j):
if A[k] < x:
h = h + 1
A[h], A[k] = A[k], A[h]
A[h], A[i] = A[i], A[h]
return h

def QuickSort(A, p=0, r= -1):
if r is -1:
r = len(A)
if cmps(p, r - 1):
q = Partition(A, p, r)
QuickSort(A, p, q)
QuickSort(A, q + 1, r)
from time import time
start1 = time()
QuickSort(k)
end1 = time()
print k
print "List sorted by QuickSort in: ", end1 - start1, "seconds."


#from time import time
print s
def GnomeSort(list):
i = 0
while cmps(i, len(list)):
if i == 0 or cmpse(list[i - 1], list[i]):
i += 1
else:
list[i], list[i - 1] = list[i - 1], list[i]
i -= 1
start2 = time()
GnomeSort(s)
end2 = time()
print s
print "List sorted by GnomeSort in: ", end2 - start2, "seconds."


"""Comparison between QuickSort and GnomeSort"""

if cmps(end2 - start2, end1 - start1):
print "QuickSort is slower than GnomeSort."
elif cmpe(end2 - start2, end1 - start1):
print "QuickSort and GnomeSort have the same sorting time."
elif cmpb(end2 - start2, end1 - start1):
print "QuickSort is faster than GnomeSort."

avatar
Lucaci Andrei
"Tata Lor"


Number of messages : 222
Points : 2266743
Reputation : 1007
Registration date : 2008-08-15
Age : 25
Location : Cluj-Napoca

View user profile http://www.andreil.wgz.ro

Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum