Реализация алгоритмов сортировки и / или поиска - где и почему

Question

Время от времени я сталкиваюсь с алгоритмами сортировки и / или поиска, реализованными вручную, вместо использования алгоритмов, реализованных на языке. Большая часть исходного кода, который я изучал, написана на Java, C # или PHP - но я предполагаю, что это явление не зависит от языка.

Относительно обычных структур данных, таких как списки; Почему и где вы реализуете свой алгоритм? Идеологические причины? Больше памяти эффективно? Не можете выдержать идею использования встроенных функций? Java предпочтительно использует mergesort (в Collections.sort ()), который имеет некоторые издержки, когда вы сравниваете его с быстрой сортировкой в ​​качестве примера. Если у вас есть избранное, которое вы регулярно используете для выполнения общих задач, вы можете отправить его на выбранном вами языке!

Answer 1

• Не каждый алгоритм сортировки реализован стандартной библиотекой.
• Не каждый язык поддерживает универсальные типы данных / контейнеры
• Иногда вам нужно переключаться между алгоритмами сортировки в зависимости от размера данных
• Настройка алгоритма для определенного набора ввода проще
• Для измерения скорости процессора
• Курсовая
• Просто для удовольствия

Это лишь некоторые из причин ...

Answer 2

Bogosort

while (!is_sorted(array)) {
    randomly_shuffle(array);
}

Ожидаемое время работы: O (n!)

:)

Answer 3

В C ++ вы можете иметь контейнер с массивом внутри, который ищется только методами контейнера. Вы можете использовать некоторую реализацию библиотеки, но тогда вам нужно будет предоставить класс компаратора, и это будет столько же кода, сколько просто написания цикла for (). Зачем создавать новый объект (класс компаратора) для такого случая?

Answer 4

Встроенные языковые реализации обычно будут быстрее, но только если вы сортируете / ищите стандартным способом. Как только вы сделаете что-то немного необычное, будь то способ интерпретации ключа, работа с несколькими указателями, подключение к другой среде и т. Д., Вы можете повысить производительность, настроив основные процедуры в соответствии с вашими точными требованиями.

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