JAVA : question 1 The selection sort is a combination of searching and sorting.
ID: 3582213 • Letter: J
Question
JAVA : question 1
The selection sort is a combination of searching and sorting. During each pass, the unsorted
element with the smallest (or largest) value is moved to its proper position in the array.
Create a file named Problem1.java (must be named as Problem1.java), then implement the following two methods:
selectionSort and minIndex methods.
public static void selectionSort(int[] list){
//this method is used to sort array in ascending order, and you MUST use the minIndex method within this method
//add code here
}
private static int minIndex(int[] list, int startIndex, int endIndex){
//this method returns the index of the smallest value among the elements as specified
//by startIndex and endIndex. Add your code below
}
Problem 2 (40 points)
The typical operations of a stack ADT include push, top, and pop. The push operation adds an element to the top of the stack;
the pop operation removes the top element of the stack; the top operation returns the top element of the stack.
Write a class named MyStack.java, which implements MyStackInterface, then use the following code to test your stack ADT
(Node: you are not allowed to use any predefined data structures)
public static void main(String[] args){
MyStack s=new MyStack();
s.push(new MyData("1"));
s.push(new MyData("2"));
s.push(new MyData("3"));
while(!s.isEmpty()){
System.out.println((String)(s.top().getData()));
s.pop();
}
}
public class MyData{
private Object data;
private MyData next;
public MyData(Object data){
setData(data);
next=null;
}
public Object getData(){
return data;
}
public MyData getNext(){
return next;
}
public void setData(Object data){
this.data = data;
}
public void setNext(MyData next){
this.next = next;
}
}
interface MyStackInterface{
public boolean isEmpty();
public void push(MyData data);
public MyData top();
public void pop();
}
Explanation / Answer
question 1
public class Problem1 {
public static void selectionSort(int[] list){
//this method is used to sort array in ascending order, and you MUST use the minIndex method within this method
//add code here
int j, tmp;
int n = list.length - 1;
for (j = 0; j < n-1; j++)
{
int iMin = minIndex(list,j,n);
/* test against elements after j to find the smallest */
if(iMin != j)
{
tmp = list[j];
list[j] = list[iMin];
list[iMin] = tmp;
}
}
}
private static int minIndex(int[] list, int startIndex, int endIndex){
//this method returns the index of the smallest value among the elements as specified
//by startIndex and endIndex. Add your code below
int min=startIndex;
for ( int i = startIndex+1; i < endIndex; i++) {
/* if this element is less, then it is the new minimum */
if (list[i] < list[min]) {
/* found new minimum; remember its index */
min = i;
}
}
return min;
}
}
//------------------------------------------------------------------------------------------------
Problem 2
public class MyStack implements MyStackInterface {
MyData start = null;
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
if(start == null)
return true;
else return false;
}
@Override
public void push(MyData data) {
// TODO Auto-generated method stub
data.setNext(start);
start = data;
}
@Override
public MyData top() {
// TODO Auto-generated method stub
return start;
}
@Override
public void pop() {
start = start.getNext();
}
}
// rest of the classes remain same
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.