Сложность алгоритма сортировки

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

Не имеет смысла. Предположим это будет иметь в среднем профит над тупым find_max(). Ну давай по какнонам - взять и вставить это типа n, потом каждый раз тебе надо пройтись 1 ... n раз по твоему списку, чтобы найти место. В худжем такое же днище, как и find_max(). Но т.к. он у тебя уже отсортирован, то тебе надо в среднем пройти половину в «лучшем среднем случаее» - т.е. каждый раз проходить 1 ... n/2. С таким же успехом можно пологать, что максимальный елемент будет в первой половине списка и будет тоже самое.

Реально же твоя поделка имеет мистический(возможно реальный) профит над find_max(), но профит над днищем ~= днище.

Понятно, что в лучшем (когда можна сразу либо в голову, либо в хвост) - O(n), в худшем - O(n^2). А в среднем щас подумаю.

Причем, правильно я понял, что худший случай у тебя такой список: 0 5 1 2 3 4. Too bad

днище

Привет, супирьхакирькодер.

А в среднем щас подумаю.

Не, не буду думать. С наскоку не скажешь, но не удивительно, если рост тоже как у квадрата

Если не считать того, что элемент может вставляться в хвост, то это обычная сортировка вставками.

Средняя сложность такая же (n²), однако отсортированный в обратном порядке список сортируется за n, а не n².

И для списков inplace merge sort как раз очень хорошо подходит. Тут вот маленький пример имплементации.

сложность получится O(N^2). Так как каждый раз будешь искать заново куда вставить. А если искать место вставки бисекцией, то будет O(NlogN)

Бисекция на связном списке... Вроде тот же O(n^2) получается, не? За счет последовательного перебора всех элементов. Не прав?

да, все верно. Квадрат в худшем случае.

n*log(n) максимум без выделения доп памяти

с доп памятью radix sort

У нас новый игрок! Кто даст меньше?

Бисекция на связном списке... Вроде тот же O(n^2) получается, не? За счет последовательного перебора всех элементов. Не прав?

Не прав. чтобы вставить элемент на нужное место надо будет сделать log2(N) сравнений.

в связном списке?

в связном списке?

в отсортированном списке с доступом по индексу.

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

брр...тогда это уже массив, не? И доступ по индексу в связном списке - это

ну массив, да.

перебор всех элементов до нужного, или пока я тут в криокамере спал, какой-то новый способ изобрели?

ну никто ж не заставляет чистый связанный список использовать.

Если у нас список на массивах - то каждая вставка в элементов в середину или голову вызывает копирование всех элементов вызывает копирование всех элементов от места вставки и до конца. Это еще веселее.

Если у нас список на массивах - то каждая вставка в элементов в середину или голову вызывает копирование всех элементов вызывает копирование всех элементов от места вставки и до конца. Это еще веселее.

а если заранее зарезервировать место, то все будет ок. кроме этого - можно держать таблицу ссылок.

дикли, ты сейчас дерево сбалансированное изобретешь :-P

O(n^2)

кроме этого - можно держать таблицу ссылок

На ЛОРе можно держать таблицу facepalm'ов