[解決済み】Javaでリンクリストを手動でバブルソートする

質問

ここで初めて質問させていただきます。 私はjavaで整数のリンクリストを手動でソートしようとしていますが、私のコードの何が間違っているのかがわかりません。何か提案はありますか？エラーは出ませんが、出力が順番通りにならないのです。いくつかの方法を試してみましたが、うまくいきませんでした。どなたか助けていただけると幸いです。

public class Node {

    int data; 
    Node nextNode;

    public Node(int data) {
        this.data = data;
        this.nextNode = null;       
    }

    public int getData() {
        return this.data;
    }
} // Node class


public class DataLinkedList implements DataInterface {  
    private  Node head;
    private int size; 

    public DataLinkedList(){
        this.head = null;
        this.size = 0;
    }

    public void add(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
        } else {
            Node currentNode = head;
            while(currentNode.nextNode != null) {
                currentNode = currentNode.nextNode;
            }
            currentNode.nextNode = node;
        }
        size++;     
    }

    public void sort() {
        if (size > 1) {
            for (int i = 0; i < size; i++ ) {
                Node currentNode = head;
                Node next = head.nextNode;
                for (int j = 0; j < size - 1; j++) {
                    if (currentNode.data > next.data) {
                        Node temp = currentNode;
                        currentNode = next;
                        next = temp;
                    } 
                    currentNode = next;
                    next = next.nextNode;                   
                } 
            }
        }
    }

    public int listSize() {     
        return size;
    }

    public void printData() {
        Node currentNode = head;
        while(currentNode != null) {
            int data = currentNode.getData();
            System.out.println(data);
            currentNode = currentNode.nextNode;
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }
} // DataInterface class

public class DataApp {

    public static void main (String[]args) {

        DataLinkedList dll = new DataLinkedList();

        dll.add(8);
        dll.add(7);
        dll.add(6);
        dll.add(4);
        dll.add(3);
        dll.add(1);

        dll.sort();
        dll.printData();
        System.out.println(dll.listSize());
    }
} // DataApp class

解決方法は？

問題は、予想通り、メソッドにあります。 sort() :

public void sort() {
        if (size > 1) {
            for (int i = 0; i < size; i++ ) {
                Node currentNode = head;
                Node next = head.nextNode;
                for (int j = 0; j < size - 1; j++) {
                    if (currentNode.data > next.data) {
                        Node temp = currentNode;
                        currentNode = next;
                        next = temp;
                    } 
                    currentNode = next;
                    next = next.nextNode;                   
                } 
            }
        }
    }

細かい問題ですが、バブルソートは常にn*n回実行されます。実際には、リスト内の任意のペアの間に変化があったかどうかをチェックする方がよいでしょう。もし変更があれば、リスト全体をもう一度実行する必要がありますし、そうでなければ必要ありません。100個の要素を持つリストが、次のようなときにすでにソートされているという限界的なケースを考えてみましょう。 sort() が呼び出されます。これは、実際には何もすることがないのに、リスト内のノードが10000回実行されることを意味します。

しかし、一番の問題は、リスト内のノードへのポインタを交換していることです。

if (currentNode.data > next.data) {
    Node temp = currentNode;
    currentNode = next;
    next = temp;
} 

を翻訳した場合 カレントノード によって v[i] と 次 によって v[i - 1] というように、配列を並べ替えるようにすればよいのです。しかし、これはリスト上で実行するポインタを変更するだけで、リスト自体には影響がありません。最良の解決策は、（まあ、もしあなたが バブルソート これは常に最悪の解決策ですが）ノード内でデータを交換することでしょう。

if (currentNode.data > next.data) {
    int temp = currentNode.data;
    currentNode.data = next.data;
    next.data = temp;
}

しかし、コンセプトの説明のために、ノード間のリンクを変更することを提案しようと思う。これらのポインターは、実際にリスト内のソートをマークするものです。私が言っているのは nextNode 属性は ノード クラスがあります。

チャットはもういい、これでいい。

public void sort() {
        if (size > 1) {
            boolean wasChanged;

            do {
                Node current = head;
                Node previous = null;
                Node next = head.nextNode;
                wasChanged = false;

                while ( next != null ) {
                    if (current.data > next.data) {
                        /*
                        // This is just a literal translation
                        // of bubble sort in an array
                        Node temp = currentNode;
                        currentNode = next;
                        next = temp;*/
                        wasChanged = true;

                        if ( previous != null ) {
                            Node sig = next.nextNode;

                            previous.nextNode = next;
                            next.nextNode = current;
                            current.nextNode = sig;
                        } else {
                            Node sig = next.nextNode;

                            head = next;
                            next.nextNode = current;
                            current.nextNode = sig;
                        }

                        previous = next;
                        next = current.nextNode;
                    } else { 
                        previous = current;
                        current = next;
                        next = next.nextNode;
                    }
                } 
            } while( wasChanged );
        }
    }

ノード交換を管理するコードが "double" である理由は、ノード間のリンクを変更する必要があり、これは単なる単一のリンクリストなので、前のノード（ヘッダーノードもない）を追跡する必要があるからで、初回が head .

if ( previous != null ) {
    Node sig = next.nextNode;

    previous.nextNode = next;
    next.nextNode = current;
    current.nextNode = sig;
} else {
    Node sig = next.nextNode;

    head = next;
    next.nextNode = current;
    current.nextNode = sig;
}

IdeOneにあるコードは、こちらです。 http://ideone.com/HW5zw7

お役に立てれば幸いです。