목록에 3 개 이상의 개체가있는 경우 내 버블 정렬이 바뀌지 않습니다. JAVA

Question

스택에 개체가 4 개 이상이면 내 버블 정렬이 작동하지 않습니다. 어째서? 내가 푸시면 a, b, c. 버블 정렬은 그들을 정렬합니다 : c, b, 올바른지. 그러나 만약 내가 a, b, c, d. 버블 정렬은 다음과 같이 정렬합니다 : a, d, c, b. 만약 내가 a, b, c, d, e가 있다면. 버블 정렬은 다음과 같이 정렬합니다 : a, b, e, d, c, b.

내 노드 클래스 :

public class Stack implements StackAPI{ 

public Stack(){ 
} 

private Node first = null; 
private int size = 0; 

private class Node implements Comparable<Node>{ 
    String item; 
    Node next; 

    public String getItem(){ 
     return this.item; 
    } 
    public int compareTo(Node other){ 

     if(getItem().compareTo(other.getItem()) > 0){ 
      return 1; 
     } 

     else if(getItem().compareTo(other.getItem()) < 0){ 
      return -1; 
     } 
     else 
      return 0; 
    } 
} 

버블 정렬 기능 :

public void bubbleSort(){ 
    int N = size; 
    boolean swapped = true; 


    while(swapped == true){ 
     Node currentNode = first; 
     swapped = false; 


     for(int i=0; i < N-1; i++){ 
      if(less(currentNode.next, currentNode)){ 

       exch(currentNode); 
       swapped = true; 
      } 

      currentNode = first.next; 
     } 
    } 
} 

덜하고 EXCH 기능 :

private static boolean less(Comparable v, Comparable w){ 
    return v.compareTo(w) < 0; 
} 

private static void exch(Node a) { 
    String swap = a.item; 
    a.item = a.next.item; 
    a.next.item = swap; 
} 

Answer 1

보이는 문제가 여기에 있습니다 :

for(int i=0; i < N-1; i++){ 
     if(less(currentNode.next, currentNode)){ 

      exch(currentNode); 
      swapped = true; 
     } 

     //currentNode = first.next; // <== here? 
     currentNode = currentNode.next; 
    } 

올바른 방법 :

for (Node curr = first, next = curr.next; next != null; next = curr.next) { 
     if (next >= curr) { 
      curr = next; 
      continue; 
     } 
     // update head, if required 
     if (first == curr) { 
      first = next; 
     } 
     // swap elements 
     curr.next = next.next; 
     next.next = curr; 
     swapped = true; 
    }