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

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

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

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

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