Здравствуйте, Аноним, Вы писали:
А>Существует ли сабж? Или доказано что он невозможен?
С теоретической точки зрения, стабильная сортировка эквивалентна "нестабильной".
Т.е. достаточно добавить порядковый номер элемента в структуру, массив из которой сортируется и добавить условие в предикат.
Этот аккаунт покинут.
Re[2]: Стабильная сортировка за NlogN без линейной доп. памя
Здравствуйте, Head Ache, Вы писали:
А>>Существует ли сабж? Или доказано что он невозможен?
HA>С теоретической точки зрения, стабильная сортировка эквивалентна "нестабильной". HA>Т.е. достаточно добавить порядковый номер элемента в структуру, массив из которой сортируется и добавить условие в предикат.
Если для порядкового номера нет места, то требуется создать вспомогательный массив с размером равным исходному. Вот и получаем линейную дополнительную память.
Вопрос же автора был в том, есть ли обход этого условия.
The God is real, unless declared integer.
Re: Стабильная сортировка за NlogN без линейной доп. памяти?
Здравствуйте, SergH, Вы писали:
SH>Здравствуйте, Аноним, Вы писали:
А>>Существует ли сабж? Или доказано что он невозможен?
SH>Heap-sort (она же пирамидальная, она же иерархическая) точно не подходит? SH>Я не очень уверен, что она stable, но, кажется, ничего не мешает.
Она не stable.
Re: Стабильная сортировка за NlogN без линейной доп. памяти?
