COMP
301 Analysis of Algorithms, Fall 2020
Instructur: Zafer Aydın
Lab Assignment 1
Introduction
In this lab you will implement two sorting algorithms: insertion sort and selection
sort. Submit your answers to the questions below in a text file (e.g. Word document).
Name your file in name_surname.docx format. Submit your solution document and
Java codes as a folder in name_surname format to TA through a USB flash disk.
Assignment
1. (a) Implement the insertion sort algorithm given below in Java. Implement the
algorithm as a separate method. You can use the code template insertion.java.
where A is an aray of numbers and the array indices start from 1.
(b) Test your algorithm by choosing an integer array of size 10. Initialize your array by
random numbers. Make sure your program sorts arrays correctly. Include the output of
your program for this sample input in your report.
(c) Compute and compare the time it takes to sort 1000 integers. Repeat this experiment
1000 times (i.e. in each repetition a new random array should be generated and used as
input). Repeat these steps by sorting 10000 integers. Fill the table below for minimum,
average and maximum running times. You can complete implementing the
statistics method in insertion.java.
Minimum Time Average Time Maximum Time
Sorting 1000
integers
Sorting 10000
integers
(d) How much does the average running time increase by changing the input size from
1000 to 10000? For instance, does it increase by 10-fold or 100 fold, etc?
COMP 301 Analysis of Algorithms, Fall 2020
Instructur: Zafer Aydın
Lab Assignment 1
2. Consider sorting n numbers stored in array A by first finding the smallest element of A
and exchanging it with the element in A[1] . Then find the second smallest element of A,
and exchange it with A[2]. Continue in this manner for the first n-1 elements of A. This is
the selection sort algorithm.
(a) Implement this algorithm in Java. Implement the algorithm in a separate method.
You can use the code template selection.java.
(b) Test your algorithm by choosing an integer array of size 10. Initialize your array by
random numbers. Make sure your program sorts arrays correctly. Include the output of
your program for this sample input in your report.
(c) Compute and compare the time it takes to sort 1000 integers. Repeat this experiment
1000 times (i.e. in each repetition a new random array should be generated and used as
input). Repeat these steps by sorting 10000 integers. Fill the table below for minimum,
average and maximum running times. You can complete implementing the
statistics method in selection.java or use the statistics method you
implemented for insertion.java.
Minimum Time Average Time Maximum Time
Sorting 1000
integers
Sorting 10000
integers
(d) How much does the average running time increase by changing the input size from
1000 to 10000? For instance, does it increase by 10-fold or 100 fold, etc?
3. Compare the average running times of insertion sort and selection sort. Which
algorithm performs better? Can you give any reason?
COMP 301 Analysis of Algorithms, Fall 2020
Instructur: Zafer Aydın
Lab Assignment 1
You can find the following Java commands useful in this lab
To import class libraries
import java.util.Arrays;
import java.util.Random;
To generate and store random numbers in an array
int data[ ] = new int[10];
Random rand = new Random();
rand.setSeed(System.currentTimeMillis());
for (int i = 0; i < data.length; i++)
data[i] = rand.nextInt(100);
To measure the running time put the following code before and after your selection sort
block
long startTime = System.currentTimeMillis();
/* Your selection sort block will go here */
long endTime = System.currentTimeMillis();
long elapsed = endTime − startTime;
or you can also use the nanoTime which could be more convenient:
long startTime = System.nanoTime();
/* Your sorting block will go here */
long endTime = System.nanoTime();
long elapsed = endTime − startTime;
