Theory and Tasks for Students - Spring 2019
Сортировки - Пузырёк, Усовершенствованный Пузырёк

Во многих алгоритмах требуется упорядочить данные в том или ином порядке. Для этого используются алгоритмы сортировок. В основном все такие алгоритмы производят две операции - сравнение двух элементов коллекции и перестановка двух элементов. Мы будем изучать в основном квадратичные сортировки, т.е. сортировки со сложностью O(N2).

Сортировка "Пузырьком" (Bubble Sort)

int[] arr = new int[n]; // допустим, что массив уже заполнен и переменная n определена for (int i = 0; i < arr.Length; i++) { for (int j = 0; j < arr.Length - i - 1; j++) { if (arr[j] > arr[j + 1]) { int c = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = c; } } }

На каждой итерации внешнего цикла по i происходит проход по всей неотсортированной части массива: чем больше i, тем меньше эта часть, поэтому ограничение второй цикла - arr.Length - i - 1. При проходе по массиву сравнивается очередной элемент arr[j] со следующим arr[j + 1], поэтому, в условии второго цикла вычитается единица - иначе при сравнении последнего элемента массива со "следующим" будет выход за границу массива. Итак, если очередной элемент больше следующего, то они меняются местами. Таким образом, при каждом проходе по неотсортированной части в конец "всплывает" самый большой элемент, отсюда и название. Очевидно, если поменять знак в сравнении, элементы будут отсортированы в обратном порядке, т.е. по убыванию. Также несложно догадаться, что сортировать можно не только числа, а, например, строки или любые объекты, для которых возможно описать операцию сравнения. Более точная оценка сложности - O(N * (N - 1) / 2).

Сортировка Улучшенным "Пузырьком" (Improved Bubble Sort)

У такой реализации алгоритма есть один недостаток - если массив становится отсортированным до выполнения всех проходов, алгоритм не завершит работу и будет совершать бесполезные перестановки. Внесём небольшую модификацию - будем проверять, произошла ли хотя бы одна перестановка в течении очередного прохода. Если нет, значит массива отсортирован и можно выйти из цикла. bool flag; for (int i = 0; i < arr.Length; i++) { flag = false; // false - не происходило перестановок for (int j = 0; j < arr.Length - i - 1; j++) { if (arr[j] > arr[j + 1]) { int c = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = c; flag = true; } } if (!flag) { break; } } Также можно провести и вторую оптимизацию - перебирать элементы до индекса последней произведённой перестановки в предыдущем проходе, т.к. отсутствие перестановок означает упорядоченность элементов. bool flag; int lastSwap = arr.Length - 1, curSwap; // swap - перестановка do { // необходимо выполнить хотя бы один проход для проверки массива на упорядоченность curSwap = 0; for (int j = 0; j < lastSwap; j++) { if (arr[j] > arr[j + 1]) { int c = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = c; curSwap = j; } } lastSwap = curSwap; } while (lastSwap > 0);