fork download
copy 
  1. # name: Marilyn Mao
  2. # email: m_mao4@yahoo.com
  3. # program: benchmark.py
  4.  
  5. import random
  6. import time
  7. import timeit
  8. from timeit import Timer
  9.  
  10. def bubbleSort(aList): # sort list in place 
  11.     for passnum in range(len(aList) - 1, 0, -1):
  12.         for i in range(passnum):
  13.             if aList[i] > aList[i + 1]:
  14.                 temp = aList[i]
  15.                 aList[i] = aList[i + 1]
  16.                 aList[i + 1] = temp
  17.  
  18.  
  19. def mergeSort(aList): # sort list in place
  20.     if len(aList) > 1:
  21.         mid = len(aList) // 2
  22.         lefthalf = aList[:mid]
  23.         righthalf = aList[mid:]
  24.  
  25.         mergeSort(lefthalf)
  26.         mergeSort(righthalf)
  27.  
  28.         i = 0
  29.         j = 0
  30.         k = 0
  31.         while i < len(lefthalf) and j < len(righthalf):
  32.             if lefthalf[i] < righthalf[j]:
  33.                 aList[k] = lefthalf[i]
  34.                 i = i + 1
  35.             else:
  36.                 aList[k] = righthalf[j]
  37.                 j = j + 1
  38.             k = k + 1
  39.  
  40.         while i < len(lefthalf):
  41.             aList[k] = lefthalf[i]
  42.             i = i + 1
  43.             k = k + 1
  44.  
  45.         while j < len(righthalf):
  46.             aList[k] = righthalf[j]
  47.             j = j + 1
  48.             k = k + 1
  49.  
  50.  
  51. def bigList(n): # creates a list of 1 to in in random order
  52.     theList = [i+1 for i in range(n)] # 1,2,3,... n
  53.     random.shuffle(theList) # randomly shuffle elements
  54.     return theList
  55.  
  56.  
  57. # DO NOT MODIFY defs above this line
  58. # -------------------------------------------
  59. # Add your code after this comment block to plot the time it takes to run
  60. # the previous functions bubbleSort(aList), mergeSort(aList)
  61. # on a list created by calling bigList(n) with n at different sizes in
  62. # range(1000,10000,1000)
  63. #
  64. # Use timeit or the time method to time how log bubbleSort and mergeSort take to
  65. # run on a list of n size created by calling bigList(n), make sure to call
  66. # bigList(n) once for timing each function for every value of n
  67. # Print the timings in a tab delimited table as shown below using
  68. #   print( n, t1, t2, sep='\t') # where t1 is the time for merge and t2 is time for bubble
  69. #
  70. # Here is a example of the form your output should look like
  71. # NOTE the <tab> just shows you that there will be tabs between each column
  72. # Also make sure to print the headings at the top before you loop starts
  73. # when you call timeit, set number equal to 1 !
  74.  
  75. # N  <tab>  merge  <tab>  bubble
  76. # 1000  <tab>  0.0136160  <tab>  0.21380919
  77. # 2000  <tab>  0.0329329  <tab>  0.81959286
  78. # 3000  <tab>  0.0413493  <tab>  1.83145118
  79. # 4000  <tab>  0.0569270  <tab>  3.32819083
  80. # 5000  <tab>  0.0708057  <tab>  5.15382035
  81. # 6000  <tab>  0.0868657  <tab>  7.44444825
  82. # 7000  <tab>  0.1045654  <tab>  10.2676698
  83. # 8000  <tab>  0.1207415  <tab>  13.6543210
  84. # 9000  <tab>  0.2433110  <tab>  17.4238122
  85.  
  86.  
  87. timeMerge = Timer("mergeSort(aList)",
  88.                 "from __main__ import mergeSort, aList")
  89. timeBubble = Timer("bubbleSort(aList)",
  90.                "from __main__ import bubbleSort, aList")
  91.  
  92.  
  93. print("N\tMerge\tBubble")
  94. for n in range(1000, 10000, 1000):
  95.     x = list(range(n))  # create new list the size of the control variable n using bigList(n) -
  96.     aList = x  # assign new list to aList
  97.     t1 = timeMerge.timeit(number=1)
  98.     x = list(range(n))
  99.     aList = x
  100.     t2 = timeBubble.timeit(number=1)
  101.  
  102. print("%15d\t%15.5f\t%15.5f" % (n, t1, t2))
  103.  
  104.  
Time limit exceeded #stdin #stdout 5s 38128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cobItg
language:
Python 3 (python  3.12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!