SHARE
TWEET

good sorts

PyCodr Feb 27th, 2020 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import gc
  2. import multiprocessing
  3. import random
  4. from time import time as _time
  5.  
  6. gc.enable()
  7.  
  8.  
  9. def main():
  10.     opopopop = 0
  11.     strings = [""] * 9
  12.     sorts = [bubble_sort, quick_sort, sort_insert, sort_select, sort_merge, sort_radix, sort_shell, sort_count, tim_sort]
  13.     d = [0] * 9
  14.     l = " " * 6
  15.     # create table
  16.     print("      \u001b[34;1mType \u001b[0m:   "
  17.           "|%s\u001b[32;1mbubble\u001b[0m%s|"
  18.           "|%s\u001b[32;1mquick\u001b[0m %s|"
  19.           "|%s\u001b[32;1minsert\u001b[0m%s|"
  20.           "|%s\u001b[32;1mselect\u001b[0m%s|"
  21.           "|%s\u001b[32;1mmerge\u001b[0m %s|"
  22.           "|%s\u001b[32;1mradix\u001b[0m %s|"
  23.           "|%s\u001b[32;1mshell\u001b[0m %s|"
  24.           "|%s\u001b[32;1mcount\u001b[0m %s|"
  25.           "|%s\u001b[32;1mtim\u001b[0m %s|"
  26.           % (l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l + " ", l + " "))
  27.     for i in range(0, 3):
  28.         for y in range(3, 8):
  29.             # create input
  30.             nums = [random.randint(0, 1000) for f in range(0, pow(10, y))]
  31.             if i > 0:
  32.                 nums = sorted(nums)
  33.             if i == 2:
  34.                 nums.reverse()
  35.             for w in range(len(sorts)):
  36.                 a = nums.copy()
  37.                 if w == 1:
  38.                     process = multiprocessing.Process(target=sorts[w], args=(a, 0, len(nums) - 1,))
  39.                 else:
  40.                     process = multiprocessing.Process(target=sorts[w], args=(a,))
  41.                 process.start()
  42.                 b = millis()
  43.                 process.join(10)
  44.                 if process.is_alive():
  45.                     process.terminate()
  46.                 d[w] = (millis() - b)
  47.             # create output strings
  48.             for h in range(0, len(strings)):
  49.                 strings[h] = "|   \u001b[36;1m%0.10f\u001b[0m   |" % d[h]
  50.                 # yellow if more than 3
  51.                 if d[h] >= 1:
  52.                     strings[h] = "|   \u001b[33;1m%0.10f\u001b[0m   |" % d[h]
  53.                 # red if overtime
  54.                 if d[h] > 9.9999999999:
  55.                     strings[h] = "|   \u001b[31;1m9.9999999999\u001b[0m   |"
  56.                 if d[h] == min(d):
  57.                     strings[h] = "|   \u001b[39;1m%0.10f\u001b[0m   |" % d[h]
  58.             # print
  59.             print("\u001b[35m%10d\u001b[0m :   %s%s%s%s%s%s%s%s%s"
  60.                   % (pow(10, y), strings[0], strings[1], strings[2], strings[3], strings[4], strings[5], strings[6], strings[7], strings[8]))
  61.             for j in range(9):
  62.                 opopopop += d[j]
  63.             gc.collect()
  64.         if i == 0:
  65.             print("\n    \u001b[34;1mAlready sorted:\u001b[0m\n")
  66.         if i == 1:
  67.             print("\n    \u001b[34;1mSorted and reversed:\u001b[0m\n")
  68.     print("Total time: %s" % opopopop)
  69.  
  70.  
  71. def quick_sort(nums, start, end):
  72.     if start >= end:
  73.         return
  74.     i, j = start, end
  75.     opora = nums[random.randint(start, end)]
  76.     while i <= j:
  77.         while nums[i] < opora:
  78.             i += 1
  79.         while nums[j] > opora:
  80.             j -= 1
  81.         if i <= j:
  82.             nums[i], nums[j] = nums[j], nums[i]
  83.             i, j = i + 1, j - 1
  84.     quick_sort(nums, start, j)
  85.     quick_sort(nums, i, end)
  86.  
  87.  
  88. def bubble_sort(nums):
  89.     n = 1
  90.     while n < len(nums):
  91.         for i in range(0, len(nums) - n):
  92.             if nums[i] > nums[i + 1]:
  93.                 nums[i], nums[i + 1] = nums[i + 1], nums[i]
  94.         n += 1
  95.  
  96.  
  97. def sort_insert(nums):
  98.     for i in range(0, len(nums)):
  99.         j = i - 1
  100.         current = nums[i]
  101.         while j >= 0 and nums[j] > current:
  102.             nums[j + 1] = nums[j]
  103.             j -= 1
  104.         nums[j + 1] = current
  105.     return nums
  106.  
  107.  
  108. def sort_select(nums):
  109.     for i in range(len(nums)):
  110.         nums_min = i
  111.         for j in range(i + 1, len(nums)):
  112.             if nums[j] < nums[nums_min]:
  113.                 nums_min = j
  114.         nums[i], nums[nums_min] = nums[nums_min], nums[i]
  115.  
  116.  
  117. def merge(left, right):
  118.     nums = []
  119.     while left and right:
  120.         if left[0] < right[0]:
  121.             nums.append(left.pop(0))
  122.         else:
  123.             nums.append(right.pop(0))
  124.     if left:
  125.         nums.extend(left)
  126.     if right:
  127.         nums.extend(right)
  128.     return nums
  129.  
  130.  
  131. def sort_merge1(nums):
  132.     length = len(nums)
  133.     if length >= 2:
  134.         mid = int(length / 2)
  135.         nums = merge(sort_merge(nums[:mid]), sort_merge(nums[mid:]))
  136.     return nums
  137.  
  138.  
  139. def sort_merge(nums):
  140.     nums = sort_merge1(nums)
  141.  
  142.  
  143. def sort_shell(nums):
  144.     n = len(nums)
  145.     gap = n // 2
  146.     while gap > 0:
  147.         for i in range(gap, n):
  148.             intern = nums[i]
  149.             j = i
  150.             while j >= gap and nums[j - gap] > intern:
  151.                 nums[j] = nums[j - gap]
  152.                 j -= gap
  153.             nums[j] = intern
  154.         gap /= 2
  155.         gap = int(gap)
  156.  
  157.  
  158. def sort_radix(nums):
  159.     for i in range(1, len(str(max(nums))) + 1):
  160.         table = [[] for f in range(0, 10)]
  161.         for y in nums:
  162.             table[int((y / pow(10, i)) % 10)].append(y)
  163.         index = 0
  164.         for y in table:
  165.             for o in range(0, len(y)):
  166.                 nums[index] = y[o]
  167.                 index += 1
  168.  
  169.  
  170. def sort_count(nums):
  171.     max_val = max(nums) + 1
  172.     inter = [0] * (max_val + 1)
  173.     for a in nums:
  174.         inter[a] += 1
  175.     i = 0
  176.     for a in range(max_val):
  177.         for c in range(inter[a]):
  178.             nums[i] = a
  179.             i += 1
  180.     return nums
  181.  
  182.  
  183. def tim_sort(nums):
  184.     nums.sort()
  185.  
  186.  
  187. def millis():
  188.     return _time()
  189.  
  190.  
  191. if __name__ == '__main__':
  192.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top