💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Простейшие методы сортировки: метод обмена.

Данный метод относится к классу простейших, занимая в нем последнее место по производительности. Тем не менее, он очень широко известен, видимо, благодаря своему одному легко запоминающемуся названию – метод всплывающего пузырька. Работа алгоритма действительно похожа на всплывание наверх пузырьков воздуха: сначала на самый верх всплывает самый легкий элемент, потом за ним – чуть более тяжелый и т.д.

Пусть имеется n элементов а₁ а₂, а₃,..., а_n, расположенных в ячейках массива. Для простоты будем считать, что сам элемент совпадает с его ключом. Алгоритм состоит из повторении n-1 шага, на каждом из которых в оставшемся необработанном наборе за счет попарного сравнения соседних элементов отыскивается минимальный элемент.

Шаг 1. Сравниваем а_n с а_n-1 и если а_n < а_n-1 то меняем их местами, потом сравниваем а_n-1 с а_n-2 и, возможно, переставляем их, сравниваем а_n-2 и а_n-3 и т.д. до сравнения и, возможно, перестановки а₂ и а₁. В результате на первом месте в массиве оказывается самый минимальный элемент, который в дальнейшей сортировке не участвует

Шаг 2. Аналогично сравниваем а_n с а_n-1, а_n-1 с а_n-2 и т.д., а₃ с а₂, в результате чего на месте а₂ оказывается второй наименьший элемент, который вместе с а₁ образует начальную часть упорядоченного массива

Шаг 3. Аналогичными сравнениями и перестановками среди элементов а₃, а₄, …, а_n находится наименьший, который занимает место а₃

.....

Шаг n-1. К этому моменту первые n-2 элемента в массиве уже упорядочены и остается “навести порядок” только между двумя последними элементами а_n-1 и а_n. На этом сортировка заканчивается.

Пример. Дано 6 элементов – целые числа 15, 33, 42, 07, 12, 19.

Таблица 1.

Метод обмена.

Итого, для шести элементов сделано 5+4+3+2+1=15 сравнений и 8 перестановок.

В общем случае, на каждом из n-1 шагов выполняется в среднем n/2 сравнений, поэтому оценка для числа сравнений выражается соотношением n(n-1)/2, т.е. данный метод относится к классу O(n²). Аналогично, число перестановок тоже пропорционально n². Несмотря на то, что было предложено несколько улучшений данного метода, он остается самым неэффективным. Уже для 1000 элементов число сравнений выражается внушительной величиной порядка 500 тысяч.