1,1
рейтинг
6 января в 03:25

Разработка → Еще один разбор пузырьковой сортировки tutorial recovery mode


Однажды, новогодним вечером, вдохновившись статьей про пузырьковую сортировку и ее модификации, я решил написать свою реализацию, и подумать, как бы я смог ее улучшить. А заодно начать все-таки изучать JAVA (по профессии я не программист, хотя немного писал).

Зачем в наши дни нужна сортировка пузырьком?
Она ведь практически самая медленная.
У нее самый высокий (квадратичный) алгоритм сложности.

Но! Она самая простая в реализации и весьма наглядная, и часто используется в образовательных целях или на собеседованиях джуниоров/интернов.
Кроме того, с небольшими модификациями, можно достичь интересных результатов.
Новичков в программировании и заинтересовавшихся — прошу под кат.


Итак, сразу преследуем несколько целей.
Написать реализацию классической пузырьковой сортировки;
Попробовать написать модифицированный алгоритм, который должен обогнать классический «пузырек»;
Изучить основы JAVA и немного ООП.

Всю работу с сортировками и их обработкой вынесем в отдельный класс ArrayUtils, из класса Run будем вызывать методы сортировки и формировать очередность вызовов с разными наборами данных.

В классе ArrayUtils у нас будет:
  1. Собственно сам массив
  2. В качестве простейших метрик, добавим две переменные compareValue и switchValue, чтобы считать количество сравнений и количество перемещений значений, а также timeAmount — время работы — они будут обновляться при запуске метода сортировки;
  3. Метод вывода результатов и метрик results();
  4. Метод validation(), чтобы сразу проверять, действительно ли сортировка работает корректно;


Валидацию я сделал следующим способом.
Конструктор класса ArrayUtils получает на вход массив, который копирует в два локальных массива array и sortedArray, последний тут же сортируем штатным сортировщиком Arrays.sort().
класс ArrayUtils
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);
    }

    void results(String text)
    {
        System.out.println(String.format("%-35s Compares: %, 15d, Switches: %, 15d, Time: %, 15d", text, compareCount, switchCount, timeAmount));
    }
}


Собственно метод validation() сравнивает текущее состояние array с нашим sortedArray, который отсортирован штатным сортировщиком ( в Java это одна из вариаций умного quicksort). Метод я вызываю через assert, в eclipse по умолчанию он выключен, но добавив опции -ea, наш assert корректно вываливается, если массив у нас ломается.
Validation method
boolean validate() 
{
    if (Arrays.equals(array,sortedArray))
        return true;
    return false;
}


Теперь мы можем приступить к реализации пузырьковой сортировки, которая будет эталоном для дальнейшей работы.
sortBubbleClassic
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(), чтобы создать набор случайных данных для дальнейшей сортировки.
Run.java
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.
Если, пробежав весь внутренний цикл, мы не сделали ни одной перестановки, можно не гонять дальше циклы впустую, а сразу выходить.
sortBubbleAdvanced - step 1
	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 внутренних циклов, практически равных количеству элементов в массиве. Поэтому добавляем еще одну проверку, чтобы обменять местами текущее значение и самое левое значение в массиве, если оно меньше. Само по себе, это действие дает лишнюю проверку, но ускоряет несильно. Зато, после завершения пробега внутреннего цикла, мы можем быть уверены, что в самой левой позиции нашего массива данных, находится самое маленькое число. Это означает, что мы теперь можем начинать внутренний цикл не с первого элемента, а со второго. С каждым шагом, мы теперь будем урезать массив для внутреннего цикла сразу на два значения — слева и справа. Это уже явный прирост.
Располагаем наши три проверки рационально.
Первой проверкой идет основная пузырьковая — сравниваются два элемента, затем сравниваем текущий элемент с самым левым элементом массива, на предмет кто меньше. Затем с самым правым, на предмет, кто больше.
sortBubbleAdvanced - step 2
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.

