Какой алгоритм сортировки односвязного списка?

Question

[rostyslavvvv]

Какой должен быть алгоритм сортировку односвязного списка, вкратце), спасибо

Answer 1

[Wataru]

Для списка отлично подойдет merge sort. В отличии от массива - для списков не понадобится второй массив для хранения временных результатов (вообще говоря, можно и массив без него сортировать, но получается медленнее и слишком сложный алгоритм).

Answer 2

[Армянское Радио]

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

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

Сложность этой сортировки в O-нотации равна N^2.

Comments

[Lynn «Кофеман»]

Хм, а я б наверное пузырьком сортировал. Всё равно вопрос академический :)

[Армянское Радио]

Lynn «Кофеман», отлаживать сортировку выбором проще - отладили поиск максимума (отдельно) потом остается только отладить обмен элементов и движение по списку.