2. Write programs for both insertion sort and mergesort in Python and follow the instructions to execute the programs with the provided data sets below. (15 points)

Using your time efficiency function from HW1, measure the execution times of both insertion and merge sorting algorithms using the attached data files (one with 1,000 integers and the other with 1,000,000 integers ).

In addition, you also compute and display the total number of comparisons to complete each sorting algorithm along with time efficiencies.

• 1,000,000 integers are in rand1000000.txt ,
• 1,000 integers are in rand1000.txt
  • If you are interested in testing the algorithms with other sets of integers:
    • rand10000.txt
    • rand100000.txt
    • rand250000.txt
    • rand500000.txt

Deliverable:

1. 1. 1. Program source codes of both algorithms (insertion and merge sorts)
      2. The summary of your test results in terms of time efficiency tested with multiple data sets (at least, 1K and 1M) for both sorting algorithms (Insertion sort and Merge sort). You may use your own time_efficiency program written for HW1b to measure the time efficiencies of both sorting algorithms.

[Added on Feb 13: How to handle a long running program:

The insertion sort with 1,000,000 integers takes really long time (around 20 hours). This makes difficult to complete the sorting algorithm to the end on a personal computer. Below is how I would do it.

1). On a Unix (Linux) server like csegrid machine, copy the program.

2). Add the following line at the very first line of the program and save the file. This basically tells the Unix OS to run /user/bin/python3 with the Python script (program) in the file. "#!" in this line of code is called "shebang" ('sh' [Unix Bourne shell] + bang , or hash + bang)

#!/usr/bin/python3

3). On the command line, at input prompt, enter the following Unix command to make the file (say "insertionSort.py") executable.

$ chmod +x insertionSort.py

4). Run the following command from the command line to run the code in background.

$ nohup insertionSort.py > hw2sort.txt &

This will run "insertionSort.py" in background by adding "&" at the end of command line. Also the output of the command will be redirected to and stored in hw2sort.txt file instead of displaying on the display. "nohup" at the beginning of the command line tells Unix OS to continue to execute the command at the background even if the current login shell ends (which means you log out from the shell and terminates your putty session).

5). Also you may consider adding following lines to test all the data sizes in one test run for extra credit points

fileNames = ["rand1000.txt", "rand10000.txt", "rand100000.txt", "rand250000.txt" , "rand500000.txt", "rand1000000.txt" ] for name in fileNames :

[your codes ..]

Transcribed image text