Алгоритмы сортирвок

АЛГОРИТМЫ СОРТИРОВКИ

СОРТИРОВКА-ОБЩАЯ КЛАССИФИКАЦИЯ

1) Оценка алгоритма :

-время;

-память;

-устойчивость (устойчивая сортировка не меняет взаимного расположения равных элементов);

-естественность поведения (эффективность при обработке уже отсортированных или частично отсортированных данных);

-сфера приминения (внутренние и внешние);

Прямые методы:(не самые быстрые, но удобные для объяснения)

1) Сортировка с помощью включения(вставки)

*Используется при игре в карты*

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

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

Таким образом в процессе вставки элемент "просеивается" к началу массива, останавливаясь в случае, когда: 1.найден элемент меньший x; 2.достигнуто начало последовательности.

Алгоритм устойчивый и есстественный.

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

// отсортировать массив

for (i=1;i < size; i++) {

 x = a[i];

for (j=i-1; a[j] > x; j--)

a[j+1] = a[j];

a[j+1]=x;

}

// вставить backup(барьер) на правильное место

for (j=1;j<size && a[j]<backup;j++)

a[j-1]=a[j];

a[j-1]=backup;

(0xffffffff-минимально возможное число)

2) Сортировка с помощью выделения(прямого выбора):

1. Выбирается минимальный элемент;

2. Он меняется местами с первым элементом;

3. Процесс повторяется с оставшимися н-1 элементами, н-2 элементами и т.д., до тех пор пока не останется один самый большой элемент;

3) Сортировка с помощью обмена (пузырьковая сортировка):

Идея: один шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в "неправильном" порядке, то меняем их местами. После нулевого прохода "вверху" оказывается самый "легкий" элемент. Следующий проход деоается до второго сверху элемента, следовательно второй по величине поднимается на правильную позицию. Делая проходы по все-уменьшающейся нижней части доберемся до последнего элемента. Конец сортировки.