Меня такой результат порадовал лишь частично. Нельзя оставлять оптимизацию алгоритма, если он на каких-то наборах может показать результат хуже оригинала. Размышляя, как можно улучшить пузырьковую сортировку, не меняя основной принцип, я обратил внимание на то, что в «пузырьке», большие числа активно путешествуют вправо с каждым проходом внутреннего цикла, плюс максимальное число тоже туда перемещается. Таким образом, наша правая часть массива становится отсортированной раньше левой части… Эта мысль реализовалась в следующую идею:
При каждой перестановке, я запоминаю эту позицию. Дойдя до последнего элемента внутреннего цикла, я могу уменьшить массив справа не на единицу, а сразу обрезать до этой последней позиции, где была перестановка, так как это означает, что все позиции после нее уже отсортированы.
Количество циклов должно значительно сократиться, как минимум примерно в два раза для декрементального массива.
Реализуется это всего тремя строчками:
sortBubbleAdvanced - final step
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 использует рекурсию, по-хорошему надо было бы добавить метрику для нее… но как ее сравнивать с алгоритмами без рекурсии? В общем, не суть...), итак:
Простая реализация 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

Все равно, почти вдвое быстрее.
На почти отсортированном массиве, где количество неотсортированных элементов не превышает некоторого минимального количества, наш переделанный пузырьковый алгоритм показывает не квадратичную сложность, а обычный O(N), и учитывая его простоту по реализации, он обходит quicksort.

Если добавить количество не отсортированных элементов примерно до 10-ти, скорость quicksort и bubbleAdvanced сравниваются, а затем наш алгоритм все-же скуксивается в безнадежную квадратичную медлительность. Тем не менее, если нужно отсортировать несколько случайно вставленных значений в заранее отсортированном массиве данных — он оказался вне конкуренции.

Мораль, итоги, выводы.

Итоги, а точнее цифры были показаны выше, можно обсудить в комментариях.
Исходники — доступны на github (правда там немного мусора, я пытался освоить maven, но исходные файлы классов можно скомпилировать в любой IDE или консоли).
Вдобавок я таки написал свой первый JAVA код, чуть сложнее, чем HelloWorld. А также узнал как минимум про два метода сортировки изнутри.
А кроме того, если поковыряться в алгоритмах, можно потом интуитивно догадываться, какие результаты можно ожидать, и куда копать.
Пока что, я не очень понимаю, почему декрементальный массив обрабатывается быстрее, чем случайный. Мне казалось, что для bubble sort самый плохой случай, это именно decremental массив. Возможно, это связано с тем, что в случайном массиве встречаются одинаковые числа, в общем еще есть над чем подумать.

