Сортировка пузырьком на Си

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

Упорядоченный массив создается на том же участке памяти, где находится исходная последовательность. Идея метода состоит в том, чтобы попарно сравнивать соседние элементы. Каждый проход начинается с начала последовательности. Сравнивается первый элемент со вторым: если порядок между ними нарушен, то они меняются местами. Затем сравниваются второй с третьим, третий с четвертым и так далее до конца массива; элементы с неправильным порядком в паре меняются местами. В итоге, после первого прохода, максимальный (или минимальный, в зависимости от вида сортировки: по возрастанию/по убыванию) элемент будет находится на последнем месте в массиве, он как бы “всплывет” наверх. Именно поэтому этот метод называется сортировка пузырьком. На следующем проходе рассматривается последовательность от 1 до N-1, затем от 1 до N-2, и так до конца. После каждого прохода можно делать проверку: выполнялись ли перестановки элементов. Если не выполнялись, то сортировка завершена.

При сортировке пузырьком максимальное число сравнений составляет 0,5N², а среднее число сравнений приблизительно 0,25N².

Ниже приведена реализация алгоритма сортировки на языке программирования Си:

где N – число элементов в массиве, а mass[] – массив элементов.

Приведем пример консольной программы на языке программирования Си, которая считывает массив, сортирует его пузырьком и выводит результат на экран.

Разберем код программы. Подключим необходимые библиотеки (строки 1-2), предложим пользователю ввести число N – количество элементов в массиве (строка 7), считаем число N (строка 8), выделим память под массив (строка 10), предложим пользователю ввести элементы массива (строка 11), считаем элементы массива (строки 12-13), выполним сортировку пузырьком (строки 18-33), выведем отсортированный массив на экран (35-36), освободим память, выделенную под массив элементов (строка 38).

Работа программы представлена на скриншоте ниже:

Сортировка пузырьком на Си - vscode.ru

Для того, чтобы скачать исходник программы, нажмите на кнопку:

Скачать исходник

 

 

Смотрите также:

Сортировка методом выбора на языке Си

Сортировка вставками на Си

Сортировка методом подсчета на Си

 

Сортировка пузырьком на Си
5 (100%) 1 vote

Поделиться в соц. сетях:

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">