FilesExpand file tree

 master

/

pythonSortTest.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

165 lines (147 loc) · 4.4 KB

 master

/

pythonSortTest.py

Copy path

Top

File metadata and controls

• Code
• Blame

165 lines (147 loc) · 4.4 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

'''

# Create by LokiSharp(loki.sharp#gmail) at 2017-1-22

'''

TOTAL=5000

def sortTest(func, total=1000):

import random, copy, operator, math, time

arrList = [i for i in range(-math.floor(total/2),math.ceil(total/2))]

arrListR = copy.deepcopy(arrList)

while operator.eq(arrList,arrListR):

random.shuffle(arrListR)

#print("--- [Origin List]", arrList, "Use", func.__name__,"with Total:", len(arrList))

#print("--> [Random List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))

start = time.clock()

arrListR = func(arrListR)

end = time.clock()

runtime = end-start

#print("--> [Sorted List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))

if operator.eq(arrList, arrListR):

print("[Success]", func.__name__,"with Total:", len(arrList),"in %.5fs" % runtime)

return True

else:

print("[Fail]", func.__name__,"with Total:", len(arrList),"in %.5fs" % runtime)

return False

def bubbleSort(arr):

for i in range(1, len(arr)):

for j in range(0, len(arr)-i):

if arr[j] > arr[j+1]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

return arr

def selectionSort(arr):

for i in range(len(arr)-1):

for j in range(i+1, len(arr)):

if arr[j] < arr[i]:

arr[i], arr[j] = arr[j], arr[i]

return arr

def insertionSort(arr):

for i in range(len(arr)):

preIndex = i-1

current = arr[i]

while preIndex >= 0 and arr[preIndex] > current:

arr[preIndex+1] = arr[preIndex]

preIndex-=1

arr[preIndex+1] = current

return arr

def shellSort(arr):

import math

gap=1

while(gap < len(arr)/3):

gap = gap*3+1

while gap > 0:

for i in range(gap,len(arr)):

temp = arr[i]

j = i-gap

while j >=0 and arr[j] > temp:

arr[j+gap]=arr[j]

j-=gap

arr[j+gap] = temp

gap = math.floor(gap/3)

return arr

def mergeSort(arr):

import math

if(len(arr)<2):

return arr

middle = math.floor(len(arr)/2)

left, right = arr[0:middle], arr[middle:]

return merge(mergeSort(left), mergeSort(right))

def merge(left,right):

result = []

while left and right:

if left[0] <= right[0]:

result.append(left.pop(0));

else:

result.append(right.pop(0));

while left:

result.append(left.pop(0));

while right:

result.append(right.pop(0));

return result

def quickSort(arr, left=None, right=None):

left = 0 if not isinstance(left,(int, float)) else left

right = len(arr)-1 if not isinstance(right,(int, float)) else right

if left < right:

partitionIndex = partition(arr, left, right)

quickSort(arr, left, partitionIndex-1)

quickSort(arr, partitionIndex+1, right)

return arr

def partition(arr, left, right):

pivot = left

index = pivot+1

i = index

while i <= right:

if arr[i] < arr[pivot]:

swap(arr, i, index)

index+=1

i+=1

swap(arr,pivot,index-1)

return index-1

def swap(arr, i, j):

arr[i], arr[j] = arr[j], arr[i]

def buildMaxHeap(arr):

import math

for i in range(math.floor(len(arr)/2),-1,-1):

heapify(arr,i)

def heapify(arr, i):

left = 2*i+1

right = 2*i+2

largest = i

if left < arrLen and arr[left] > arr[largest]:

largest = left

if right < arrLen and arr[right] > arr[largest]:

largest = right

if largest != i:

swap(arr, i, largest)

heapify(arr, largest)

def swap(arr, i, j):

arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):

global arrLen

arrLen = len(arr)

buildMaxHeap(arr)

for i in range(len(arr)-1,0,-1):

swap(arr,0,i)

arrLen -=1

heapify(arr, 0)

return arr

def countingSort(arr, maxValue=None):

bucketLen = maxValue+1

bucket = [0]*bucketLen

sortedIndex =0

arrLen = len(arr)

for i in range(arrLen):

if not bucket[arr[i]]:

bucket[arr[i]]=0

bucket[arr[i]]+=1

for j in range(bucketLen):

while bucket[j]>0:

arr[sortedIndex] = j

sortedIndex+=1

bucket[j]-=1

return arr

sortTest(bubbleSort, TOTAL)

sortTest(selectionSort, TOTAL)

sortTest(insertionSort, TOTAL)

sortTest(shellSort, TOTAL)

sortTest(mergeSort, TOTAL)

sortTest(quickSort, TOTAL)

sortTest(heapSort, TOTAL)