Java: сортировка пузырьков в связанном списке не работает должным образом - PullRequest
Новая
       13

Java: сортировка пузырьков в связанном списке не работает должным образом

0 голосов
/ 10 февраля 2020

У меня есть пузырьковая сортировка, которая работает со связанным списком, созданным из данных в файле. Мой алгоритм сортировки не работает, если число меньше моего начального главного узла. Как я могу обновить свой код, чтобы исправить это?

пример: если мой список 3, 1, 8, 5, он напечатает 3 -> 5 -> 8, а 1 - это не то место, которое нужно увидеть 

    public void bubbleSort(LinkedNode head) {

        LinkedNode previous; 
        LinkedNode current; 
        LinkedNode next; 

        boolean isSorted = true;

        //if list is empty or only 1 item is in list -> it is sorted
        if (head == null || head.getNext() == null) {
            return;
        }

        long start = System.currentTimeMillis(); //begin count for bubbleSort

        while(isSorted) {
            bubbleComparisons = 0;
            bubbleExchanges = 0;
            previous = null;
            current = head;
            next = head.getNext();
            isSorted = false;

               while(next != null) {
                    bubbleComparisons ++; //increment counter for each comparison made

                    if (current.getElement() > next.getElement()) {
                        if (head == current) {
                            head = next;
                        }
                        else {
                            previous.setNext(next);
                        }
                        current.setNext(next.getNext());
                        next.setNext(current);
                        isSorted = true;
                        current = next;
                        bubbleExchanges++;    

                    }
                    previous = current;
                    current = previous.getNext();
                    next = current.getNext();
            }

1 Ответ

0 голосов
/ 10 февраля 2020

Пара обновлений кода. Я пометил их // Вверх . Я провел несколько тестовых случаев, просто проверь, решает ли это цель. 

public class Solution {
  static class LinkedNode {

    private int element;
    private LinkedNode next;

    LinkedNode(int element) {
      this.element = element;
    }

    public int getElement() {
      return element;
    }

    public void setElement(int element) {
      this.element = element;
    }

    public LinkedNode getNext() {
      return next;
    }

    public void setNext(LinkedNode next) {
      this.next = next;
    }

  }

  private int bubbleComparisons;
  private int bubbleExchanges;

  public LinkedNode bubbleSort(LinkedNode head) {

    LinkedNode previous;
    LinkedNode current;
    LinkedNode next;

    boolean isSorted = true;

    // if list is empty or only 1 item is in list -> it is sorted
    if (head == null) {
      return null;
    } else if (head.getNext() == null) {
      return head;
    }

    while (isSorted) {
//      bubbleComparisons = 0; // Up - 08
//      bubbleExchanges = 0;  // Up - 09
      previous = null;
      current = head;
      next = head.getNext();
      isSorted = false;

      while (next != null) {
        bubbleComparisons++; // increment counter for each comparison made

        if (current.getElement() > next.getElement()) {
          if (head == current) {
            head = next;
          } else {
            previous.setNext(next);
          }
          current.setNext(next.getNext());
          next.setNext(current);
          isSorted = true;
          previous = next; // Up - 01
          // current = next; // Up - 02
          next = current.next; // Up - 03
          bubbleExchanges++;
        } else { // Up - 06
          previous = current;
          current = current.getNext(); // Up - 10 not required
          next = current.getNext();
        }
      }
    }
    return head; // Up - 05
  }

  public static void main(String[] args) {
    LinkedNode head = new LinkedNode(10);
    head.setNext(new LinkedNode(8));
    head.getNext().setNext(new LinkedNode(7));
    head.getNext().getNext().setNext(new LinkedNode(5));

    LinkedNode current = head;
    while (current != null) {
      System.out.print(current.element + "->");
      current = current.next;
    }
    System.out.println();
    Solution s = new Solution();
    current = s.bubbleSort(head);
    while (current != null) {
      System.out.print(current.element + "->");
      current = current.next;
    }
    System.out.println();
    System.out.println("comp:" + s.bubbleComparisons);
    System.out.println("exh:" + s.bubbleExchanges);
  }
}
...