Однажды, новогодним вечером, вдохновившись статьей про пузырьковую сортировку и ее модификации, я решил написать свою реализацию, и подумать, как бы я смог ее улучшить. А заодно начать все-таки изучать JAVA (по профессии я не программист, хотя немного писал).
Зачем в наши дни нужна сортировка пузырьком?
Она ведь практически самая медленная.
У нее самый высокий (квадратичный) алгоритм сложности.
Но! Она самая простая в реализации и весьма наглядная, и часто используется в образовательных целях или на собеседованиях джуниоров/интернов.
Кроме того, с небольшими модификациями, можно достичь интересных результатов.
Новичков в программировании и заинтересовавшихся — прошу под кат.
Итак, сразу преследуем несколько целей.
Написать реализацию классической пузырьковой сортировки;
Попробовать написать модифицированный алгоритм, который должен обогнать классический «пузырек»;
Изучить основы JAVA и немного ООП.
Всю работу с сортировками и их обработкой вынесем в отдельный класс ArrayUtils, из класса Run будем вызывать методы сортировки и формировать очередность вызовов с разными наборами данных.
В классе ArrayUtils у нас будет:
- Собственно сам массив
- В качестве простейших метрик, добавим две переменные compareValue и switchValue
Метод вывода результатов и метрик results();
Метод validation(), чтобы сразу проверять, действительно ли сортировка работает корректно;
Валидацию я сделал следующим способом.
Конструктор класса ArrayUtils получает на вход массив, который копирует в два локальных массива array и sortedArray, последний тут же сортируем штатным сортировщиком Arrays.sort().
public class ArrayUtils {
final private int[] array;
final private int[] sortedArray;
long switchCount, compareCount, timeAmount;
public ArrayUtils(int[] array) {
this.array = array;
this.sortedArray = Arrays.copyOf(array, array.length);
Arrays.sort(sortedArray);
}
}
Собственно метод validation() сравнивает текущее состояние array с нашим sortedArray, который отсортирован штатным сортировщиком ( в Java это одна из вариаций умного quicksort). Метод я вызываю через assert, в eclipse по умолчанию он выключен, но добавив опции -ea, наш assert корректно вываливается, если массив у нас ломается.
boolean validate()
{
for (int i=0; i < array.length; i++){
if (array[i] != sortedArray[i])
return false;
}
return true;
}
Теперь мы можем приступить к реализации пузырьковой сортировки, которая будет эталоном для дальнейшей работы.
public void sortBubbleClassic() {
int currentPosition;
int maxPosition;
int temp;
switchCount=0;
compareCount=0;
time = System.nanoTime();
for (maxPosition=array.length - 1; maxPosition >= 0;maxPosition--) {
for (currentPosition = 0; currentPosition < maxPosition; currentPosition++) {
compareCount++;
if (array[currentPosition] > array[currentPosition+1]) {
temp = array[currentPosition];
array[currentPosition] = array[currentPosition+1];
array[currentPosition+1] = temp;
switchCount++;
}
}
}
time = System.nanoTime() - time;
assert(validate());
return;
}
Пишем теперь класс Run, из которого будем вызывать сортировку, в нем добавляем метод fillRandom(), чтобы создать набор случайных данных для дальнейшей сортировки.
public class Run {
static public void FillRandom(int[] array) {
for (int count=0; count < array.length; count++) {
array[count] = (int)(Math.random()*100);
}
}
public static void main(String[] args)
{
int arraySize= 10000;
int random[] = new int[arraySize+1];
FillRandom(random);
ArrayUtils bubbleClassic = new ArrayUtils(random);
bubbleClassic.sortBubbleClassic();
bubbleClassic.results("Bubble Classic, random array");
}
}
Можно запускать. Передачу массива в созданный класс, с последующим его копированием я сделал для того, чтобы исходный массив со случайными данными у нас оставался неизменным, для последующего использования. Так мы сможем сортировать идентичный набор случайных данных разными способами.
Запускаем, получаем результат:
Bubble Classic, random array Compares: 50 005 000, Switches: 24 486 908, Time: 117 116 326Если assert не выкинул ошибку, значит алгоритм сортирует корректно. На массиве из 10.000 элементов мы получили свыше 50 млн сравнений и 24 млн перестановок.
Копируем наш метод sortBubbleClassic в sortBubbleAdvanced, и начинаем думать, что же можно улучшить.
Первым делом, я подумал, что можно добавить проверку на то, отсортирован ли у нас массив, чтобы не гонять по нему впустую.
Для этого я создал Boolean переменную changed, которую перед началом внутреннего цикла устанавливается в false, а внутри цикла, если мы делаем перестановку, устанавливается в true.
Если, пробежав весь внутренний цикл, мы не сделали ни одной перестановки, можно не гонять дальше циклы впустую, а сразу выходить.
public void sortBubbleClassic() {
int currentPosition;
int maxPosition;
int temp;
switchCount=0;
compareCount=0;
timeAmount = System.nanoTime();
Boolean changed; // проверка на перестановки
for (maxPosition=array.length - 1; maxPosition >= 0;maxPosition--)
{
changed=false; // обнуляем значение
for (currentPosition = 0; currentPosition < maxPosition; currentPosition++)
{
compareCount++;
if (array[currentPosition] > array[currentPosition+1]){
temp = array[currentPosition];
array[currentPosition] = array[currentPosition+1];
array[currentPosition+1] = temp;
switchCount++;
changed = true; // была перестановка
}
}
if (!changed) { // если не было перестановок - выходим сразу
timeAmount = System.nanoTime() - timeAmount;
assert(validate());
return;
}
}
timeAmount = System.nanoTime() - timeAmount;
assert(validate());
return;
}
Если в начале массива, у нас есть большое число, мы тянем его вправо, совершая кучу перестановок. Поэтому сразу появилась мысль, что можно сразу переместить его в конец массива.
Однако, делать много проверок, чтобы выяснять куда именно его нужно кинуть — накладно. Поэтому я сделал простейшее решение — проверяем, если текущее значение больше, чем значение в крайнем правом элементе — меняем их местами. Пусть и незначительно, но сократим количество перестановок.
Сразу и вторая оптимизация — если у нас маленькое число есть в самом конце массива, оно вообще прибежит в начало массива через N внутренних циклов, практически равных количеству элементов в массиве. Поэтому добавляем еще одну проверку, чтобы обменять местами текущее значение и самое левое значение в массиве, если оно меньше. Само по себе, это действие дает лишнюю проверку, но ускоряет несильно. Но зато, если мы пробежали внутренний цикл, мы можем быть уверены, что в самой левой позиции нашего массива данных, находится самое маленькое число. А это означает, что мы теперь можем начинать внутренний цикл не с первого элемента, а со второго. И так, с каждым шагом, мы теперь будем урезать массив для внутреннего цикла сразу на два значения — слева и справа. Это уже явный прирост.
Теперь располагаем наши три проверки рационально.
Первой проверкой идет основная пузырьковая — сравниваются два элемента, затем сравниваем текущий элемент с самым левым элементом массива, на предмет кто меньше. Затем с самым правым, на предмет, кто больше.
public void sortBubbleAdvanced(){
int currentPosition;
int maxPosition; // урезаем массив справа
int minPosition = 0; // урезаем массив слева
boolean changed; // остановиться, если уже отсортировано
int temp;
switchCount = 0;
compareCount = 0;
timeAmount = System.nanoTime();
for (maxPosition = array.length - 1; maxPosition >= 0; maxPosition--)
{
changed=false;
for (currentPosition = minPosition; currentPosition < maxPosition; currentPosition++)
{
if (array[currentPosition] > array[currentPosition+1]){ // обычная пузырьковая проверка двух элементов
temp = array[currentPosition+1];
array[currentPosition+1] = array[currentPosition];
array[currentPosition] = temp;
switchCount++;
changed=true;
}
if (array[currentPosition] < array[minPosition]){ // проверяем самый левый элемент массива
temp = array[minPosition];
array[minPosition] = array[currentPosition];
array[currentPosition] = temp;
switchCount++;
changed=true;
}
if (array[currentPosition] > array[maxPosition]){ // проверяем самый правый элемент массива
temp = array[maxPosition];
array[maxPosition] = array[currentPosition];
array[currentPosition] = temp;
switchCount++;
changed=true;
}
compareCount+=3;
}
if (!changed) {
timeAmount=System.nanoTime()-timeAmount;
assert(validate());
return;
}
compareCount++;
minPosition++ // урезаем массив слева
}
timeAmount=System.nanoTime()-timeAmount;
assert(validate());
return;
}
Можно проверять, что у нас вышло. Правим класс Run, чтобы добавить теперь проверку двух методов и запускаем
Bubble Classic, random array Compares: 50 005 000, Switches: 24 758 509, Time: 105 797 881
Bubble Advanced, random array Compares: 112 317 213, Switches: 18 684 909, Time: 87 415 460
Как видим, результат весьма значительный. Количество сравнений выросло более чем в два раза. Но зато сократилось количество перестановок, а они по времени «дороже», поэтому по времени мы выигрываем около 15%!..
Добавим еще два набора данных — уже отсортированный инкрементальный массив, и отсортированный в обратном порядке — декрементальный (по идее он должен быть самым worst case для сортировки), добавляем их в класс Run и добавляем вызовы sortBubbleClassic и sortBubbleAdvanced для всех трех массивов — random, incremental и decremental
static public void fillDecremental(int[] array) {
for (int count=0; count < array.length; count++) {
array[count] = array.length-count;
}
}
static public void fillIncremental(int[] array) {
for (int count=0; count < array.length; count++) {
array[count] = count;
}
}
Смотрим результаты:
Bubble Classic, random array Compares: 50 005 000, Switches: 24 678 169, Time: 116 314 053
Bubble Advanced, random array Compares: 111 879 748, Switches: 18 615 013, Time: 77 282 419
Bubble Classic, decremental array Compares: 50 005 000, Switches: 50 005 000, Time: 48 202 818
Bubble Advanced, decremental array Compares: 112 527 500, Switches: 49 985 004, Time: 77 115 071
Bubble Classic, incremental array Compares: 50 005 000, Switches: 0, Time: 24 805 261
Bubble Advanced, incremental array Compares: 30 000, Switches: 0, Time: 35 084
На случайном наборе данных, наш продвинутый метод ожидаемо побеждает, а на decremental он почти на 60% дольше ;(
Зато он просто мгновенно проверяет уже отсортированный массиве, благодаря нашей маленькой проверке с переменной changed.
Меня такой результат порадовал лишь частично. Нельзя оставлять оптимизацию алгоритма, если он на каких-то наборах может показать результат хуже оригинала. Размышляя, как можно улучшить пузырьковую сортировку, не меняя основной принцип, я обратил внимание на то, что в «пузырьке», большие числа активно путешествуют вправо с каждым проходом внутреннего цикла, плюс максимальное число тоже туда перемещается. Таким образом, наша правая часть массива становится отсортированной раньше левой части… Эта мысль реализовалась в следующую идею:
При каждой перестановке, я запоминаю эту позицию. Дойдя до последнего элемента внутреннего цикла, я могу уменьшить массив справа не на единицу, а сразу обрезать до этой последней позиции, где была перестановка, так как это означает, что все позиции после нее уже отсортированы.
Количество циклов должно значительно сократиться, как минимум примерно в два раза для декрементального массива.
Реализуется это всего тремя строчками:
public void sortBubbleAdvanced(){
int currentPosition;
int maxPosition;
int changedMaxPosition = array.length - 1; // самая правая позиция
int minPosition = 0;
boolean changed;
int temp;
switchCount = 0;
compareCount = 0;
timeAmount = System.nanoTime();
for (maxPosition = array.length - 1; maxPosition >= 0; minPosition++) // тут уже не нужно уменьшать правую позицию, поэтому запихнем сюда minPosition++
{
changed=false;
for (currentPosition = minPosition; currentPosition < maxPosition; currentPosition++)
{
if (array[currentPosition] > array[currentPosition+1]){
temp = array[currentPosition+1];
array[currentPosition+1] = array[currentPosition];
array[currentPosition] = temp;
switchCount++;
changed=true;
changedMaxPosition = currentPosition; // запоминаем что тут была перестановка
}
if (array[currentPosition] < array[minPosition]){
temp = array[minPosition];
array[minPosition] = array[currentPosition];
array[currentPosition] = temp;
switchCount++;
changed=true;
}
if (array[currentPosition] > array[maxPosition]){
temp = array[maxPosition];
array[maxPosition] = array[currentPosition];
array[currentPosition] = temp;
switchCount++;
changed=true;
}
compareCount+=3;
}
if (!changed) {
timeAmount=System.nanoTime()-timeAmount;
assert(validate());
return;
}
compareCount++;
maxPosition = changedMaxPosition; // теперь максимальная позиция - сразу на последнюю перестановку
}
timeAmount=System.nanoTime()-timeAmount;
assert(validate());
return;
}
Смотрим, что у нас вышло:
Bubble Classic, random array Compares: 50 005 000, Switches: 25 020 725, Time: 117 550 372
Bubble Advanced, random array Compares: 45 090 482, Switches: 10 174 100, Time: 70 032 156
Bubble Classic, decremental array Compares: 50 005 000, Switches: 50 005 000, Time: 47 815 033
Bubble Advanced, decremental array Compares: 60 022 000, Switches: 30 003 000, Time: 46 042 519
Bubble Classic, incremental array Compares: 50 005 000, Switches: 0, Time: 25 072 582
Bubble Advanced, incremental array Compares: 30 000, Switches: 0, Time: 34 773
Еще примерно на 10% у нас ускорилась сортировка на случайных данных, и ДА, на декрементальном массиве с небольшим отрывом, но мы обогнали классический «пузырек» — как и предполагалось, время уменьшилось примерно в два раза.
Инкрементальный массив у нас проходит мгновенно.
Благодаря резкому сокращению пустых проходов по уже отсортированной части, количество проверок продвинутого алгоритма уменьшилось, и в некоторых случаях даже меньше, чем в оригинале, а количество перестановок значительно меньше всегда (ну и кроме проверок, это же просто расходы на пустой проход по массиву).
Итак, оставаясь в пределах главной идеи пузырьковой сортировки, мы смогли заметно улучшить результат.
Что можно сделать еще?
Давайте сравним наш алгоритм, с лидером quicksort.
Пишем простую реализацию (честно говоря, просто украл в инете, слегка подправив, чтобы оставались метрики, но учитывая, что quicksort использует рекурсию, по-хорошему надо было бы добавить метрику для нее… но как ее сравнивать с алгоритмами без рекурсии? В общем, не суть...), итак:
public void quickSort() {
timeAmount = System.nanoTime();
switchCount = 0;
compareCount = 0;
doQuickSort(0, array.length - 1);
timeAmount = System.nanoTime() - timeAmount;
assert(validate());
}
private void doQuickSort(int startPosition, int lastPosition) {
if (startPosition >= lastPosition) {
compareCount++;
return;
}
int tempStartPosition = startPosition, tempLastPosition = lastPosition;
int currentPosition = tempStartPosition - (tempStartPosition - tempLastPosition) / 2;
while (tempStartPosition < tempLastPosition) {
while (tempStartPosition < currentPosition && (array[tempStartPosition] <= array[currentPosition])) {
compareCount++;
tempStartPosition++;
}
while (tempLastPosition > currentPosition && (array[currentPosition] <= array[tempLastPosition])) {
compareCount++;
tempLastPosition--;
}
if (tempStartPosition < tempLastPosition) {
int temp = array[tempStartPosition];
array[tempStartPosition] = array[tempLastPosition];
array[tempLastPosition] = temp;
switchCount++;
if (tempStartPosition == currentPosition)
currentPosition = tempLastPosition;
else if (tempLastPosition == currentPosition){
currentPosition = tempStartPosition;
compareCount++;
}
compareCount++;
}
compareCount++;
}
doQuickSort(startPosition, currentPosition);
doQuickSort(currentPosition + 1, lastPosition);
}
Смотрим результаты:
Bubble Classic, random array Compares: 50 005 000, Switches: 24 684 713, Time: 117 338 627
QuickSort, random array Compares: 453 318, Switches: 22 234, Time: 3 000 141
Bubble Advanced, random array Compares: 44 832 715, Switches: 10 048 493, Time: 70 540 407
Bubble Classic, decremental array Compares: 50 005 000, Switches: 50 005 000, Time: 47 269 214
QuickSort, decremental array Compares: 153 632, Switches: 5 000, Time: 179 766
Bubble Advanced, decremental array Compares: 60 022 000, Switches: 30 003 000, Time: 45 579 908
Bubble Classic, incremental array Compares: 50 005 000, Switches: 0, Time: 24 927 899
QuickSort, incremental array Compares: 143 632, Switches: 0, Time: 134 437
Bubble Advanced, incremental array Compares: 30 000, Switches: 0, Time: 35 394
Как и ожидалось, quicksort легко делает все наши алгоритмы и на случайном наборе данных и на декрементальном массиве. Но внезапно, на уже отсортированном массиве, наш продвинутый пузырек делает его почти в 4 раза по скорости!
Сперва, я подумал, что особого смысла в этом нет. Ну да, проверяет мой продвинутый алгоритм, что массив уже отсортирован быстрее, но задача такая встречается крайне редко.
Затем я прикинул, что это не все — на самом деле, практически с той же скоростью, наш продвинутый алгоритм, за один проход, может отсортировать в лучшем случае 3 числа (минимальное, максимальное, и еще парочку подвигать попутно), и решил проверить на практике.
Я изменил метод, который создает инкрементальный массив, чтобы в середине отсортированного массива было несколько случайных чисел:
static public void fillIncremental(int[] array) {
for (int count=0; count < array.length; count++) {
array[count] = count;
}
for (int count=array.length/2; count < array.length/2+5; count++) // в середине массива заполним 5 элементов случайными значениями
array[count]=(int)Math.random()*100;
}
Смотрим, что вышло:
Bubble Classic, incremental array Compares: 50 005 000, Switches: 24 995, Time: 24 751 238
QuickSort, incremental array Compares: 219 964, Switches: 8 426, Time: 249 624
Bubble Advanced, incremental array Compares: 179 740, Switches: 24 981, Time: 125 123
Продвинутый пузырьковый алгоритм справился быстрее, чем quicksort, отсортировав 5 случайных чисел почти в два раза быстрее.
Увеличим размер массива в 10 раз, проверим на всякий случай:
Bubble Classic, incremental array Compares: 5 000 050 000, Switches: 249 995, Time: 2 168 664 535
QuickSort, incremental array Compares: 2 539 530, Switches: 86 062, Time: 11 479 582
Bubble Advanced, incremental array Compares: 1 799 740, Switches: 249 981, Time: 6 411 974
Все равно, почти вдвое быстрее.
На почти отсортированном массиве, где количество неотсортированных элементов не превышает некоторого минимального количества, наш переделанный пузырьковый алгоритм показывает не квадратичную сложность, а обычный logN, а учитывая его простоту по реализации, он обходит quicksort.
Если добавить количество не отсортированных элементов примерно до 10-ти, скорость quicksort и bubbleAdvanced сравниваются, а затем наш алгоритм все-же скуксивается в безнадежную квадратичную медлительность. Тем не менее, если нужно отсортировать несколько случайно вставленных значений в заранее отсортированном массиве данных — он оказался вне конкуренции.
Мораль, итоги, выводы.
Итоги, а точнее цифры были показаны выше, можно обсудить в комментариях.
Исходники — доступны на github (правда там немного мусора, я пытался освоить maven, но исходные файлы классов можно скомпилировать в любой IDE или консоли).
Вдобавок я таки написал свой первый JAVA код, чуть сложнее, чем HelloWorld. А также узнал как минимум про два метода сортировки изнутри.
А кроме того, если поковыряться в алгоритмах, можно потом интуитивно догадываться, какие результаты можно ожидать, и куда копать.
Пока что, я не очень понимаю, почему декрементальный массив обрабатывается быстрее, чем случайный. Мне казалось, что для bubble sort самый плохой случай, это именно decremental массив. Возможно, это связано с тем, что в случайном массиве встречаются одинаковые числа, в общем еще есть над чем подумать.
Выводы и мораль — под определенный набор данных, если скорость важна, всегда имеет смысл подумать и придумать свой велосипед, который может обогнать штатные методы, основная задача которых показать быстрый результат в наиболее распространенных случаях.
Автор: saboteur_kiev
