Demo entry 6638596

py

   

Submitted by anonymous on Sep 08, 2017 at 04:45
Language: Python 3. Code size: 7.0 kB.

import matplotlib.pyplot as plt
from random import *
import time
import copy
import numpy as np

def InsertionSort(input_list):
      for i in range(1,len(input_list)):
            key = input_list[i]
            j = i-1
            while j>=0 and input_list[j]>key:
                  input_list[j+1] = input_list[j]
                  j = j-1
            input_list[j+1] = key

      return input_list


def BubbleSort(input_list):
      for i in range(len(input_list)-1):     
            for j in range(len(input_list)-i-1):                  
                  if input_list[j]>input_list[j+1]:
                        input_list[j], input_list[j+1]= input_list[j+1],input_list[j]
      return input_list


def random_generator(n):
      l =  list(np.random.choice(n, n, replace=True))
      with open("/Users/Yuchen/Documents/random.txt", "w") as f:
          for s in l:
                f.write(str(s) +"\n")
      return l

def non_decreasing_generator(n):
      nums = list(np.random.choice(n, n, replace=True))
      l =  sorted(nums)
      with open("/Users/Yuchen/Documents/non_decreasing.txt", "w") as f:
          for s in l:
                f.write(str(s) +"\n")
      return l

def non_increasing_generator(n):
      nums = list(np.random.choice(n, n, replace=True))
      l =  sorted(nums)[::-1]
      with open("/Users/Yuchen/Documents/non_increasing.txt", "w") as f:
          for s in l:
                f.write(str(s) +"\n")
      return l

def random_number_test():
      
      IS_time = [0 for i in range(25)]
      BS_time = [0 for i in range(25)]
      
      for j in range(10):
            x_axis = []

            for i in range(25):                 
                  n = (i+1)*2000
                  nums1 = []
                  nums2 = []
                  random_generator(n)
                  with open("/Users/Yuchen/Documents/random.txt", "r") as f:
                        for line in f:
                              nums1.append(int(line.strip()))
                              nums2.append(int(line.strip()))
                                           
                  x_axis.append(n)
                  
                  start_time = time.clock()
                  InsertionSort(nums1)
                  end_time = time.clock()
                  IS_time[i] = IS_time[i]  + (end_time-start_time)
                  print('Random: The IS time for size '+str(n)+' for try ' +str(j+1)+' is: '+str(end_time-start_time))
                  

                  start_time = time.clock()
                  BubbleSort(nums2)
                  end_time = time.clock()
                  BS_time[i] = BS_time[i]  + (end_time-start_time)

                  print('Random: The BS time for size '+str(n)+' for try ' +str(j+1)+' is: '+str(end_time-start_time))

      IS_time = [x / 10 for x in IS_time]
      BS_time = [x / 10 for x in BS_time]

      plt.figure(1)
                
      plt.plot(x_axis,IS_time,label = 'Insertion Sort')
      plt.plot(x_axis,BS_time,label = 'Bubble Sort')

      plt.legend(bbox_to_anchor=(0, 1), loc=2, borderaxespad=0.)
      plt.title('Average running time for random numbers for 10 runs')
      plt.xlabel('data size')
      plt.ylabel('running time')
      plt.savefig('/Users/Yuchen/Documents/Random.png')

      return IS_time,BS_time            


def nonincreasing_number_test():
      IS_time = []
      BS_time = []
      x_axis = []
      for i in range(1,26):
            n = i*2000
            nums1 = []
            nums2 = []
            (non_increasing_generator(n))
            with open("/Users/Yuchen/Documents/non_increasing.txt", "r") as f:
                  for line in f:
                        nums1.append(int(line.strip()))
                        nums2.append(int(line.strip()))
            
            start_time = time.clock()
            InsertionSort(nums1)
            end_time = time.clock()
            IS_time.append(end_time-start_time)
            print('Nonincreasing: The IS time for size '+str(n)+' is: '+str(end_time-start_time))
            

            start_time = time.clock()
            BubbleSort(nums2)
            end_time = time.clock()
            BS_time.append(end_time-start_time)
            print('Nonincreasing: The BS time for size '+str(n)+' is: '+str(end_time-start_time))


      plt.figure(2)
           
      plt.plot(x_axis,IS_time,label = 'Insertion Sort')
      plt.plot(x_axis,BS_time,label = 'Bubble Sort')
      plt.legend(bbox_to_anchor=(0, 1), loc=2, borderaxespad=0.)
      plt.title('Running time for nonincreasing numbers')
      plt.xlabel('data size')
      plt.ylabel('running time')
      plt.savefig('/Users/Yuchen/Documents/nonincreasing.png')
      return IS_time,BS_time 

def nondecreasing_number_test():
      IS_time = []
      BS_time = []
      x_axis = []
      for i in range(1,26):
            n = i*2000

            nums1 = []
            nums2 = []
            (non_decreasing_generator(n))
            with open("/Users/Yuchen/Documents/non_decreasing.txt", "r") as f:
                  for line in f:
                        nums1.append(int(line.strip()))
                        nums2.append(int(line.strip()))
            
            start_time = time.clock()
            InsertionSort(nums1)
            end_time = time.clock()
            IS_time.append(end_time-start_time)
            print('Nondecreasing: The IS time for size '+str(n)+' is: '+str(end_time-start_time))
            

            start_time = time.clock()
            BubbleSort(nums2)
            end_time = time.clock()
            BS_time.append(end_time-start_time)
            print('Nondecreasing: The BS time for size '+str(n)+' is: '+str(end_time-start_time))


      plt.figure(3)           
      plt.plot(x_axis,IS_time,label = 'Insertion Sort')
      plt.plot(x_axis,BS_time,label = 'Bubble Sort')
      plt.legend(bbox_to_anchor=(0, 1), loc=2, borderaxespad=0.)
      plt.title('Running time for nondecreasing numbers')
      plt.xlabel('data size')
      plt.ylabel('running time')
      plt.savefig('/Users/Yuchen/Documents/nondecreasing.png')
      return IS_time,BS_time 
      
rand_IS,rand_BS = random_number_test()
rand = [0 for i in range(len(rand_IS))]
for i in range(len(rand_IS)):
	rand[i] = (rand_IS[i],rand_BS[i])

with open("/Users/Yuchen/Documents/random_result.txt", "w") as f:
    for s in rand:
        f.write(str(s) +"\n")
        
nonin_IS,nonin_BS = nonincreasing_number_test()

nonin = [0 for i in range(len(nonin_IS))]
for i in range(len(nonin_IS)):
	nonin[i] = (nonin_IS[i],nonin_BS[i])

with open("/Users/Yuchen/Documents/nonincreasing_result.txt", "w") as f:
    for s in nonin:
        f.write(str(s) +"\n")
        
nonde_IS,nonde_BS = nondecreasing_number_test()
nonde = [0 for i in range(len(nonde_IS))]
for i in range(len(nonde_IS)):
	nonde[i] = (nonde_IS[i],nonde_BS[i])

with open("/Users/Yuchen/Documents/nondecreasing_result.txt", "w") as f:
    for s in nonde:
        f.write(str(s) +"\n")
        

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).