Advertisement
JAS_Software

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.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement