Three Things on Format Include a header at the top of you source code that inclu

Question

Three Things on Format
Include a header at the top of you source code that includes the lab #, your name, date, problem description etc.
When naming the file use you username and the lab number For example: jsmithLab1.java
Your code is going to be read make sure to format it correctly (i.e. indent all blocks)

Lecture 2: Chapter 8 Programming Exercise 18 No PLTL

See book as formating of algorithum is not shown well

18. Merge Sort

Write a recursive method mergeSort(int[] a, int start, int finish) that sorts an array of

integers a from index start through index finish. Test your method with an array test

of 100 random numbers.

The algorithm works as follows:

Explanation / Answer

// mergesort.java 1-12-13 mergesort

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;

public class MergeSort {


public static int[] mergeSort(int [] list) {
if (list.length <= 1) {
return list;
}

// Split the array in half
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);

// Sort each half
mergeSort(first);
mergeSort(second);

// Merge the halves together, overwriting the original array
merge(first, second, list);
return list;
}

private static void merge(int[] first, int[] second, int [] result) {
// Merge both halves into the result array
// Next element to consider in the first array
int iFirst = 0;
// Next element to consider in the second array
int iSecond = 0;

// Next open position in the result
int j = 0;
// As long as neither iFirst nor iSecond is past the end, move the
// smaller element into the result.
while (iFirst < first.length && iSecond < second.length) {
if (first[iFirst] < second[iSecond]) {
result[j] = first[iFirst];
iFirst++;
} else {
result[j] = second[iSecond];
iSecond++;
}
j++;
}
// copy what's left
System.arraycopy(first, iFirst, result, j, first.length - iFirst);
System.arraycopy(second, iSecond, result, j, second.length - iSecond);
}





public static void main(String args[]) throws Exception
{
String list="";
int i=0,n=0;

MergeSort s= new MergeSort();
ArrayList<Integer> arrlist=new ArrayList<Integer>();
System.out.println(" ");
System.out.println(" ");
System.out.println("Please enter the list of elements,one element per line");
System.out.println(" write 'STOP' when list is completed ");
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
while(!(list=bf.readLine()).equalsIgnoreCase("stop")){
int intelement=Integer.parseInt(list);
arrlist.add(intelement);

}
  
int elementlist[] = new int[arrlist.size()];
Iterator<Integer> iter = arrlist.iterator();
for (int j=0;iter.hasNext();j++) {
elementlist[j] = iter.next();
}
  
elementlist=mergeSort(elementlist);
System.out.println(" ");
System.out.println(" ");
System.out.println(" ");
System.out.println("Values after Merge Sort : ");
for (int j=0;j<elementlist.length;j++) {
System.out.println(elementlist[j]+" ");
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.