Various sort methods

Apr 27th, 2021
47
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from random import randint
2. from random import sample
3. from time import time
4.
5. def generateRandomList(numberOfElements):
6.     elements = []
7.     for i in range(0,numberOfElements):
8.         value = randint(1,100)
9.         elements.append(value)
10.     return elements
11.
12. def generateRandomAlphabet():
13.     letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
14.     elements = sample(letters,26)
15.     return elements
16.
17. def bubbleSort(elements):
18.     print('Bubble Sort')
19.     start = time()
20.     swapped = True
21.     n = len(elements) - 1
22.     while swapped:
23.         swapped = False
24.         for i in range(n):
25.             if elements[i] > elements[i+1]:
26.                 #elements[i], elements[i+1] = elements[i+1],elements[i]
27.                 elements.insert(i+1,elements.pop(i))
28.                 swapped = True
29.         n -= 1
30.     print(str(time() - start))
31.     return elements
32.
33. def insertionSort(elements):
34.     print('Insertion Sort')
35.     start = time()
36.     #Loop through items
37.     for item in range(1,len(elements)):
38.         #get the item to be moved into a sorted postion
39.         marker = item - 1
40.         key = elements[item]
41.
42.         #Loop through sorted items until the correct sorted position is found
43.         #Or the start of the sorted list is reached
44.         while elements[marker] > key and marker >= 0:
45.             elements[marker + 1] = elements[marker]
46.             elements[marker] = key
47.             marker -= 1
48.         #print(elements)
49.     print(str(time() - start))
50.     return elements
51.
52. def mergeLists(lista,listb):
53.     listc = []
54.     #loop through lists and add smalledt element to sorted list until one is empty
55.     while lista != [] and listb != []:
56.         if lista[0] <= listb[0]:
57.             listc.append(lista.pop(0))
58.         else:
59.             listc.append(listb.pop(0))
60.     if len(lista) >= 1:
61.         listc += lista
62.     else:
63.         listc += listb
64.     return listc
65.
66. def mergeSort(listc):
67.     if len(listc) <= 1:
68.         return listc
69.     else:
70.         middle = int(len(listc)/2)
71.         lista = mergeSort(listc[:middle])
72.         listb = mergeSort(listc[middle:])
73.         #print(middle,lista,listb)
74.     return mergeLists(lista,listb)
75.
76. def generateOrderedList(x):
77.     elements = list(range(1,x))
78.     return elements
79. #elements = generateOrderedList(10000)
80. elements = generateRandomList(5000)
81. #elements = generateRandomAlphabet()
82. bubbleSorted = bubbleSort(elements[:])
83. #print('Bubble List: {}'.format(bubbleSorted))
84. insertionSorted = insertionSort(elements[:])
85. #print('Insert List  : {}'.format(insertionSorted))
86.
87. print("Merge Sort")
88. start = time()
89. mergeSorted = mergeSort(elements[:])
90. print(str(time() - start))
91.
92. print("Tim Sort")
93. start = time()
94. a = sorted(elements[:])
95. print(str(time() - start))
96.