0

Я новичок в программировании. Списки. Вопрос сортировки. Как сортировать его пузырьком, если нужен предыдущий элемент?

1 ответ 1

1

Откуда такие извращения берутся ?

Если брать примитивные сортировки, то линейный односвязный список естественно сортировать вставками.

Исключаете элементы из исходного и вставляете их в новый (строящийся, отсортированый). Потом возвращаете новый список или меняете указатель в голове списка (зависит от используемой Вами структуры списков).

4
  • В дополнение к предудущему посту, могу сказать, что для сортировки пузырьком (если захочется поизвращаться) нужен как минимум двусвязный список. Но, действительно, правильным будет метод вставок. +1 20 мар 2012 в 23:54
  • 1
    @nikita_sergeevich, если пузырьковая сортировка, это перестановка неупорядоченной пары (честно,не помню точно, что такое "пузырек"), то для односвязного тоже реализуется. Просто сравниваете p->data с p->next->data и обмениваете указатели (естественно для первого элемента списка особый случай), ну и делаете p = p->next (переход к следующему в списке во внутреннем цикле сортировки), только если обмена не было. Дело в коэффициенте при O(n^2).
    – avp
    21 мар 2012 в 7:54
  • чтобы поменять значения местами, как я понимаю для "первого" поля нужно иметь указатель на "второй" чтобы сравнить и обменять, а "второй" должен иметь указатель на предыдущий "первый", чтобы заменить. А это уже двусвязный. Хотя, могу ошибаться. 21 мар 2012 в 23:45
  • 1
    Не совсем так. В структуре, описывающей элемент списка достаточно указателя на следующий. Просто для p->data, p->data->next забыл написать о еще одном важном указателе (назовем pp). Это указатель на предыдущий элемент в списке (p на текущий). В начале просмотра, устанавливаете его в NULL. Перед p=p->next пишите pp = p. При обмене ими надо аккуратно манипулировать, особенно в начале и конце списка. Кстати, та же идея используется для удаления элемента из односвязного списка.
    – avp
    22 мар 2012 в 8:53

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.