Одномерный массив. Пузырьковая сортировка.

Пузырьковая сортировка — это самая простая для человеческого восприятия сортировка, но очень неэффективная с точки зрения быстродействия. Тем не менее, в самом начале своего пути вы просто обязаны познакомиться с пузырьковой сортировкой.
  • Сортировка — это процесс перестановки чего-либо по какому-то признаку. Например, фамилии можно отсортировать по алфавиту, группу чисел по возрастанию или убыванию, учеников какой-то группы по успеваемости.
Под сортировкой массива понимают перестановку элементов массива любым заранее оговорённым образом: или по возрастанию/убыванию, или же с левой стороны массива положительные числа, идущие по возрастанию, а с правой отрицательные числа, идущие по возрастанию и т. п.
Начинается знакомство с сортировками с самых простых сортировок, при этом элементы, как правило, сортируются по убыванию или по возрастанию. В этой теме будет приведён пример сортировки массива по возрастанию.
Чтобы приступить к сортировке обычного массива, вы должны как минимум уметь менять переменные:

Нужно уметь не просто присваивать значения, а уметь взаимодействовать с уже существующими значениями переменных. Обычно создаётся временная переменная, которую используют как резерв для хранения значений. Эту маленькую задачу вам на самостоятельный разбор. Просто добавьте ещё одну переменную и заставьте её взаимодействовать с существующими: сначала нужно сохранить в резерве существующее значение, потом вытащить из резерва сохранённое значение.
Кроме умения использовать временную переменную для резервирования значений, нужно хотя бы немного представлять, что такое массив. Нужно понимать, что такое индексы массива, границы массива, значения массива.
Основа пузырьковой сортировки — сдвиг правильного элемента в край массива:

Смысл показанного кода в том, чтобы вы поняли основу движения в пузырьковой сортировке. Если анализировать массив слева-направо (что я и делаю), то самый левый элемент постепенно впрыгивая вправо по ячейкам сдвигается в правильную для себя позицию, в правый край. Прыжки происходят, когда условием сравнения определяется, что элемент находится не на своём месте.
Более полный код пузырьковой сортировки:

После каждого обхода массива, сдвигавшего некоторый элемент в правильную позицию, процесс сдвига происходит заново, только первоначальная позиция только что пододвинутого элемента больше не учитывается. Происходит сдвиг точки отсчёта и процесс повторяется. Таким образом точка отсчёта сдвигается по всему массиву. Это всё достигается путём оборачивания сдвига одного элемента в цикл. Вот и всё.
Особенно внимательным надо быть к границам массива. Поскольку в моём коде процесс происходит слева-направо, а элемент сравнивается с правостоящим, то при обходе массива нужно бежать к предпоследнему элементу, а не последнему. Последний элемент учтётся как правостоящий, в противном случае последний элемент массива будет сравнен с элементом, стоящим за пределами массива, а в этом ничего хорошего нет. При сдвиге некоторого элемента в край переменная j обозначает правостоящий элемент. Поскольку изначально она непосредственный сосед, то она при каждом новом проходе (после вставки некоторого элемента в свой край) принимает значение i+1, потом она становится вторым соседом, третьим соседом и т. д. Поскольку она правый сосед, то её учитывать надо вместе с последним элементом массива.
Распознавание границ массива — это хороший навык, который должен у вас появиться. Это одна из причин, почему стоит изучать пузырьковую сортировку, она хорошо способствует пониманию выхода за пределы или неполного захвата массива при анализе. Как сортировка — пузырьковая сортировка в реальных задачах не применяется вообще, потому что очень долго работает на больших массивах, предпочтение отдают другим видам сортировок.
Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

Добавить комментарий

Ваш e-mail не будет опубликован.

Поиск

 
     

Случайная книга в электронном формате

Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Когда проходишь IQ тест в интернете... помни что самый главный критерий определения твоего IQ — это отправишь ты СМС или нет...

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок