DESCRIPTION In this programming Assignment you are expected to code, run and eva
ID: 675267 • Letter: D
Question
DESCRIPTION
In this programming Assignment you are expected to code, run and evaluate different sorting
algorithms. You should design tests for measuring run time of each algorithm based on the
input size. For turning in this assignment you will submit you folder containing all required
documents and the deadline is in two weeks. Make sure your submission has the following
criteria:
• You should submit all the codes for different task in a separate file
• Your code should be easily readable and should be well commented for each part
• You will submit a written file that contains documentation and details about your implementations.
This file will contain you final results and evaluations
• for visualizing your results you are allowed to use any software you like such as excel, R
orMatlab and that is only for charts and graph you are asked to submit
• for the specific questions and algorithms you are expected to turn in your own code. It
should not be copied from the internet. A code checking software will be ran on your
codes and the least punishment for a violation would be complete denial of the grades.
• Report document is very important. Every submissionwithout a report will be regarded
as not submitted.
• Your code should be in Java.
1
RANDOM ARRAY GENERATOR
Write a program that generates an array of arbitrary size with integer elements. Your input
should take the array size for this specific assignment and should write down the output in a
file with each element of the array in one line exactly.
SORTING ALGORITHMS
Implement three sorting algorithms. Bubble sort, Insertion sort andMerge sort. Each of your
algorithms should take a text file with one element in each line as input and produce an output
of the same format. And you are not allowed to use soring libraries for implementation.
Your algorithms should bemade from the scratch.
TIME EVALUATION
Modify your code for each algorithm in such a way that the programtakes an array of integers
as input size, sorts them and output the total runtime for the algorithm.
EFFICIENCY MEASURE
Use your last three sections to create an evaluation program. Your program runs on each
algorithm on a broad range of different input size. for testing each algorithm you should
exhaust your memory i.e. for each sorting algorithm start from a small size array, 10 for example,
run the algorithm and save the ouput, and make the array size bigger and run again.
You should do this until your program takes more than 5 minutes to calculate the run time.
For each algorithm save the input size vs runtime in a separate file and visualize it using any
method you like. (hint: your input should grow exponential and for ploting you will need to
use log-log plot).
REPORT
Report all the graphs, runtimes and psuedo code for you implementation in the report document.
If some part of your code does not work write it down in the report. The report should
be submitted only in PDF format.
BONUS
Apply everything discussed here to QuickSort
Explanation / Answer
RANDOME NUMBERS:
import java.util.Random;
public class RandomNumbers
{
public static void main(String args[]){
Random rm = new Random();
int array [] = new int[10];
if(array.length==0)
System.out.print("not possible");
for(int i = 0; i <array.length; i++){
array[i] = rm.nextInt(13768) ;
}
int max = array[0];
System.out.println("Random Array is");
for( int j = 0; j< array.length; j++ ){
System.out.println(array[j]);
if(array[j] > max){
max = array[j];
}
}
System.out.println("Maximum Number "+ max);
}
}
INSERTION SORTING:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
public class InsertionSort {
public static int[] insertionSorting(int[] list) {
for (int p = 1; p < list.length; p++) {
int next = list[p];
int q= p;
while (q > 0 && list[q - 1] > next) {
list[q] = list[q - 1];
q--;
}
list[q] = next;
}
return list;
}
public static void main(String args[]) throws Exception
{
String list="";
int p=0,n=0;
InsertionSorting s= new InsertionSorting();
ArrayList<Integer> arrlist=new ArrayList<Integer>();
System.out.println(" ");
System.out.println(" ");
System.out.println(" Enter the list of elements");
System.out.println(" Stop the entering ");
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
while(!(list=bf.readLine()).equalsIgnoreCase("stop")){
int intnumber=Integer.parseInt(list);
arrlist.add(intnumber);
}
int numberlist[] = new int[arrlist.size()];
Iterator<Integer> iter = arrlist.iterator();
for (int q=0;iter.hasNext();q++) {
numberlist[q] = iter.next();
}
numberlist=insertionSorting(numberlist);
System.out.println(" ");
System.out.println(" ");
System.out.println(" ");
System.out.println("Values after Insertion Sorting : ");
for (int q=0;q<numberlist.length;q++) {
System.out.println(numberlist[q]+" ");
}
}
}
BUBBLE SORTING
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
public class BubbleSorting {
public static int[] bubbleSorting(int[] list) {
for (int p = (list.length - 1); p >= 0; p--) {
for (int q = 1; q <= p; j++) {
if (list[q - 1] > list[q]) {
int temp = list[q - 1];
list[q - 1] = list[q];
list[q] = temp;
}
}
}
return list;
}
public static void main(String args[]) throws Exception
{
String list="";
int p=0,n=0;
BubbleSorting s= new BubbleSorting();
ArrayList<Integer> arrlist=new ArrayList<Integer>();
System.out.println(" ");
System.out.println(" ");
System.out.println(" enter list of elements");
System.out.println(" stop ");
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
while(!(list=bf.readLine()).equalsIgnoreCase("stop")){
int intnumber=Integer.parseInt(list);
arrlist.add(intnumber);
}
int numberlist[] = new int[arrlist.size()];
Iterator<Integer> iter = arrlist.iterator();
for (int q=0;iter.hasNext();q++) {
numberlist[q] = iter.next();
}
numberlist=bubbleSorting(numberlist);
System.out.println(" ");
System.out.println(" ");
System.out.println(" ");
System.out.println("Values after Sorting : ");
for (int q=0;q<numberlist.length;q++) {
System.out.println(numberlist[q]+" ");
}
}
}
MERGE SORTING
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
public class MergeSorting{
public static int[] mergeSorting(int [] list) {
if (list.length <= 1) {
return list;
}
int[] first = new int[list.length / 2];
int[] second = new int[list.length - first.length];
System.arraycopy(list, 0, first, 0, first.length);
System.arraycopy(list, first.length, second, 0, second.length);
mergeSorting(first);
mergeSorting(second);
merge(first, second, list);
return list;
}
private static void merge(int[] first, int[] second, int [] result) {
int pFirst = 0;
int pSecond = 0;
int q = 0;
while (pFirst < first.length && pSecond < second.length) {
if (first[pFirst] < second[pSecond]) {
result[q] = first[pFirst];
pFirst++;
} else {
result[j] = second[pSecond];
pSecond++;
}
q++;
}
System.arraycopy(first, pFirst, result, q, first.length - pFirst);
System.arraycopy(second, pSecond, result, q, second.length - pSecond);
}
public static void main(String args[]) throws Exception
{
String list="";
int p=0,n=0;
MergeSort s= new MergeSort();
ArrayList<Integer> arrlist=new ArrayList<Integer>();
System.out.println(" ");
System.out.println(" ");
System.out.println("enter the list of elements");
System.out.println(" 'STOP' ");
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
while(!(list=bf.readLine()).equalsIgnoreCase("stop")){
int intnumber=Integer.parseInt(list);
arrlist.add(intnumber);
}
int numberlist[] = new int[arrlist.size()];
Iterator<Integer> iter = arrlist.iterator();
for (int q=0;iter.hasNext();q++) {
numberlist[q] = iter.next();
}
numberlist=mergeSort(numberlist);
System.out.println(" ");
System.out.println(" ");
System.out.println(" ");
System.out.println("Values after Sorting : ");
for (int q=0;q<numberlist.length;q++) {
System.out.println(numberlist[q]+" ");
}
}
}
Time evalution and efficiency measure :Variations in numbers or time recorded varies from computer to computer .
if the code change to prit 10 numbers the three sortings run time is 0 milisecoonds
for 1000 elements merge sort is taking 1 milliseconds,bubble sort is taking 2 milliseconds , insertion sort is taking 0 mllisecons. for 100000 elements the merge sort took 97 milliseconds,100000 elements the Bubble sort took 19096 milliseconds,100000 elements the insertion sort took 3 milliseconds.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.