I need some help! I am trying to make a merge sort sortMe method to the IntList
ID: 662919 • Letter: I
Question
I need some help! I am trying to make a merge sort sortMe method to the IntList class, so that x.sortMe() returns no value but has the side effect of sorting the contents of the IntList x into non-decreasing order.
Here are my current classes:
import javax.xml.soap.Node;
public class IntList {
private ConsCell start;
public IntList(ConsCell s){
start = s;
}
public IntList cons (int h){
return new IntList(new ConsCell(h, start));
}
public int length(){
int len = 0;
ConsCell cell = start;
while (cell != null){
len++;
cell = cell.getTail();
}
return len;
}
public void print(){
System.out.print("[");
ConsCell a = start;
while(a != null){
System.out.print(a.getHead());
a = a.getTail();
if (a != null) System.out.print(",");
}
System.out.println("]");
}
//
// Reverses the order of the elements in the List.
//
public IntList reverse()
{
IntList Reverselist = new IntList(null);
ConsCell begin = start;
while (begin != null) {
Reverselist = Reverselist.cons(begin.getHead());
begin = begin.getTail();
}
return Reverselist;
}
}
public class Driver {
public static void main(String[] args){
IntList a = new IntList(null);
IntList b = a.cons(2);
IntList c = b.cons(1);
IntList d = c.reverse();
int x = a.length() + b.length() + c.length();
a.print();
b.print();
c.print();
System.out.println(x);
System.out.println("And now for the reversed list...");
d.print();
System.out.println("And now, for the merge sort");
d.sortMe(null, 1, 2);
}
}
public class ConsCell {
private int head;
private ConsCell tail;
public ConsCell(int h,ConsCell t){
head = h;
tail = t;
}
public int getHead(){
return head;
}
public ConsCell getTail(){
return tail;
}
public void setTail(ConsCell t){
tail = t;
}
}
Thank you!
Explanation / Answer
ConsCell get(int i){
ConsCell cell = start;
while (cell != null && i > 1){
cell = cell..getTail();
i--;
}
return cell;
}
void sortMe(){
int len = length();
for (int i = 1; i <= len; i++){
ConsCell c1 = get(i);
for (int j = 1; j <= len; j++){
if (j == i)
continue;
ConsCell c2 = get(j);
if (c1.getHead() > c2.getHead()){
ConsCell temp = c2.getTail();
c1.setTail(temp);
c2.setTail(c1);
}
}
}
}