В данной статье мы рассмотрим сортировку методом пузырька, реализованную на языке C#.
Описание алгоритма:
Идея данной сортировки заключается в попарном сравнении соседних элементов, начиная с нулевого в массиве. Больший элемент при этом в конце первой итерации оказывается на месте последнего элемента массива, и в следующих итерациях мы его уже не сравниваем его с остальными элементами (то есть у нас будет n-1 сравнений). Затем таким же образом мы находим второй по максимальности элемент и ставим его на предпоследнее место, и т. д. После всех итераций получится, что на месте нулевого элемента окажется элемент с наименьшим числовым значением, а на месте последнего — с наибольшим числовым значением. Таким образом у нас как бы «всплывают» элементы от большего к меньшему.
Примечание: можно также реализовать последовательность от меньшего к большему. В коде это лишь замена знака «>» на знак «<» в коде (подробнее в примечании ниже).
Пример:
У нас имеется массив: 7 2 9 4 1 0
Проводим первую итерацию. Мы берем нулевой элемент массива (7) и сравниваем его с соседним:
7<>2 9 4 1 0
Так как 7 больше, чем 2, мы меняем эти элементы местами. Получается массив:
2 7 9 4 1 0
Далее мы сравниваем 7 и 9.
2 7<>9 4 1 0
Число 9 больше, чем 7. Значит 7 остаётся на своём месте. Теперь мы будем сравнивать число 9 с остальными числами и, если 9 будет больше, чем соседние с ним числа, то будет меняться местами с ними.
2 7 9<>4 1 0
2 7 4 9<>1 0
2 7 4 1 9<>0
2 7 4 1 0 9
Большего числа, чем 9 в нашем массиве не оказалось, поэтому 9 занимает последний элемент в массиве. На этом первая итерация окончена. Теперь мы найдём следующее число, которое по значению будет меньше 9, но больше остальных чисел. Причём нам незачем больше трогать 9, так как оно уже на своём месте и в любом случае у него самое больше числовое значение. Поэтому количество шагов в итерации у нас уменьшается на 1 (n-1).
Вторая итерация. Мы опять «захватываем» нулевой элемент массива (2) и сравниваем его с соседним.
2<>7 4 1 0 9
Число 2 меньше, чем 7, поэтому они не будут меняться местами, а на следующем шаге будет сравниваться число 7 со следующим соседним элементом.
2 7<>4 1 0 9
И следующим:
2 4 7<>1 0 9
И следующим:
2 4 1 7<>0 9
Отлично, мы нашли второй элемент, и он занимает предпоследнее место в массиве. Вторая итерация окончена. Опять уменьшаем шаги итерации на 1, так как нам не надо больше сравнивать оставшиеся числа с 7.
После второй итерации наш массив выглядит так:
2 4 1 0 7 9
Третья итерация. Повторяем всё точно так же. Начинаем с нулевого элемента и ищем большее значение среди оставшихся чисел.
2<>4 1 0 7 9
2 4<>1 0 7 9
2 1 4<>0 7 9
Итого получается:
2 1 0 4 7 9
Третья итерация окончена. Начинаем четвертую и не забываем уменьшить шаги итерации на 1.
2<>1 0 4 7 9
1 2<>0 4 7 9
1 0 2 4 7 9
Осталась последняя итерация и сравнение лишь двух чисел:
1<>0 2 4 7 9
Сортировка окончена. Наш упорядоченный массив теперь выглядит вот так:
0 1 2 4 7 9
Код программы:
Программу будем делать в консоли. Для начала создадим функцию самой сортировки (перед функцией main):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
static int[] BubbleSort(int[] mas) { int temp; for (int i = 0; i < mas.Length; i++) { for (int j = i + 1; j < mas.Length; j++) { if (mas[i] > mas[j]) { temp = mas[i]; mas[i] = mas[j]; mas[j] = temp; } } } return mas; } |
Мы создаём функцию BubbleSort. В неё будет передан массив mas, который мы заполним числами для сортировки.
Здесь мы сравниваем, так сказать, предыдущий элемент (i) с последующим (j).
Если элемент массива под номером i будет больше, чем элемент массива под номером j, то меняем элементы местами и продолжаем сравнение дальше, как в алгоритме.
Примечание: выше обсуждалась возможность менять «направление» сортировки, где меньший элемент будет в конце массива, а больший в начале. Для этого надо лишь поменять строку if (mas[i] > mas[j]) на if (mas[i] < mas[j]).
Данная функция возвращает отсортированный массив mas (строка 16).
Теперь разберем основную функцию main:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
static void Main(string[] args) { Console.WriteLine("Сколько чисел будем сортировать?"); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите числа для сортировки:"); int[] mas=new int[N]; for (int i = 0; i < mas.Length; i++) { mas[i] = Convert.ToInt32(Console.ReadLine()); } BubbleSort(mas); Console.WriteLine("После сортировки:"); for (int i = 0; i < mas.Length; i++) { Console.WriteLine(mas[i]); } Console.ReadLine(); } |
В строках 3-10 мы считываем информацию, которую введет нам пользователь. Сначала это будет количество элементов в массиве, затем сами значения этих элементов массива.
В строке 11 мы вызываем функцию сортировки, передаём в неё полученный массив, получаем отсортированный массив.
В остальной части кода мы выводим полученный массив на экран.
Вот так будет выглядеть наша программа в консоли:
Сортировка методом пузырька на C#
Исходный код программы:
Скачать исходникПоделиться в соц. сетях:
Спасибо большое!
Хорошее описание,Спасибо большое!!!