В 90% случаях, проходя интервью на должность разработчика в любой компании, вас попросят написать алгоритм сортировки. Поэтому можно сказать, что хорошего программиста от плохого отличает умение здесь и сейчас написать алгоритм сортировки (но это не точно). Как не парадоксально, многие синьоры сходу не напишут вам ту или иную сортировку, ведь в современных языка программирования в Java в том числе, уже реализованы методы сортировки, причем метод sort() работает таким образом, что анализирует объем данных для сортировки и выбирает на основании наиболее эффективный метод сортировки. Вообще теме сортировки данных уделено огромное внимание, проведено такое же количество исследований и тема сортировки вечная.
Мы выяснили, что в современных реалиях помнить методы сортировки не имеет смысла, в особенности если вы разрабатываете на языкам типа Java, для которых написано невероятное количество библиотек. Однако, понимать в общих чертах популярные методы все же нужно. И так, на интервью вас просят написать алгоритм сортировки. Ручаюсь, первым что придет в вашу голову будет сортировка методом “Пузырька”. Этим “Пузырьком” нас пичкали еще в младших классах, потом повторяли все это в старших классах и университете. Думаю поэтому любой человек мало мальски сведущий в информационных науках слышал о “Пузырьке”.
В чем же простота легендарного “Пузырька”? Конечно, в его легкости. 6 строк кода на Java. 6 КАРЛ!!! Однако, даже сходу вспомнить эти 6 строк не всегда удается. А все потому что мы не запоминаем код, мы запоминаем суть. И в вопросе пузырьковой сортировки само название подсказывает нам ассоциацию, с сутью алгоритма.
Сортировка “Пузырьком” называется так, потому что самый большой “пузырь” всегда всплывает вверх, за ним следует пузырь поменьше и так далее до самого маленького “пузырька”.
На рисунке видно как последовательно “всплывают пузырьки” наверх массива (в данном случае меньшие всплывают наверх). Запомнив эту легкую ассоциацию вы всегда сможете даже если вам разбудят среди ночи написать сортировку пузырьком.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
import java.util.Arrays; public class Sort { public static void main(String[] args) { int[] array = {10, 3, 53, 2, 5, 7, 3, 6, 12, 3, 32, 65}; //исходный массив // Сортировка пузырьком int temp; // переменная для замены for (int i = array.length - 1; i > 0; i--) { // внешний цикл for (int j = 0; j < i; j++) { // внутренний цикл if (array[j] > array[j + 1]) { // сравнение temp = array[j]; // если истино, то меняем array[j] = array[j + 1]; // местами элементы array[j + 1] = temp; } } } // конец сортировки System.out.println(Arrays.toString(array)); //выводим результат на консоль } } |
Результат выглядит следующим образом:
|
1 |
[2, 3, 3, 3, 5, 6, 7, 10, 12, 32, 53, 65] |
Как можно увидеть в алгоритме сортировки пузырьком есть инвариант.
Инвариант – это выражение, истинность которого сохраняется при выполнении одного шага алгоритма. В данном случае инвариантом является то, что после каждого прохода цикла на вершине массива элементы будут отсортированы. Поэтому мы используем внешний цикл, каждый раз уменьшая количество сравнений на 1. Видеть инварианты в алгоритмах это полезный навык, который пригодится вам как разработчику.
Сложность алгоритма сортировки “Пузырьком”.
Предположим, у необходимо отсортировать массив из 10 элементов. Внешний цикл сделает 9 операций, внутренний каждый раз на интеграцию меньше т.е. 9, 8, 7, 6, … , 1. Всего будет произведено 9+8+7+6+5+4+3+2+1 = 45 шагов в случае если массив был отсортирован в обратную сторону. Получаем, что сложность примерно N^2/2, где N – количество элементов массива. В обозначении О – синтаксиса сложность равна О(N^2). Основной минус алгоритма сортировки “Пузырьком” – его медленная скорость.
