I need help with the following code for my JAVA class. This has to be done using
ID: 3663800 • Letter: I
Question
I need help with the following code for my JAVA class. This has to be done using Eclipse. Also to be written using the following code I wrote:
public class Utility {
public static void Swap(int []a, int swap1, int swap2){
int swap=a[swap1];
a[swap1]=a[swap2];
a[swap2]= swap;
}
public static void print(int[] array){
System.out.print("[" + array[0]);
for(int i = 1; i < array.length; i++)
System.out.print(array[i] + ", ");
System.out.print("]");
}
public static boolean isAscending(int[] array){
for(int i = 0; i < array.length - 1; i++)
if(array[i] > array[i + 1])
return false;
return true;
}
public static int[] randomArray(int size){
int[] array = new int[size];
for(int i = 0; i<array.length; i++)
array[i] = (int)(Math.random() * 99);
return array;
}
public static int linearSearch(int[] array, int target){
for(int i = 0; i< array.length; i++){
if(array[i] == target){
return i;
}
}
return -1;
}
}
Create a new class, name it Sorter. All methods in this class are static. You will implement 4 different sorting algorithms in this class in the next week or two.
Place a static boolean data field in your class. Call it debug. Set it to true. This will be used to control some debug outputs for the sorting assignments. When set to false, your methods will work without the excess output.
For this assignment, you will implement selection sort. The method should be named selectionSort. It has an array of ints as its only parameter, and returns nothing. In this method, you should:
Initialize two counters to 0. One for comparisons, one for assignments.
Perform selection sort on the array to sort it into ascending order.
While performing selection sort, any time two values are compared, increment the comparison count by 1. Any time a value is stored into any entry of the array, increment assignment count by 1. (If you call on swap, increment it by 2)
If debug is set to true, display the number of comparisons and assignments done during the sorting process.
For selection sort, the number of comparisons done should be O(n2), and the number of assignments to the array should be O(n). Write a test program and verify this by using different sized arrays and looking at the counts.
Explanation / Answer
A sorting algorithm rearranges the elements of a collection so that they are stored in sorted order.The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.
The selection sort works as follows: you look through the entire array for the smallest element, once you find it you swap it (the smallest element) with the first element of the array. Then you look for the smallest element in the remaining array (an array without the first element) and swap it with the second element. Then you look for the smallest element in the remaining array (an array without first and second elements) and swap it with the third element, and so on. Here is an example,
Example.
29, 64, 73, 34, 20,
20, 64, 73, 34, 29,
20, 29, 73, 34, 64
20, 29, 34, 73, 64
20, 29, 34, 64, 73
The worst-case runtime complexity is O(n2).
public class SortbySelection
{
public SortbySelection( int [] OneArray)
{
a = OneArray[15];
}
public void sort()
{
for(int i = 0; i < a.length-1; i++)
{
int minPos = minimumPosition(i);
swap(minPos, i);
}
}
private int minimumPosition(int from){
int minPos = from;
for(int i = from + 1; i < a.length; i++)
if(a[i] < a[minPos]) minPos = i;
return minPos;
}
private void swap( int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private int [] a;
}
public class SortbySelectionTester
{
public static void main(String[] args)
{
int [] a = ArrayUtil.randomIntArray(20, 100);
ArrayUtil.print(a);
SortbySelection sorter = new SortbySelection(a);
sorter.sort();
ArrayUtil.print(a);
}
}