Я программирую функцию для TI-Nspire, поэтому я не могу использовать встроенные функции внутри функции. Каков наиболее общий алгоритм сортировки списка чисел без изменения самого списка? (рекурсия и расщепление списков - это справедливая игра, как и общее использование математики.)Эффективная функциональная сортировка
Mergesort прост, прост, эффективен и стабилен: разбиваем список, сортируем рекурсивно и объединяем результаты.
Чтобы быть более конкретным, mergesort принимает O (N log N), что является асимптотически оптимальным. Кроме того, на практике (с использованием обоих алгоритмов, модифицированных для сортировки коротких подсписок со специальным типом), mergesort может быть близким конкурентом модифицированной быстрой сортировки, используемой в стандартных библиотеках C/C++.
Редактировать: в отличие от видов на месте, таких как сортировка quicksort и insertion, mergesort требует вспомогательной памяти и проще всего реализовать, копируя, а не заменяя.
Если бы вы могли изменить список, я бы предложил quicksort, потому что он в среднем использует меньше памяти, но mergesort - определенно способ пойти в этом случае. –
@ Justin Peel: обратите внимание также, что наивная реализация быстрого сортировки будет легко замедляться, чем сортировка слияния для больших данных. AFAIK, эффективная быстрая сортировка означает быструю сортировку + выборщик поворота + (возможно) откат к сортировке кучи (см. Вступление сортировки). В противном случае, по моему опыту, чистая быстрая сортировка не работает хорошо по сравнению с сортировкой слияния. – Giorgio
Timsort используется в python и java SE 7. Он берет лучшее из сортировки и вставки сортировки. Сортировка вставки - O (n^2), но с небольшими списками чисел она быстрее, чем сортировка слияния!
Таким образом, вы можете использовать это в качестве алгоритма общего сортировочной, как указано here
не хотелось читать все, но учитывая, что вы сказали, что он берет лучшее из слияния и сортировки вставки, а сортировки вставки изменяют значение inplace, требует ли timsort любая модификация на месте? – muhmuhten
Timsort замечательный, но я думаю, что это намного сложнее, чем нужно для получения хорошего вида на калькуляторе. –
Я полагаю, вы пытались дозвониться 'SortA' в списке, но калькулятор не позволит вам сделать это, потому что это в функции? Вздох. Эта проблема существует и для TI-68k. –
точно проблема. 83-серия не имеет этой проблемы, но также не имеет встроенного аргумента передачи. – muhmuhten
Если это помогает, я заметил эти функции сортировки на ticalc.org: http://www.ticalc.org/archives/files/fileinfo/429/42964.html –