прорыв в алгоритмах сортировки
От: koenig  
Дата: 07.11.18 22:08
Оценка: 6 (2) +4 -4 :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))) :))
Re: прорыв в алгоритмах сортировки
От: C0s Россия  
Дата: 08.11.18 18:10
Оценка: 3 (1) +2 :))) :))
Здравствуйте, koenig,


коллега предложил более экономный вариант — PolPotSort с мощностью O(1). На выходе — сразу пустой список.
Re: прорыв в алгоритмах сортировки
От: bzig  
Дата: 08.11.18 19:16
Оценка: 2 (2) :))
Задача на собеседовании: KgbSort — найти и удалить наименьший список "лишних" элементов, после которого список становится сортированным.
Re: прорыв в алгоритмах сортировки
От: 3V Россия  
Дата: 08.11.18 17:48
Оценка: :))) :)
Здравствуйте, koenig, Вы писали:

K>Image: x9triplll1v11.jpg


Тоже придумал сортировку.
Назвал ее LGBTranSort.
Итерируешь по элементам.
Если элемент is out of order, то он просто меняет гендерную идентичность
значение на подходящее (ну чтобы можно было нормально пристроиться к предыдущему
элементу).
Re: прорыв в алгоритмах сортировки
От: vdimas Россия  
Дата: 08.11.18 16:59
Оценка: +1
Здравствуйте, koenig, Вы писали:

K>Image: x9triplll1v11.jpg


Внешние сортировки так и работают. ))
Только на следующем шаге слияние и заход на новый круг.
Re: прорыв в алгоритмах сортировки
От: ylp  
Дата: 08.11.18 17:15
Оценка: -1
Здравствуйте, koenig, Вы писали:

Настоящий прорыв в алгоритмах сортировки сделал
Автор: ylp
Дата: 07.11.18
в соседней ветке CoderMonkey
Автор: CoderMonkey
Дата: 08.11.18
. Только вот незадача — код
Автор: CoderMonkey
Дата: 08.11.18
он никому не хочет показывать
Re[3]: прорыв в алгоритмах сортировки
От: C0s Россия  
Дата: 09.11.18 14:50
Оценка: +1
Здравствуйте, Vi2, Вы писали:

C0s>>коллега предложил более экономный вариант — PolPotSort с мощностью O(1). На выходе — сразу пустой список.


Vi2>Более корректно, выдавать список, состоящий из первого(последнего) элемента: вот он уж точно отсортированный.


но тогда приходится проверять на непустоту — уже лишнее усложнение
Re: прорыв в алгоритмах сортировки
От: alexzzzz  
Дата: 09.11.18 14:11
Оценка:
PentagonSort — обнулять случайные участки списка, пока он не отсортируется.
Re[2]: прорыв в алгоритмах сортировки
От: Vi2 Удмуртия http://www.adem.ru
Дата: 09.11.18 14:38
Оценка:
Здравствуйте, C0s, Вы писали:

C0s>коллега предложил более экономный вариант — PolPotSort с мощностью O(1). На выходе — сразу пустой список.


Более корректно, выдавать список, состоящий из первого(последнего) элемента: вот он уж точно отсортированный.
Vita
Выше головы не прыгнешь, ниже земли не упадешь, дальше границы не убежишь! © КВН НГУ
Re[2]: прорыв в алгоритмах сортировки
От: B0FEE664  
Дата: 12.11.18 13:42
Оценка:
Здравствуйте, bzig, Вы писали:

B>Задача на собеседовании: KgbSort — найти и удалить наименьший список "лишних" элементов, после которого список становится сортированным.


Ну и задачка...
O(2n) времени + O(n) памяти или можно быстрее?
И каждый день — без права на ошибку...
Re[3]: прорыв в алгоритмах сортировки
От: bzig  
Дата: 12.11.18 14:41
Оценка:
BFE>O(2n) времени + O(n) памяти

Ну так NP полная же

BFE>или можно быстрее?


Троллите, товарищ?
Re[3]: прорыв в алгоритмах сортировки
От: Chorkov Россия  
Дата: 13.11.18 07:27
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE>O(2n) времени + O(n) памяти или можно быстрее?

Можно O(n2) времени + O(n) памяти. (Динамическое программирование.)
Re[2]: прорыв в алгоритмах сортировки
От: Ops Россия  
Дата: 13.11.18 08:06
Оценка:
Здравствуйте, alexzzzz, Вы писали:

A>PentagonSort — обнулять случайные участки списка, пока он не отсортируется.


Не, там от больших элементов отпиливают "лишнее", чтобы и список был сортированный, и это лишнее пристроить.
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Re[4]: прорыв в алгоритмах сортировки
От: Hobbes Россия  
Дата: 13.11.18 08:08
Оценка:
Здравствуйте, Chorkov, Вы писали:

C>Можно O(n2) времени + O(n) памяти. (Динамическое программирование.)


Ага. Тоже сразу подумал, а не применить ли тут динпрог.
Re[4]: прорыв в алгоритмах сортировки
От: Hobbes Россия  
Дата: 13.11.18 08:08
Оценка:
Здравствуйте, bzig, Вы писали:

B>Ну так NP полная же


Инфа сколько процентов?
Re[4]: прорыв в алгоритмах сортировки
От: B0FEE664  
Дата: 13.11.18 08:38
Оценка:
Здравствуйте, Chorkov, Вы писали:

BFE>>O(2n) времени + O(n) памяти или можно быстрее?

C>Можно O(n2) времени + O(n) памяти. (Динамическое программирование.)
Алгоритм?
И каждый день — без права на ошибку...
Re[5]: прорыв в алгоритмах сортировки
От: Chorkov Россия  
Дата: 13.11.18 09:27
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, Chorkov, Вы писали:


BFE>>>O(2n) времени + O(n) памяти или можно быстрее?

C>>Можно O(n2) времени + O(n) памяти. (Динамическое программирование.)
BFE>Алгоритм?

Поздно писать, watchmaker уже привел ссылку
Автор: watchmaker
Дата: 13.11.18
на O(n*log(n)) алгоритм .
Re[6]: прорыв в алгоритмах сортировки
От: B0FEE664  
Дата: 13.11.18 10:59
Оценка:
Здравствуйте, Chorkov, Вы писали:

C>Поздно писать, watchmaker уже привел ссылку
Автор: watchmaker
Дата: 13.11.18
на O(n*log(n)) алгоритм .


Что ж, отличный вопрос для собеседования. Не сомневаюсь, что Тёмчик
Автор: Тёмчик
Дата: 01.11.18
минут за 5 решит.
И каждый день — без права на ошибку...
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.