単方向リストの昇順ソートについて

質問

単方向リストに値を入れるところまでは何とか切り抜けることができましたが、次はソートにてこずっています。this.value と this.next.valueの値を比べて入れ替えるというところまでは何とか想像つきますが、どうやってソートが完了するまでまわしてあげればいいかが分かりません。
class Chain3{
public static void main(String args[]){
Node start = new Node(Integer.parseInt(args[0]));
for(int i = 1; i < args.length; i++){
start.append(Integer.parseInt(args[i]));
}
start.sort();
}
}
class Node{
private int value;
private Node next;
public Node(int value, Node next){
this.value = value;
this.next = next;
}
public Node(int value){

this.value = value;
}
public Node(){
this.value = 0;
this.next = null;
}
public int getValue(){
return value;
}
public void setValue(int value){
this.value = value;
}
public Node getNext(){
return next;
}
public void setNext(Node n){
this.next = n;
}
public void append(int v){

if(this.next == null)
this.next = new Node(v);
else
this.next.append(v);
}
//昇順にソートする
public void sort(){
int tmp;
/*ここで私はバブルソートで行おうと思っているのだが、どう回数制限していいか分からない*/
if(this.value > this.next.value){
tmp = this.value;
this.value = this.next.value;
this.next.value = tmp;
}
this.next.sort();
}
}

回答No.2

anmochi · ベストアンサー

論理的に考えていこう。プログラムを組む時に、その関数はどんなタスクを実行して、その行までにどんなタスクが完了していなければならないのか。

public void sort(){
if(this.next == null) { // 自分が1番下ならソート完了
return;
}
this.next.sort(); // 配下のソートが終わるまで待つ(ここで自分の1個下が配下中最も小さな値になる)
if(this.value > this.next.value){ // 自分の方がおっきければ
int tmp = this.value; // 自分と自分の1個下をスワップする(ここで自分の1個下に配下中に配置されるべき値がはいる)
this.value = this.next.value;
this.next.value = tmp;
this.next.sort(); // もう一度配下をソートし直す必要がある
}
}

　後で試してみれば分かるが、実はこのアルゴリズムはバブルソートよりも効率が悪い。改良は頑張ってくれ。
　余談だが、せっかくポインタ数珠繋ぎのリストにしたんだから交換法じゃなくて挿入法の方が良いと思う。それと、値の交換よりもアドレスの交換の方が応用が利くよ。

お礼

返答遅れてゴメンナサイ。
再帰処理が２行があり、多少処理を追うのに苦労しましたが何とか理解できました。ありがとうございます。

回答No.1

taka451213

こんばんは。

よくわかりませんが、単純にNULLになるまで回せばいいような・・・？
回数は可変ですから・・・。
(^^ゞ

補足

具体的にソースで記述するとどのようになりますか?