Insertion Sort

Instructions:

Use Insertion Sort to sort the table given below in ascending order. Click on an item to select it and copy its value to another position by clicking on the new position.

1. def sorttime(B):
2. A = [randrange(1,1000) for _ in range(testsize)] # To make it create a real A for copying
3. numruns = 5
5. print "Range ", range(0, numruns)
7. totaltime = 0
8. for runs in range(1, numruns):
9. for i in range(len(B)):
10. A[i] = B[i]
11. time1 = datetime.now()
12. insertionsort(A)
13. time2 = datetime.now()
14. checkorder(A)
15. totaltime += millis(time2-time1)
16. print "Standard Insertion Sort: Size ", testsize, ", Time: ", totaltime
18. totaltime = 0
19. for runs in range(1, numruns):
20. for i in range(len(B)):
21. A[i] = B[i]
22. time1 = datetime.now()
23. insertionsort2(A)
24. time2 = datetime.now()
25. checkorder(A)
26. totaltime += millis(time2-time1)
27. print "Standard Insertion Sort, no swap function: Size ", testsize, ", Time: ", totaltime
29. totaltime = 0
30. for runs in range(1, numruns):
31. for i in range(len(B)):
32. A[i] = B[i]
33. time1 = datetime.now()
34. insertionsortshift(A)
35. time2 = datetime.now()
36. checkorder(A)
37. totaltime += millis(time2-time1)
38. print "Shifting Insertion Sort: Size ", testsize, ", Time: ", totaltime
40. totaltime = 0
41. for runs in range(1, numruns):
42. for i in range(len(B)):
43. A[i] = B[i]
44. time1 = datetime.now()
45. insertionsortshift(A)
46. time2 = datetime.now()
47. checkorder(A)
48. totaltime += millis(time2-time1)
49. print "Shifting Insertion Sort 2 (!=): Size ", testsize, ", Time: ", totaltime
51. totaltime = 0
52. for runs in range(1, numruns):
53. for i in range(len(B)):
54. A[i] = B[i]
55. time1 = datetime.now()
56. myinsertionsort(A)
57. time2 = datetime.now()
58. checkorder(A)
59. totaltime += millis(time2-time1)
60. print "Chris Dusold's Insertion Sort: Size ", testsize, ", Time: ", totaltime
62. totaltime = 0
63. for runs in range(1, numruns):
64. for i in range(len(B)):
65. A[i] = B[i]
66. time1 = datetime.now()
67. insertionsortshiftpy(A)
68. time2 = datetime.now()
69. checkorder(A)
70. totaltime += millis(time2-time1)
71. print "Python'y Insertion Sort with shift: Size ", testsize, ", Time: ", totaltime
73. # Instead of swapping, "shift" the values down the array
74. # /* *** ODSATag: InsertionOpt *** */
75. def insertionsortshift(A):
76. for i in range(1, len(A)): # Insert i'th record
77. temp = A[i]
78. j = i
79. while j > 0 and temp < A[j-1]:
80. A[j] = A[j-1]
81. j -= 1
82. A[j] = temp
83. # /* *** ODSAendTag: InsertionOpt *** */
86. # Same as insertionsortshift, but try != instead of < for the zero test
87. # This will only matter to JavaScript
88. def insertionsortshift2(A):
89. for i in range(1, len(A)-1): # Insert i'th record
90. temp = A[i]
91. j=i
92. while (j != 0) and (temp < A[j-1]):
93. A[j] = A[j-1]
94. j -= 1
95. A[j] = temp
97. # Same as standard insertion sort, except get rid of the swap
98. # function call
99. def insertionsort2(A):
100. for i in range(1, len(A)-1): # Insert i'th record
101. j = i;
102. while (j != 0) and (A[j] < A[j-1]):
103. temp = A[j]
104. A[j] = A[j-1]
105. A[j-1] = temp
106. j -= 1
108. def success():
109. print "Success! (Need to define this)"
111. def sorttest(A):
112. insertionsort(A)
114. # /* *** ODSATag: Insertionsort *** */
115. def insertionsort(A):
116. for i in range(len(A)): # Insert i'th record
117. j = i
118. while j > 0 and A[j] < A[j-1]:
119. swap(A, j, j-1)
120. j -= 1
121. # /* *** ODSAendTag: Insertionsort *** */
123. # Chris Dusold's attempt to "pythonize" the sort
124. def myinsertionsort(A):
125. for i in range(len(A)): # Insert i'th record
126. for j in range(i,0,-1):
127. if (A[j] >= A[j-1]):
128. break
129. A[j],A[j-1]=A[j-1],A[j]
131. # Instead of swapping, "shift" the values down the array
132. # Try to make it more "native" python
133. # SOLUTION BELOW NOT WORKING
134. def insertionsortshiftpy(A):
135. for i in range(1, len(A)-1): # Insert i'th record
136. temp = A[i]
137. for j in range(i,0,-1):
138. if (temp >= A[j-1]):
139. break
140. A[j] = A[j-1]
141. A[j-1] = temp
142. # SOLUTION ABOVE NOT WORKING