Основы сортировки

Основы сортировки

Алгоритмы сортировки можно разделить на два типа: устойчивые и неустойчивые. К устойчивой сортировке относятся те алгоритмы, которые при наличии в наборе данных нескольких равных элементов в отсортированном наборе оставляют их в том же порядке, в котором эти элементы были в исходном наборе. Например, предположим, что в наборе имеется три элемента и значение каждого элемента равно 42 (т.е. элементы равны). Пусть в исходном наборе элемент А находится в позиции 12, элемент В - в позиции 234, а С - в позиции 3456. После выполнения устойчивой сортировки они будут находиться в последовательности А, В, С, т.е. их взаимный порядок не изменится. С другой стороны, неустойчивая сортировка не гарантирует, что элементы с равными значениями будут находиться в определенной последовательности. Для нашего примера элементы А, В и С могут оказаться в последовательности А, В, С, или С, В, А, или любой другой.

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

Каждый из алгоритмов сортировки с целью упрощения понимания будет описан на примере сортировки колоды карт. Выберите все черви из колоды и перетасуйте их (манипулирование только 13 картами позволит упростить вашу работу).

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

6.2. Функции сортировки и поиска

Из книги автора

6.2. Функции сортировки и поиска Сортировка и поиск являются двумя фундаментальными операциями, потребность в которых постоянно возникает во многих приложениях Библиотека С предоставляет ряд стандартных интерфейсов для осуществления этих задач.Все процедуры разделяют


Самые быстрые алгоритмы сортировки

Из книги автора

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


12.5.2. Алгоритмы сортировки и упорядочения

Из книги автора

12.5.2. Алгоритмы сортировки и упорядочения Четырнадцать алгоритмов сортировки и упорядочения предлагают различные способы упорядочения элементов контейнера. Разбиение (partition) – это разделение элементов контейнера на две группы: удовлетворяющие и не удовлетворяющие


Обсуждение сортировки

Из книги автора

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


Временное пространство сортировки

Из книги автора

Временное пространство сортировки Запросы с предложениями ORDRE BY и GROUP BY "паркуют" промежуточные наборы для дальнейших операций сортировки во временном хранилище. Рекомендуется иметь доступную память, приблизительно в 2.5 раза превышающую размер самой большой таблицы,


Направление сортировки

Из книги автора

Направление сортировки По умолчанию сортировка выполняется в возрастающем порядке. Для выполнения сортировки в убывающем порядке добавьте ключевое слово DESC, как показано в примере 23.8. Если вам нужна убывающая сортировка, создайте для нее убывающий индекс. Firebird не может


Два вида сортировки

Из книги автора

Два вида сортировки Алгоритмы qSort() и qStableSort()могут быть использованы при сортировке элементов QList<T>, QVector<T> или в любом динамическом C++ массиве. С Qt 4, также возможно определить любой оператор сравнения (вместо operator<()). Stable сортировка имеет свойство сохранения порядка


11.1.2. Сохранение результатов сортировки

Из книги автора

11.1.2. Сохранение результатов сортировки Чтобы сохранить результаты сортировки, укажите опцию -o и выходной файл. Можно также воспользоваться традиционным методом переадресации с помощью оператора >. В следующем примере результаты сортировки сохраняются в файле results.out$


11.1.5. Проверка факта сортировки файла

Из книги автора

11.1.5. Проверка факта сортировки файла Каким образом можно узнать, отсортирован ли данный файл? Если он содержит, например, около 30 строк, то достаточно его просмотреть. А если в нем 400 строк? Примените команду sort -c, которая сама определит, отсортирован ли файл:$ sort -с video.txtsort:


11.1.12. Несколько ключей сортировки

Из книги автора

11.1.12. Несколько ключей сортировки При использовании опций +позиция и -k следует быть особенно аккуратным. Если вы внимательно прочитали их описание в табл. 11.1, то должны были отметить такой факт: когда не указана конечная позиция, ключ сортировки считается заканчивающимся