버블 정렬을 사용하여 링크드 목록을 정렬 할 때이 코드가 올바르게 작동하지 않는 이유는 무엇입니까?

Question

다음과 같이 LinkedList를 사용하여 버블 정렬을 구현했습니다. 나는이 문제에 대한 정확하고 효율적인 해결책을 찾을 수 없다. 효율성을 높이기 위해이 코드에서 어떤 변화가 필요합니다. 누군가가 연결 목록에 버블 정렬을보다 효율적으로 구현한다면 그것을 제공하십시오.

class SortList { 
    int size; 
    Node head; 
    class Node{ 
    int data; 

    Node next; 
    Node(int data){ 
     this.data = data; 
     this.next = null; 
     } 
    Node(){ 
     this.data = 0; 
     this.next = null; 
    } 
    } 

    public void push(int d) { 
     Node newNode = new Node(); 

     newNode.data = d; 

     newNode.next = head; 

     head = newNode; 
     size++; 
    } 
    public void display(){ 
    Node n = head; 
    while(n!=null){ 
     System.out.print(n.data +" "); 

     n = n.next; 
     } 
    } 
    public int getLength(){ 
     int count=0; 
     Node n = head; 
     while(n!=null){ 
      count++; 
      n = n.next; 
      } 
      return count; 
    } 
    public int getLengthR(Node n){ 

      if(n==null) return 0; 
      return 1+getLengthR(n.next); 

    } 
    public int getL(){ 
    return getLengthR(head); 
    } 
    public static void main(String[] args) { 
     SortList ls = new SortList(); 
    int[]arrList = {5,2,7,3,1,2}; 
    for(int i=0;i<arrList.length;i++){ 
     ls.push(arrList[i]); 
     } 
     ls.display(); 

     ls.sortList(); 

     ls.display(); 
    } 

    public void sortList(){ 
    if(size > 1){ 
     Node node = head; 
     Node nextNode = head.next; 
      for(int i=0;i<size;i++){ 

      for(int j=0;j<size - i - 1;j++){ 
       while(node.data > nextNode.data){ 
        Node temp =node; 
        node = nextNode; 
        nextNode = temp; 
       } 
       node = nextNode; 
       nextNode = nextNode.next; 
      } 
     } 

     } 
    } 
} 

Answer 1

주석에서 제안한 StackOverFlow 답변을 확인해야합니다. 약간 다른 전술을 사용하여 정렬 방법을 수정했습니다. 노드를 교체하는 대신 노드의 값을 교체했습니다. 스 왑해야 할 수도있는 정렬 목적으로 사용하지 않는 노드와 연관된 다른 데이터가있을 수 있으므로 항상 적용 가능한 것은 아닙니다.

기본적으로 아래의 방법은 각 패스 후에 목록의 크기를 1 줄이는 것입니다. 이는 변수 terminal을 사용하여 방금 올바른 위치에 놓인 노드를 추적함으로써 수행됩니다.

public void sortList(){ 
    if(size > 1){ 
     Node terminal = null; 
     while (head.next != terminal) { 
      Node node = head; 
      Node nextNode = head.next; 

      while (nextNode != terminal) { 
       if(node.data > nextNode.data){ 
        int temp =node.data; 
        node.data = nextNode.data; 
        nextNode.data = temp; 
       } 
       node = nextNode; 
       nextNode = nextNode.next; 
      } 
      terminal = node; 
     } 
    } 
}