Nano Hash - криптовалюты, майнинг, программирование

Пузырьковая сортировка в двусвязном списке

Был в этом в течение нескольких часов, пытаясь заставить реализацию пузырьковой сортировки работать в двойном связанном списке. Мой код, похоже, работает за один проход, но затем завершается преждевременно, не завершая сортировку. Мы будем очень признательны за любые рекомендации.

public void bubbleSort()
{
    Node cur = head.getNext();
    boolean done = false;

    while (!done)
    {
        done = true;
        while(cur != tail)
        {
            if (cur.getNext().getCount()>cur.getCount())
            {
                swap(cur.getNext(),cur);
                done=false;
            }
            cur = cur.getNext();
        }
    }
}

Используемый мной метод подкачки, по-видимому, искажает размещение узлов до тех пор, пока между двумя узлами не образуется круговая петля.

private void swap(Node n1, Node n2)
{
    Node b1, b2, a1, a2;
    System.out.println("Swapping n1: " + n1 + " with n2: " + n2);
    b1 = n2.getPrev();
    if (b1 == n1) // handle adjacent nodes
        b1 = n2;
    a1 = n2.getNext();

    b2 = n1.getPrev();
    if (b2 == n2) // handle adjacent nodes
        b2 = n1;
    a2 = n1.getNext();

    // swap

    n1.setPrev(b1);
    n1.setNext(a1);

    n2.setPrev(b2);
    n2.setNext(a2);

    b1.setNext(n1);
    a1.setPrev(n1);

    b2.setNext(n2);
    a2.setPrev(n2);
}

Спасибо

java linked-list bubble-sort
24.02.2013

  • почему бы не написать компаратор javarevisited.blogspot.com/2011 /06/ 24.02.2013
  • В связанном списке замена элемента его непосредственным преемником является особым случаем. Был ли этот случай проверен? Вам нужно вернуться к началу списка для каждой итерации внешнего цикла. 24.02.2013
  • Запустите код шаг за шагом для простого списка и наблюдайте за его поведением. 24.02.2013

Ответы:


1

Проблемы, которые я вижу в вашем коде:

  • Вы должны начать с head, а не с head.getNext().
  • Вы должны перезапустить Node cur на каждой while(!done) итерации.

С этими изменениями ваш код должен быть

public void bubbleSort() {
    boolean done = false;
    while (!done) {
        Node cur = head;
        done = true;
        while(cur != tail) {
            if (cur.getNext().getCount()>cur.getCount()) {
                swap(cur.getNext(),cur);
                done=false;
            }
            cur = cur.getNext();
        }
    }
}

Этот код предполагает, что ваш метод swap работает без проблем. Протестировано с использованием int count в качестве данных в вашем классе Node, назначающем 10000 значений int в списке.

РЕДАКТИРОВАТЬ: На основе редактирования вашего вопроса я сделал свой класс Node и функцию swap следующим образом:

private static class Node {
    int count;
    Node next;
    //getters and setters...
}

//this function just swaps data, no need to swap the nodes prev and next
//(note that yours is an algorithm design issue)
private void swap(Node node1, Node node2) {
    int aux = node1.getCount();
    node1.setCount(node2.getCount());
    node2.setCount(aux);
}

Нет необходимости делать весь шаблонный код, который вы сделали в своей реализации swap.

24.02.2013
  • Затем я получаю ошибку нулевого указателя, поскольку голова и хвост являются дозорными маркерами. Я почти уверен, что это метод обмена. 24.02.2013
  • @efnx Думаю, у вас проблема с реализацией LinkedList =\. Я сделал быстрый тест и работал как шарм. 24.02.2013
  • @efnx, основываясь на вашем вопросе, почему у вас есть весь этот шаблонный код? Вам нужно всего лишь поменять местами данные в узлах! 24.02.2013

    • 2

    Добавление cur = head.getNext(); в начале внешнего цикла отлично работает для моей реализации связанного списка. Итак, проблема связана с методом swap или реализацией вашего списка.

    Согласно вашему методу bubbleSort, метод swap меняет местами только данные узлов, а не сами узлы. Я имею в виду, что он просто меняет значение count. Если это не так, проблема заключается в методе swap. В противном случае у вашей реализации двусвязного списка будут проблемы.

    24.02.2013
  • Спасибо за вашу помощь. Это определенно метод обмена. Теперь мне просто нужно выяснить, что не так. Для простого списка n ‹ 100 он работает нормально, но для списка n = 1000, который я тестирую, у меня возникла ошибка. 24.02.2013

    • 3

    Вам обязательно нужно оставить cur = head.getNext(); в конце внешнего цикла while, иначе при втором проходе внутренний цикл while будет полностью пропущен, и выполнено будет true.

    Учитывали ли вы время выполнения вашей пузырьковой сортировки? Я заметил в вашем ответе MD.Unicorn, что он отлично работал для списка ‹100, но не для списка из 1000. Ожидаемое время выполнения списка из 1000 как минимум в 100 раз медленнее, чем список, который меньше 100. Вы не можете дать ему достаточно времени, чтобы закончить.

    Сколько времени потребуется, чтобы отсортировать список из 100?

    24.02.2013
  • На моем компьютере требуется от 4390 мс до 5038 мс для 100 элементов, от 12740 мс до 13608 мс для 1000 элементов. 24.02.2013
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..