Выводы и мораль — под определенный набор данных, если скорость важна, всегда имеет смысл подумать и придумать свой велосипед, который может обогнать штатные методы, основная задача которых показать быстрый результат в наиболее распространенных случаях.
Сергей Кулик @saboteur_kiev
карма
10,0
рейтинг 1,1
DevOps
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (11)

  • 0
    на собеседованиях джуниоров/интернов.

    это вы лично с таким встречались?

    наш переделанный пузырьковый алгоритм показывает не квадратичную сложность, а обычный logN

    такое ощущение, что вы ошиблись, на сколько я вижу из кода, один проход по массиву в отсортированном случае ваш Bubble Sort все равно делает, т. е. O(N) сравнений.

    который может обогнать штатные методы

    а со штатными методами вы вроде ничего и не сравнивали, вы сравнивали с «самописным» Quick Sort, т. е. другими словами сравнивали один велосипед с другим. Причем один из велосипедов вы доработали напильником, а второй взяли как есть.

    boolean validate() 
    {
        for (int i=0; i < array.length; i++){
            if (array[i] != sortedArray[i])
                return false;
        }
        return true;
    }
    

    Array.equals?
  • 0
    Точно, O(n), ошибся.
    Что же касается штатных методов — в штатной сортировке нет счетчиков проверок и перестановок. Но не проблема проверить и штатный.
    Добавил следующий код:
    public void javaQuickSort() {
        timeAmount = System.nanoTime();
        Arrays.sort(array);
        timeAmount = System.nanoTime() - timeAmount;
    }
    


    Результат:
    Bubble Classic, random array        Compares:      50 005 000, Switches:      24 750 505, Time:     116 024 377
    QuickSort, random array             Compares:         436 415, Switches:          22 062, Time:       2 783 738
    Bubble Advanced, random array       Compares:      45 003 506, Switches:      10 067 942, Time:      58 992 210
    Java sort, random array             Compares:               0, Switches:               0, Time:         504 525
    
    Bubble Classic, decremental array   Compares:      50 005 000, Switches:      50 005 000, Time:      46 714 701
    QuickSort, decremental array        Compares:         153 632, Switches:           5 000, Time:         199 326
    Bubble Advanced, decremental array  Compares:      60 022 000, Switches:      30 003 000, Time:      44 974 788
    Java sort, decremental array        Compares:               0, Switches:               0, Time:         192 186
    
    Bubble Classic, incremental array   Compares:      50 005 000, Switches:          24 995, Time:      24 873 255
    QuickSort, incremental array        Compares:         219 964, Switches:           8 426, Time:         241 551
    Bubble Advanced, incremental array  Compares:         179 740, Switches:          24 981, Time:         126 364
    Java sort, incremental array        Compares:               0, Switches:               0, Time:         150 581
    

    Учитывая, что штатный сортировщик, скорее всего оптимизирован с учетом работы java-машины, весьма неплохой результат обогнать его на декрементальном массиве с пятью случайными числами велосипедом, слепленным за пару дней новичком.

    Если интересно, можно скопировать реализацию штатного сортировщика, добавить в него счетчики метрик, чтобы еще больше выровнять условия. Тем не менее, я осознаю что статья полезнее для новичков, чем для про, и количество добавлений в избранное меня радует.
    • 0
      весьма неплохой результат обогнать его на декрементальном массиве с пятью случайными числами велосипедом

      Вы обогнали стандартную сортировку в очень-очень специфичном случае и при простом типе ключа для сравнения, причем разница минимальна, а во всех остальных тестах с треском провалились — мне кажется, что вы сильно переоцениваете результат.
      • 0
        Как я писал в самом начале — цель была не создать супер-пупер алгоритм.
        Понятно же, что пузырьковая сортировка, остается квадратичной, и не способна обогнать тот же quicksort в принципе, а я хотел оставаться в рамках именно пузырьковой сортировки, но оптимизировать процесс.

        Меня просто удивило, что в определенном случае, даже такой вариант обогнал штатную оптимизированную сортировку, о чем я и написал вывод, что в узкоспециализированном случае, велосипед может помочь.

        Разница минимальна — вы не правы. Если убрать счетчики метрик, разница будет почти в два раза, и как я приводил пример, разница остается такой же на бОльшем массиве, то есть в случае практически отсортированного массива, алгоритм ведет себя не как квадратичный, а как O(n).

        И еще раз — я совершенно не переоцениваю результат. Результатом является реализация простейших алгоритмов сортировки на java и туториал для новичков, о чем говорят метки и хабы, поэтому, пожалуйста принимайте это во внимание. Я всегда готов прислушаться к советам.
        • 0
          Как я писал в самом начале — цель была не создать супер-пупер алгоритм.

          Я ничего не говорил про алгоритм, я говорил про ваш вывод о «весьма неплохом результате».

          Меня просто удивило, что в определенном случае, даже такой вариант обогнал штатную оптимизированную сортировку, о чем я и написал вывод, что в узкоспециализированном случае, велосипед может помочь.

          Ваш случай уж слишком специализированный: 5 элементов в середине массива случайны — что-то уж слишком специфичное. Если бы вы хотя бы подвигали эти элементы по массиву, или меняли бы их число, было бы хотя бы примерно видно где «границы применимости», и тогда уже можно было бы удивляться каким-то результатам.

          Если убрать счетчики метрик, разница будет почти в два раза,

          Получается, что счетчики отнимают 40% времени вашего Advanced Buble Sort-а? Вот это уже интересный результат… Заглянул в ваш код, вы запускаете каждую сортировку один раз, это выглядит не очень честным сравнением для JVM. Я полагаю, что JVM для нахождения и оптимизации Hot Path-ов нужно какое-то время, т. е. более честно будет если вы сначала «прогреете» алгоритмы — на количество сравнений и перестановок это не повлияет, но может повлиять на на окружающий код (это только предположение, я не знаю наверняка). Кроме того можно получить и среднее время и разброс результатов.

          И еще раз — я совершенно не переоцениваю результат.

          весьма неплохой результат обогнать его на декрементальном массиве с пятью случайными числами велосипедом

          Ну ок, я не буду настаивать.
          • –1
            > Получается, что счетчики отнимают 40% времени вашего Advanced Buble Sort-а? Вот это уже интересный результат…
            Не совсем так.
            Я сравнил время, которое затратил тот quicksort, который я нашел в инете и штатный javasort, после чего убрал счетчики из quicksort. Он ускорился почти в полтора раза. Следовательно счетчики, особенно в quicksort едят много. Вызов рекурсии я при этом не считал.

            Что же по поводу случайных элементов в середине массива — в статье я же писал, что 10 элементов уже практически без выигрыша, что интуитивно понятно — алгоритм за один проход может раскидать три элемента. Значит 10 элементов это уже примерно 3-4 прохода. А где именно они находятся — не важно, все равно выполняется полный проход по всему массиву.
  • 0
    Пожалуйста, не пишите бенчмарки с помощью System.nanoTime(), потому что они скорее всего будут неправильными, лучше возьмите JMH.
    • 0
      System.nanoTime() не неправильный, он не идеально точный, и если не помнить про кеширование и оптимизацию java машины, можно ошибиться. Но на простых вещах, например циклы и долгие рассчеты, когда разница в 10-20 милисекунд не играет разницы — он вполне приемлим, ибо встроить его в уже рабочий проект — легко.

      JMH неудобен тем, что его сложно просто так взять и вставить в уже готовый проект.
      Проще создать с нуля новый maven проект на JMH и специально под него переписать все, что нужно потестить, что я и сделал за несколько вечеров, пока ковырялся с JMH (кстати, официальная документация — не очень).

      Добавил в исходники на гитхабе рабочий вариант с сортировкой рандомного массива, с десятью warm-up и 10 итерациями для замера.
      Но результаты не отличаются от тех, что я получил раньше.
      Benchmark                       Mode  Cnt   Score   Error  Units
      MyBenchmark.emptySortProcedure  avgt   10   0,464 ? 0,005  ms/op
      MyBenchmark.sortBubbleAdvanced  avgt   10  49,661 ? 0,395  ms/op
      MyBenchmark.sortBubbleClassic   avgt   10  96,772 ? 1,483  ms/op
      MyBenchmark.sortJavaQuickSort   avgt   10   0,689 ? 0,009  ms/op
      MyBenchmark.sortQuickSort       avgt   10   1,292 ? 0,014  ms/op
      

      Тут замеры только для случайного массива — остальные не писал, было интересно вообще понять, будет ли с JMH другой результат, но нет — как и ранее, на рандомном массиве данных bubbleAdvanced примерно в два раза быстрее bubbleClassic, QuickSort и штатный JavaQuickSort практически мгновенны.

      Кстати, штатный сортировщик в Java (Java 8) — это два метода. Сперва определяется размер массива, затем маленьких массивов используется quicksort, для больших mergesort.
  • 0
    Целый литературный рассказ. Похвально. Однако, я считаю, что кроме формального описания, описания на конкретном языке программирования, литературного, есть еще иной способ описания алгоритмов — как некоего набора шагов, которые способен понять даже ребёнок. Это можно сделать словами, графически, с помощью анимации и т.д. Я не знаю Java, но с ходу мне не понять особенностей реализации.
    Википедия говорит, что для улучшения алгоритма пузырьковой сортировки достаточно добавить досрочный выход из внешнего цикла. Вдобавок эту задачу можно повесить на переменную, которая участвует в процесс обмена.
    Пример: http://ru.vingrad.com/Sortirovka-puzyrkom-uluchshennaya-id56971ea2ae20150a56f985e1
    • 0
      Так собственно досрочный выход я добавил чуть ли не первым делом.
      Думаю, основное ускорение дало возможность идти сразу с двух сторон — сокращать недосортированную часть массива не только справа, но и слева за один проход.

      Анимацию думаю еще добавить, и это могла бы быть отдельная статья. Но минусующие без комментариев меня демотивируют.
      • 0
        Ну судя по нашей переписке, вы читаете комментарии не очень внимательно, что вполне может демотивировать тех кто их пишет, и это при том, что пузырьковая сортировка не самая интересная для обсуждения тема.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.