Когда бы вы внедрили собственный алгоритм сортировки?

Question

Простите, если это глупый вопрос .... но я вспоминаю свою Комп.Sci.классы, и я отчетливо помню, как меня изучали / опрашивали по нескольким алгоритмам сортировки и соответствующей нотации «Big O».

За пределами классной комнаты я никогда не писал код для сортировки.

Когда я получаю результаты из базы данных, я использую 'Order By'.В противном случае я использую класс коллекции, который реализует сортировку.У меня есть реализовано IComparable , чтобы разрешить сортировку;но я никогда не выходил за рамки этого.

Была ли сортировка всегда лишь академическим занятием для тех из нас, кто не использует языки / структуры?Или это просто из-за того, что современные языки, работающие на современном оборудовании, беспокоят подробности?

Наконец, когда я вызываю, например, сортировку по списку (строки), какой алгоритм сортировки используетсяпод капотом?

Answer 1

Хотя вам редко может понадобиться реализовать алгоритм сортировки, вы сами понимаете различные алгоритмы, и их сложность может помочь вам в решении более сложных задач.

Наконец, когда я, например, вызываю .Sort on List (Of String), какой алгоритм сортировки используется под капотом?

Быстрая сортировка

Answer 2

Я никогда не реализовывал свой собственный алгоритм сортировки с тех пор, как брал уроки CS в колледже, и если бы я даже думал о написании своего собственного, я бы хотел, чтобы мою голову сначала осмотрели.

List<T>использует Quicksort в соответствии с документацией MSDN:

http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Answer 3

Для программиста важно знать, как работают эти алгоритмы. Одна из причин заключается в том, что в определенных условиях определенные алгоритмы лучше, хотя сортировка редко является узким местом.

В некоторых средах функция .Sort использует различные методы в зависимости от ситуации.

Answer 4

Вы, вероятно, не реализуете свой собственный алгоритм сортировки, если используете языки высокого уровня ...

То, что вы узнали в классе, было просто там, чтобы научить вас существованию и важности большого О(omicron) нотация.

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

Это учитЕсли вы выполняете циклы внутри циклов и рекурсий, это может привести к большим проблемам с производительностью, если их не анализировать / оптимизировать задолго до начала кодирования.

Это руководство для проверки вашего проекта до того, как вы сможете приблизиться к скорости выполнения.

Answer 5

Разве сортировка всегда была академическим занятием для тех из нас, кто не применяет языки / структуры? Или это просто из-за того, что современные языки, работающие на современном аппаратном обеспечении, вызывают беспокойство?

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

Answer 6

Реализация собственного вида - это то, что вы делаете, чтобы понять, как работают алгоритмы, каковы компромиссы, какие проверенные подходы, которые эффективно решают широкий спектр проблем, известны и т. Д.

Как отмечается в ответе Дарина Димитрова, подпрограммы сортировки библиотеки должны иметь очень конкурентоспособную среднюю производительность, поэтому обычно выбирается быстрая сортировка.

Answer 7

Мне иногда приходилось писать собственные методы сортировки, но только когда я писал для относительно незрелой и недостаточно мощной платформы (например, .Net 1.1 в Windows CE или встроенной java или что-то подобное).

На всем, что напоминает современный компьютер, лучшим алгоритмом сортировки является предложение ORDER BY в T-SQL.

Answer 8

ИМО, это стало чем-то вроде академического упражнения.Вы должны понимать алгоритмическую сложность, и сортировка является хорошим примером для проработки, потому что вы можете легко увидеть результаты и вычислить различные сложности.В реальной жизни, тем не менее, почти наверняка есть вызов библиотеки, который сортирует ваш диапазон быстрее, чем вы могли бы сделать, если бы попытались свернуть свой собственный.

Я не знаю, для чего используются библиотеки .Netих реализация по умолчанию, но я предполагаю, что это Quicksort или Shellsort.Мне было бы интересно узнать, если это что-то еще.

Answer 9

1. Современные языки, работающие на современном оборудовании, заставляют беспокоиться о мелочах, если профилировщик не показывает, что сортировка является узким местом вашего кода.
2. Согласно this , List.Sort использует Array.Sort, который использует QuickSort.

Answer 10

Я думаю, что бывают случаи, когда вам нужен собственный метод сортировки.Что делать, если вы хотите отсортировать по марке автомобилей, но не по алфавиту?Например, у вас есть база данных с марками: Honda, Lexus, Toyota, Acura, Nissan, Infiniti

Если вы используете обычную сортировку, вы получите заказ: Acura, Ford, Honda, Hyundai, Lexus,Toyota

Что делать, если вы хотите отсортировать их по стандарту и классу класса автомобиля вместе?Лексус, Тойота, Хонда, Акура, Ниссан, Инфинити.

Я думаю, вам понадобится специальный метод сортировки, если это так.