Сортировка перемешиванием в С имеет множество различных названий:
пузырьковая сортировка двунаправленного действия;
шейкер-сортировка;
сортировка пульсацией;
сортировка трансфером;
«счастливый час».
Сколько бы ни было названий — результат один.
Сортировка перемешиванием в С
По своей сути сортировка перемешиванием — это модифицированная всем известная пузырьковая сортировка. Основной недостаток традиционной пузырьковой сортировки — это медленное «движение» значений массива к своим отсортированным позициям. В сортировке перемешиванием избавились от этого недостатка. Этого удалось добиться за счет поочередной сортировки массива в разных направлениях. Применяя такой подход, удалось достичь того, что элементы, которые располагаются далеко от отсортированных позиций, быстрее занимают выделенные места.
Почему такую сортировку называют «сортировка перемешиванием» или «шейкер-сортировка»? Потому что в момент ее выполнения массив действительно похож на хорошо перемешанный массив.
Сортировка перемешиванием в С, реализация кодом
Приведем простой пример реализации сортировки перемешиванием:
bool sort_number = true;
do {
sort_ number = true;
for (int i = 0; i < n; i++) { // n — количество элементов массива
if (number[i] > number[i + 1]) {
swap (number[i], number[i + 1]);
sort_ number = false;
}
}
for (int i = 4; i >= 1; i--) {
if (number[i] < number[i - 1]) {
swap (number[i], number[i - 1]);
sort_ number = false;
}
}
} while (sort_ number == false);
Объясняем пример. Мы создали bool-переменную «sort_number» и сразу придали ей значение «true». Мы за 2 цикла проверим, были ли изменены значения в ячейках.
«sort_number» присвоит значение «false», когда результаты после выполнения оператора «if» будут «true».
Смысл заключается в том, что мы прописали в цикле «do while», что «sort_number == false». Это означает, что, пока происходит обмен значений ячеек, сортировка перемешиванием заканчиваться не будет. Когда «sort_number» после цикла не будет равна «false», такой цикл будет считаться завершенным и мы выйдем из него.
Заключение
Сортировка перемешиванием в С не так сложна в реализации, как кажется изначально. Мы привели простейший пример, но при этом есть много других способов, как она реализовывается.
Другое
