Question

This is on python.

26.1 Lab 6 - Sorting and Runtime Analysis

Introduction

In this lab, we will explore sorting algorithms and perform a practical analysis of algorithm runtimes. In lecture, we have introduced algorithm - or asymptotic - analysis. In theoretical analysis, we care about the behavior of our algorithms out at the asymptotes. Or in other words, as the problem sizes get larger and larger, what functions can we use to bound algorithmic runtime? Does an algorithm's runtime grow at a linear rate to the problem size? Or is it logarithmic? Or Quadratic?

From the theoretical perspective, in our discussion of runtime, we care about the number of operations required for algorithms to complete. This allows us to separate the "runtime" of an algorithm from any individual computer on which it is run. Theoretically, we can analyze the runtime of the Merge Sort algorithm irrespective of any specific hardware.

Practically however, we do care about the actual time it takes for algorithms and programs to complete. In this lab, you will perform a runtime analysis to measure the actual time it takes for sorting algorithms selection sort and merge sort to complete for lists of increasing size. Since, on an individual computer, runtime is a good proxy for an algorithm's Big-O behavior, you will illustrate the runtime behaviors of these two algorithms.

This lab is broken into two parts:

• ZyBooks Coding Portion
• Canvas Runtime Analysis

Once you complete the coding portion for this lab, you will use it to perform a runtime analysis of both Selection Sort and Merge Sort which you will submit through canvas.

Sort Verification

We will start by writing functions to determine whether lists or files contain sorted data.

A) Warm-up

Write a program that checks whether a list of numbers is sorted in increasing order and prints True if the list is sorted in increasing order, and False otherwise. Test your program for several lists.

B) Is Sorted Function

Refactor your program as a function is-sorted(lst) that takes as input a list of numbers, and returns True if the list is sorted in increasing order, and False otherwise.

Pro-tip: Use doctests to test your function for several inputs.

It’s fantastic if you can make your function recursive, but in this case, it’s ok to use loops as well.

C) Is File Sorted Function

Write a function is_file_sorted(filename). This function takes as input a name of the input file containing a list of integer numbers, one number per line, and returns True if the list is sorted in increasing order, and False otherwise. Test your function with several inputs.

Important: Remember to convert string values to integers before testing. Otherwise your numbers will be sorted alphabetically, for example, numbers [1,2,11,12] will be sorted [1,11,12,2], which is not the right order for integers.

Sort Verifier

Now write a sort_verifier(filename) function that, as above, takes as input a name of the input file containing a list of integer numbers, one number per line, and outputs a user-friendly message with the result, as follows:

>>> sort_verifier("input.txt")
Looks like input.txt needs to be sorted

or

>>> sort_verifier("inputsorted.txt")
Congratulations! The file inputsorted.txt is nicely sorted!

Using Sorting Algorithms

Two sorting algorithms have been provided to you in the file sorters.py. In python, we can import and use functions from other modules (other python source files).

Start with carefully studying the implementations of sorting algorithms provided in sorters.py.

Now add the following line to the top of your lab6.py file:

from sorters import selection_sort, merge_sort

Now you can call on these two functions directly from within lab6.py.

A) Merge Sort Write a function use_mergesort(inputfile, outputfile). This function takes as input a name of the input file containing a list of integer numbers, one number per line, and the output file name. This function should read-in numbers from the file, sort them using the provided merge_sort function, and output the sorted numbers to the output file, one number per line.

Important: Remember to convert string values to integers before testing. Otherwise your numbers will be sorted alphabetically, for example, numbers [1,2,11,12] will be sorted [1,11,12,2], which is not the right order for integers.

B) Selection Sort

Write a function use_selection(inputfile, outputfile). This function takes as input a name of the input file containing a list of integer numbers, one number per line, and the output file name. This function should read-in numbers from the file, sort them using the provided selection_sort function, and output the sorted numbers to the output file, one number per line.

C) Random Number Generator

Then write a function generate_nums(filename, n) that makes a file named filename and writes to it n random numbers from 0 to 99, inclusive. Use generate_nums() function to generate files of different size that you would then use for testing your use_mergesort() and use_selection().

Define this function as follows:

def generate_nums(filename, n):
    import random
    random.seed(0)
    # you fill in the rest

In the above, you are importing the module random and setting the random number generator seed to be 0.

Tip: The instruction

num = random.randrange(0, 10)

will generate a single random number in the range 0-9 inclusive.

Seed Explanation:

In programming there is no such thing as a true random number generator. In reality all algorithmic random number generators are "pseudo-random" number generators. Although there are efforts that go to great lengths to actually import randomness into computing systems.

Algorithmic pseudo-random number generators use complex mathematical functions to approximate random sequences of numbers. While the sequences may seem ransom, they are actually deterministic sequences generated by using a "seed" as the input value to the function. Two "random" sequences generated from the same seed will be identical. In your function, by setting the seed to be 0 you are guarantying that your function called with the same n will always return the same sequence of numbers, a great peroperty for testing and reproducibility purposes. In this application, we don't really care if the numbers are truly random, only that they are not ordered.

