Demo entry 6641748

test

   

Submitted by anonymous on Sep 21, 2017 at 03:08
Language: Python 3. Code size: 10.3 kB.

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

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 quickSort(A,lo,hi):
      if lo<hi:
            p = partition(A,lo,hi)
            quickSort(A, lo, p-1)
            quickSort(A, p+1, hi)

def partition(A,lo,hi):
      pivot = A[hi]
      i = lo - 1
      for j in range(lo,hi):
            if A[j]<pivot:
                  i = i+1
                  A[i],A[j]= A[j],A[i]
      if A[hi] < A[i + 1]:
            A[i+1],A[hi] = A[hi],A[i+1]
      return i+1
            
def MERGE(A,p,q,r):
      left = A[p:q+1]
      right = A[q+1:r+1]
      i = 0
      j = 0
      left.append(99999)
      right.append(99999)
      for k in range(p,r+1):
            if left[i]<=right[j]:
                  A[k] = left[i]
                  i = i+1
            else:
                  A[k] = right[j]
                  j = j+1

def mergeSort(A,p,r):
    if p+1<r:
        q = int((p+r)/2)
        mergeSort(A,p,q)
        mergeSort(A,q+1,r)
        MERGE(A,p,q,r)

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(20)]
      QS_time = [0 for i in range(20)]
      MS_time = [0 for i in range(20)]     
      for j in range(10):
            x_axis = []

            for i in range(20):                 
                  n = (i+1)*500
                  nums1 = []
                  nums2 = []
                  nums3 = []
                  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()))
                              nums3.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()
                  quickSort(nums2,0,len(nums2)-1)
                  end_time = time.clock()
                  QS_time[i] = QS_time[i]  + (end_time-start_time)

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

                  start_time = time.clock()
                  mergeSort(nums3,0,len(nums3)-1)
                  end_time = time.clock()
                  MS_time[i] = MS_time[i]  + (end_time-start_time)

                  print('Random: The MS 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]
      QS_time = [x / 10 for x in QS_time]
      MS_time = [x / 10 for x in MS_time]

      plt.figure(1)
                
      plt.plot(x_axis,IS_time,label = 'Insertion Sort')
      plt.plot(x_axis,QS_time,label = 'Quick Sort')
      plt.plot(x_axis,MS_time,label = 'Merge 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')

      plt.figure(2)
                
      plt.plot(x_axis,QS_time,label = 'Quick Sort')
      plt.plot(x_axis,MS_time,label = 'Merge 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/Random2.png')

      return IS_time,QS_time,MS_time

def nonincreasing_number_test():
      IS_time = []
      QS_time = []
      MS_time = []
      x_axis = []
      for i in range(1,21):
            n = i*500
            nums1 = []
            nums2 = []
            nums3 = []
            x_axis.append(n)
            (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()))
                        nums3.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()
            quickSort(nums2,0,len(nums2)-1)
            end_time = time.clock()
            QS_time.append(end_time-start_time)
            print('Nonincreasing: The QS time for size '+str(n)+' is: '+str(end_time-start_time))


            start_time = time.clock()
            mergeSort(nums3,0,len(nums3)-1)
            end_time = time.clock()
            MS_time.append(end_time-start_time)
            print('Nonincreasing: The MS 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,QS_time,label = 'Quick Sort')
      plt.plot(x_axis,MS_time,label = 'Merge 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')


      plt.figure(4)
      plt.plot(x_axis,QS_time,label = 'Quick Sort')
      plt.plot(x_axis,MS_time,label = 'Merge 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/nonincreasing2.png')
      
      return IS_time,QS_time,MS_time 

def nondecreasing_number_test():
      IS_time = []
      QS_time = []
      MS_time = []
      x_axis = []
      for i in range(1,21):
            n = i*500
            nums1 = []
            nums2 = []
            nums3 = []
            x_axis.append(n)
            (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()))
                        nums3.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()
            quickSort(nums2,0,len(nums2)-1)
            end_time = time.clock()
            QS_time.append(end_time-start_time)
            print('Nonincreasing: The QS time for size '+str(n)+' is: '+str(end_time-start_time))


            start_time = time.clock()
            mergeSort(nums3,0,len(nums3)-1)
            end_time = time.clock()
            MS_time.append(end_time-start_time)
            print('Nonincreasing: The MS time for size '+str(n)+' is: '+str(end_time-start_time))


      plt.figure(5)
           
      plt.plot(x_axis,IS_time,label = 'Insertion Sort')
      plt.plot(x_axis,QS_time,label = 'Quick Sort')
      plt.plot(x_axis,MS_time,label = 'Merge 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')


      plt.figure(6)
      plt.plot(x_axis,QS_time,label = 'Quick Sort')
      plt.plot(x_axis,MS_time,label = 'Merge 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/nondecreasing2.png')
      
      return IS_time,QS_time,MS_time 


sys.setrecursionlimit(20000)
rand_IS,rand_QS,rand_MS = 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_QS[i],rand_MS[i])

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

nonde_IS,nonde_QS,nonde_MS = 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_QS[i],nonde_MS[i])

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

nonin_IS,nonin_QS,nonin_MS = 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_QS[i],nonin_MS[i])

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

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).