Выбор сортировки

Question

Моя книга гласит:

Предположим, у вас есть группа из N чисел, и вы хотите определить k-е по величине. Это известно как проблема выбора. Большинству студентов, у которых был один или два курса по программированию, не составит труда написать программу для решения этой проблемы. Есть немало «очевидных» решений. Одним из способов решения этой проблемы было бы чтение N чисел в массив, сортировка массива в порядке убывания.

Это говорит о том, что имеет смысл сортировать массив в порядке убывания. Как это имеет смысл? Если у меня есть массив {1,9,3,7,4,6} и я хочу получить самый большой элемент, я бы отсортировал его в порядке возрастания, чтобы {1,3,4,6,7,9}, а затем возвратил последний элемент. Почему в книге сказано в порядке убывания?

Answer 1

Сам порядок не так важен, но если вы хотите k -й наибольший элемент, то если вы сортируете в порядке убывания, он расположен в k -й элемент (или k-1 , если мы начнем с индекса 0), тогда как если мы сортируем в порядке возрастания, он расположен в индексе n-k + 1 (или nk , если индекс начинается с 0).

Для ленивых алгоритмов сортировки (как в Haskell и C # Linq .OrderBy), это может иметь последствия в отношении сложности времени. Если мы реализуем ленивый алгоритм сортировки выбора (например, генератор), то он будет работать в O (k & times; n) вместо O (n ^{2 *) 1026 *)} . Если мы используем, например, вариант lazy QuickSort, потребуется O (n + k log n) для получения первых k элементов.

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

Answer 2

Поскольку вам может не потребоваться самый большой элемент, в книге написано

хотел бы определить k-ую наибольшую

Если вы сортируете его в порядке возрастания, как вы узнаете, что такое, скажем, третье по величине число, не выяснив сначала, насколько велик массив?

Это было бы проще, если бы массив был убывающим, поскольку 3-й по величине будет просто 3-м элементом.