Development

You may develop your code in ZyBooks and while in development, you may add code to the bottom of your file outside of the functions for testing purposes. When you go to submit, remove all extraneous code (even a call to main()) as any code outside of the functions may break the ZyBooks tests.

Interactive Terminal

For this lab, an interactive terminal has been enabled for you. This is a beta feature of ZyBooks. In the terminal, you can issue the run command to run your program. You can then directly interact with your program on the terminal, entering user input as needed. You can still opt to run and test your programs the old way, by specifying all input in the "Enter program input" box and clicking on the "Run Program" button.

In the interactive terminal, if you write doctests, you can issue the run -v command to print the output of your doctests.

Answer 1

In this question we have written all the programs using python language as instructed in the question and in this question there is a mention of two major sorting algorithms-

selection sort

this sorting algorithm first finds the minimn of the list and then put it in its perfect position and repeats itself for n number of time so that the final list will be sorted but this algorithm uses brute force approach so its time complexity is high

its time complexity of worstcase senerio is

merge sort

this type if sorting algorithms sort by dividing the list into several small parts and then solving the easy part that is merging them according to the values of elements now because of this properties of the merge sort this algorithm uses divide and conquer approach.

the following are the codes and their outputs

A)CODE:

def sor(test_list):
  key = 0
  i = 1
  while i < len(test_list): 
      if(test_list[i] < test_list[i - 1]): 
          key = 1
      i += 1
        
  # printing result 
  if (not key) : 
      print ("True") 
  else : 
      print ("False") 

OUTPUT:

B)CODE:

def is_sorted(test_list):
  key = 0
  i = 1
  while i < len(test_list): 
      if(test_list[i] < test_list[i - 1]): 
          key = 1
      i += 1
        
  # printing result 
  if (not key) : 
      return True 
  else : 
      return False

OUTPUT:

C)

a)CODE:

def is_file_sorted(file_name):
  with open(file_name,mode='r') as list_file:
    lis=[int(x) for x in list_file.readlines()]
  print(is_sorted(lis))

OUTPUT:

b.)CODE:

def sort_verifier(file_name):
  with open(file_name,mode='r') as list_file:
    lis=[int(x) for x in list_file.readlines()]
  ret=is_sorted(lis)
  if (ret==True):
    print("Congratulations! The file "+file_name+" is nicely sorted!")
  else:
    print("Looks like "+file_name+" needs to be sorted")

OUTPUT:

A)CODE:

def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 
  
    # create temp arrays 
    L = [0] * (n1) 
    rr = [0] * (n2) 
  
    # Copy data to temp arrays L[] and rr[] 
    for i in range(0 , n1): 
        L[i] = arr[l + i] 
  
    for j in range(0 , n2): 
        rr[j] = arr[m + 1 + j] 
  
    # Merge the temp arrays back into arr[l..r] 
    i = 0     # Initial index of first subarray 
    j = 0     # Initial index of second subarray 
    k = l     # Initial index of merged subarray 
  
    while i < n1 and j < n2 : 
        if L[i] <= rr[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = rr[j] 
            j += 1
        k += 1
  
    # Copy the remaining elements of L[], if there 
    # are any 
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
  
    # Copy the remaining elements of R[], if there 
    # are any 
    while j < n2: 
        arr[k] = rr[j] 
        j += 1
        k += 1
  

def mergeSort(arr,l,r): 
    if l < r: 
  
        # Same as (l+r)//2, but avoids overflow for 
        # large l and h 
        m = (l+(r-1))//2
  
        # Sort first and second halves 
        mergeSort(arr, l, m) 
        mergeSort(arr, m+1, r) 
        merge(arr, l, m, r) 
  
  
def use_mergesort(inputfile, outputfile):
  with open(inputfile,mode='r') as list_file:
    lis=[int(x) for x in list_file.readlines()]
  mergeSort(lis,0,len(lis)-1) 
  with open(outputfile,mode='w') as outfile:
    for x in lis:
      outfile.writelines("%d\n"%(x)) 

OUTPUT:

B).CODE:

def selection_sort(A):

  for i in range(len(A)):
    min_= i
    for j in range(i+1, len(A)):
      if A[min_] > A[j]:
        min_ = j
    
   #swap
    A[i], A[min_] = A[min_], A[i]

def use_selection(inputfile, outputfile):
  with open(inputfile,mode='r') as list_file:
    lis=[int(x) for x in list_file.readlines()]
  selection_sort(lis) 
  with open(outputfile,mode='w') as outfile:
    for x in lis:
      outfile.writelines("%d\n"%(x))

OUTPUT:

C.)CODE:

import random
random.seed(0)
def generate_nums(filename, n):
  with open(filename ,'w') as file:
    listt=[]
    for x in range(n):
      listt.append(random.randrange(0, 100))
    for j in listt:
      file.writelines("%d\n"%(j))

OUTPUT: