Связные списки. Пузырьковая сортировка. Неэффективный, но наиболее простой способ: смена звеньев местами

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

  • 1. Переставлять внутренние элементы одного звена с внутренними элементами второго звена напрямую. Способ наиболее простой, но очень долгая работа программы.
  • 2. Изменять связи в указателях. Более правильный способ, программа будет работать значительно быстрее, чем если использовать первый способ. И реализовать такой, и понять такой намного сложнее, чем первый.
Здесь будет показан способ наиболее простой к пониманию. Т. е. когда элементы копируются, а не меняется связь указателей. Для начала будет показана основа, от которой мы будем отталкиваться. Пусть, например, мы имеем вот такой список:


Как вы можете догадаться, чтобы понимать основную тему этой интернет-страницы, необходимо понимать, что это за код такой в листинге #1. (Посмотреть описание написания подобного кода можно на странице Двусвязный список) В листинге #1 реализован двусвязный список. Сам факт двусвязности обозначает, что при необходимости программу легко или дополнить или переписать так, чтобы, например, обход элементов происходил или слева-направо или справа-налево, т. е. по вкусу. Я выбираю наиболее привычную из чтения форму обхода: слева-направо. Или бежишь от хвоста по указателям на прошлое значение (по Prev), либо от начала по указателям на следующие (по Next).
Кроме этого, если вы вообще не знакомы с сортировками, то скорее всего понять саму эту темы вам не получится. Нужно понимать хотя бы самую простую, пузырьковую, сортировку обычного одномерного массива. Поскольку пузырьковая сортировка наипростейшая в реализации, в темах сайта часто используется именно она. Не исключение и эта тема.
Итак, чтобы сортировать список, можно пойти наиболее простым путём, не обновляя связи в указательных переменных, а прямым копированием звеньев. Каждую внутренность переставляемого звена нужно будет копировать во временное звено, выступающее в качестве буфера хранения. Это примитивный алгоритм перестановки, когда для перестановки двух переменных используется вспомогательная переменная для временного хранения переставляемого элемента. Из-за копирования всего звена и из-за возможно большого количества звеньев такой способ очень неэффективен, но поскольку он наиболее простой, в моём представлении, к пониманию новичками, показываю его. Добавляем функцию сортировки к нашему классу List.

Алгоритм пузырьковой сортировки, который использован здесь, эквивалент вот такому:
Поскольку у нас имеется список, количество элементов которого не отслеживается, то мы не можем столь же удобно использовать цикл for для обхода. Поэтому в пользу читаемости кода используетя цикл while. Единственное, что наиболее важно при использовании цикла while сейчас — это не забывать обновлять значение, очередное обновление которого служит признаком прекращения цикла. Поскольку для определения необходимости завершения цикла мы используем указательные переменные, и во внутреннем цикле указательная переменная бежит только на следующий элемент, при завершении внутреннего цикла эту убегающую указательную переменную нужно откатывать немного назад, для чего сначала нужно перенаправить указатель из внешнего цикла на следующий элемент, а потом направить убежавший указатель на следующий элемент относительно указателя внешнего цикла. В общем, нужно обязатель ловить беглеца и показывать ему его место.
Как уже было дважды отмечено, сам факт копирования объектов обозначает, что программа будет работать достаточно долго. Ведь объекты могут большими и их может быть много. Вместо этого можно обновлять связи. Обновление связей реализовывается сложнее, но зато программа будет работать при таком премного эффективнее.
Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

7 комментариев: Связные списки. Пузырьковая сортировка. Неэффективный, но наиболее простой способ: смена звеньев местами

  • Gev говорит:

    спасибо




    0



    0
  • nomto говорит:

    Спасибо

    а как удалять элементы?




    0



    0
  • Hayk Grigoryan говорит:

    rebyat v std::list ispolzuetsya «Merge sort» a ne «Buble sort (v perevode s angl — puzirkovaya sortirovka) »  tak chto etot primer ochen’ ploxoy ne kogda ne sortiruyte spiski takim obvrazom, eto bezgramotno




    0



    0
  • kovalyovalekc говорит:

    Здравствуй, друг. Нужен твой совет, всего 2,5 маленьких вопроса.

    1) На 25 строке написано просто while(Head), а на 39 и 57 — if (Head!=NULL) и while (temp!=NULL) соответственно. В двух последних случаях мы можем написать также, как и в первом? Если нет, то почему?

    2)Второй вопрос связан с сортировкой: когда алгоритм обнаруживает, что значение одного элемента больше значения другого, то он меняет значения этих указателей:

    if( node->x > node2->x ){
    int i = node->x;
    node->x = node2->x;
    node2->x = i;}

    Будет ли корректным менять последовательность сами указатели?
    if (n1->data > n2->data) {
    Node *i = node;
    node = node2;
    node2 = i;}

    Кстати, обязательная ли 36 строка? Как ты думаешь?




    0



    0
    • admin говорит:

      25-я строка.
      Нет обхода списка, поэтому сразу циклом происходит обход всего списка, чтобы позвенно (по звеньям) удалить элементы списка.

      if поспособствует удалению только одного указателя, а надо удалять столько указателей, сколько в список добавлено было.
      ========================
      39-я строка.
      Это просто проверка на пустоту списка, мало ли добавление не получилось, не создавать же новое звено. Цикл тут не нужен, достаточно проверит ифом.
      =======================
      57 строка
      Это обход цикла. Нужно множество звеньев, поэтому цикл, одним ифом не обойтись.
      =======================
      Head — это начало списка, если написать while(head) — то это то же, что написать while (head == true), так можно повесить программу, если head Не указывает вникуда, то будет бесконечный цикл.
      =======================
      36-я, думаю, обязательна, но могу ошибиться.
      =======================

      Последний вопрос. Можно проверить самому ведь. Это неправильно.




      0



      0

Добавить комментарий

Ваш e-mail не будет опубликован.

9 + 1 =

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/kim-bentli/upravlenie-elektronnymi-ustroystvami-na-c-22988275/?lfrom=15589587
Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

В свои 20 лет он знал более 9 опеpационных систем и ни одной женщины.

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок