Что спрашивают на собеседовании: обзор алгоритмов, часть 1

Всем доброго дня суток! Различные виды алгоритмов используются в проектах чаще, чем это может показаться. К примеру, нужно отсортировать некоторые данные по тем или иным параметрам (колонкам), чтобы мы могли без особых усилий перемещаться по ним. Поэтому нет ничего странного в том, что и на собеседованиях при приеме на работу могут спросить о том или ином базовом алгоритме, и возможно, дать задание реализовать его при помощи кода. А так как вы на этом сайте, я осмелюсь предположить, что вы пишете на Java. Поэтому сегодня я предлагаю вам ознакомиться с некоторыми базовыми алгоритмами и с конкретными примерами их реализации на Java. Под некоторыми я подразумеваю:

1. Обзор алгоритмов сортировки массива:
   • пузырьковая сортировка,
   • сортировка выбором,
   • сортировка вставкой,
   • сортировка Шелла,
   • быстрая сортировка,
   • сортировка слиянием.
2. Жадный алгоритм.
3. Алгоритмы поиска пути:
   • обход в глубину,
   • обход в ширину.
4. Транспортный алгоритм — алгоритм Дейкстры.

Что же, без лишних предисловий приступим к делу.

1. Обзор алгоритмов сортировки

Пузырьковая сортировка

Данный алгоритм сортировки известен в первую очередь за счёт своей простоты, однако при этом он имеет одну из наиболее низких скоростей выполнения. В качестве примера рассмотрим пузырьковую сортировку для чисел в возрастающем порядке. Представим себе цепочку случайно расставленных чисел, для которых будут выполняться следующие шаги, начиная с начала цепочки:

• сравнить два числа;
• если число слева больше, то поменять их местами;
• перейти на одну позицию вправо.

После прохождения по всей цепочке с выполнением данных шагов мы обнаружим, что наибольшее число оказалось в конце нашего ряда чисел. Далее выполняется точно такой же проход по цепочке с выполнением вышеописанных шагов. Но в этот раз мы не будем включать последний элемент списка, так как он самый большой и уже стоит на последнем месте, как и должен. Опять, же мы получим последний элемент в конце нашего ряда рассматриваемых чисел. Соответственно, уже два наибольших числа будут стоять на своих местах. И опять запускается проход по цепочке за исключением элементов, которые уже на своих местах, до тех пор, пока все элементы не будут стоять в необходимом порядке. Давайте рассмотрим реализацию пузырьковой сортировки в Java-коде:

public class Solution {
   public static void main(String[] args) {
    int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
    bubbleSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void  bubbleSort(int[] array) {
       for(int i = array.length -1; i > 1; i--) {
         for (int j = 0; j < i; j++) { //
             if (array[j] > array[j+1]) {
                 int temp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = temp;
             }
         }
       }
   }
}

Как видите, ничего сложного тут нет, и всё вроде бы как здорово, если бы не одно “но”… Пузырьковая сортировка весьма и весьма медленная, с временной сложностью O(N²), так как мы имеем вложенные циклы. Внешний проход по элементам выполняется за N раз, внутренний — тоже N раз, и в итоге мы получаем N*N, N² итераций Более подробно изучить данный вид сортировки можно в этой статье.

Сортировка методом выбора

Данный алгоритм имеет схожесть с пузырьковой сортировкой, но работает он несколько быстрее. Опять в качестве примера возьмём ряд чисел, которые мы хотим расставить в возрастающем порядке. Суть алгоритма заключается в последовательном переборе всех чисел и выборе наименьшего элемента, который мы возьмём и поменяем местами с крайним элементом слева (0 элементом). Тут у нас получается ситуация, схожая с пузырьковой сортировкой, но в данном случае отсортированным элементом у нас будет наименьший. Поэтому, следующий проход по элементам будет начинаться с элемента под индексом 1. Опять же, данные проходы будет повторяться до тех пор, пока все элементы не будут отсортированы. Реализация в Java:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {

       for (int i = 0; i < array.length-1; i++) { // внешний обычный  цикл
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // вставка отссортиованного числа, в положеную ему ячейку
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

Данный алгоритм превосходит пузырьковую сортировку, ведь тут количество необходимых перестановок сокращается с O(N²) до O(N): мы не гоняем один элемент через весь список, но тем не менее, количество сравнений остается O(N²). Желающим ознакомиться подробнее с этим алгоритмом рекомендую этот материал.

Сортировка методом вставки

В очередной раз для примера возьмём ряд чисел, которые мы хотим расставить в возрастающем порядке. Данный алгоритм заключается в выставлении маркера, слева от которого элементы будут уже частично отсортированы между собой. На каждом шаге алгоритма будет выбираться один из элементов и помещаться на нужную позицию в уже отсортированной последовательности. Таким образом, отсортированная часть будет увеличиваться до тех пор, пока не будут просмотрены все элементы. Вы спросите: а где же взять ту часть элементов, которые уже отсортированы и после которых и нужно ставить маркер? Но ведь массив из первого элемента уже отсортирован, не так ли?Давайте посмотрим на реализацию в Java:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       insertionSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void insertionSort(int[] array) {

       for (int i = 1; i < array.length; i++) { // i - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного элемента
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Данный вид сортировки превосходит вышеописанные, так как несмотря на то, что время работы такое же — O(N²), этот алгоритм работает вдвое быстрее пузырьковой сортировки и немного быстрее сортировки выбором. Подробнее — вот тут.

Сортировка Шелла

Данная сортировка, по своей природе является модифицированной сортировкой методом вставки. О чём я говорю? Давайте по порядку. Выбирается шаг, причем к у этого выбора есть много подходов. Слишком подробно разбираться в этом вопросе не будем. Поделим наш массив пополам и получим некоторое число — это и будет нашим шагом. Итак, если у нас в массиве 9 элементов, то наш шаг будет 9/2 = 4,5. Дробную часть мы отбросим и получим 4, так как индексы массивов — только целые числа. С помощью данного шага мы составим связи для наших групп. Если элемент имеет индекс 0, то индекс следующего элемента в его группе — 0+4, то есть 4. Третий элемент будет иметь индекс 4+4, четвертый — 8+4, и так далее. У второй группы первый элемент будет 1,5,9…. В третьей и четвертой группе дела будут обстоять точно так же. В итоге из массива чисел {6,3,8,8,6,9,4,11,1} мы получим четыре группы: I — {6,6,1} II — {3,9} III — {8,4} IV — {8,11} Свои места в общем массиве они сохраняют, но для нас они помечены как участники одной группы: {6,3,8,8,6,9,4,11,1} Далее внутри этих групп происходит описанная выше сортировка вставками, после которой группы будут иметь вид: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} В общем массиве ячейки, занимаемые группами, останутся теми же, но внутри них изменится порядок, согласно порядку групп выше: {1,3,4,8,6,9,8,11,6} Массив стал немного более упорядоченным, не так ли? Следующий шаг, будет поделен на 2: 4/2 = 2 Имеем две группы: I — {1,4,6,8,6} II — {3,8,9,11} B общий массив: {1,3,4,8,6,9,8,11,6} Проходим по обеим группам алгоритмом сортировки вставкой, и получаем массив: {1,3,4,8,6,9,6,11,8} Сейчас наш массив почти отсортирован. Осталась последняя итерация алгоритма: делим шаг на 2: 2/2 = 1. Мы получаем группу, весь массив: {1,3,4,8,6,9,6,11,8} По которому проходим алгоритмом сортировки вставкой и получаем: {1,3,4,6,6,8,8,9,11} Давайте посмотрим, как мы может отобразить данную сортировку в Java-коде:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {
       int length = array.length;
       int step = length / 2;
       while (step > 0) {
           for (int numberOfGroup = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) {//сортировка вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

На данный момент толком не обоснована эффективность сортировки Шелла, так как в разных ситуациях результаты отличаются. Оценки, полученные на основании экспериментов, лежат в интервале от O(N^3/2) до O(N^7/6).

Быстрая сортировка

Это один из самых популярных алгоритмов, и поэтому на него стоит обратить особое внимание. Суть данного алгоритма заключается в том, что в списке с элементами выбирается опорный элемент — по сути любой элемент, относительно которого нужно отсортировать остальные значения. Значения меньше его — слева, значения больше — справа. Далее у правой и левой части также выбирается по опорному элементу и происходит то же самое: сортируются значения относительно этих элементов, потом у образовавшихся частей выбираются опорные элементы — и так до тех пор, пока мы не получим отсортированный ряд. Данный алгоритм в Java реализуется с помощью рекурсии:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       fastSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void fastSort(int[] array) {
       recursionFastSort(array, 0, array.length - 1);
   }


   public static void recursionFastSort(int[] array, int min, int max) {
       if (array.length == 0)// условие выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так как нечего уже делить
           return;


       int middle = min + (max - min) / 2;  // выбираем середину
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) {  // относительно элемента middle определяемменьшие элементы слева, большие справа
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) {      //меняем местами
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // запускаем рекурсию с элементами меньшими чем middle
           recursionFastSort(array, min, j);

       if (max > i)// запускаем рекурсию с элементами большими чем middle
           recursionFastSort(array, i, max);
   }
}

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

Сортировка слиянием

Эта сортировка тоже популярна. Она относится к одному из видов алгоритмов, работающих по принципу «разделяй и властвуй»: в них мы в первую очередь делим задачи на минимальные части (также представителем таких алгоритмов является быстрая сортировка). Итак, в чём же суть данного алгоритма?

Разделяй:

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

Властвуй:

Тут и начинается процесс, задавший название алгоритму — слияние. Для этого берутся два получившиеся упорядоченных массива и сливаются в один. При этом наименьший из первых элементов двух массивов записывается в результирующий массив, и эта операция повторяется, пока не закончатся элементы в этих двух массивах. То есть, если у нас есть два минимальных массива {6} и {4}, их значения будут сравнены и записан результат: {4,6}. Если будут отсортированные массивы {4,6} и {2,8}, то сперва сравнится значение 4 и 2, из которых 2 будет записано в результирующий массив. После этого будет сравниваться 4 и 8, 4 будет записано, и в конце сравнится 6 и 8. Соответственно, 6 будет записано, и только после него — 8. В итоге мы получим результирующий массив: {2,4,6,8}. Каким же образом это будет выглядеть в Java-коде? Для обработки данного алгоритма нам будет удобно воспользоваться рекурсией:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       testArr = mergeSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static int[] mergeSort(int[] array1) {
       int[] sortArr = Arrays.copyOf(array1, array1.length);// массив для сортировки
       int[] bufferArr = new int[array1.length];// буферный массив
       return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
           return sortArr;
       }

       // запускаем рекурсию, чтобы получить два отсортированных массива:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Слияние отсортированных массивов:
       int firstIndex = startIndex;
       int secondIndex = middle;
       int destIndex = startIndex;
       int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
       while (firstIndex < middle && secondIndex < endIndex) {
           result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
                   ? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
       }
       while (firstIndex < middle) {
           result[destIndex++] = firstSortArr[firstIndex++];
       }
       while (secondIndex < endIndex) {
           result[destIndex++] = secondSortArr[secondIndex++];
       }
       return result;
   }
}

Как и в быстрой сортировке, мы выносим рекурсивный метод в промежуточный, чтобы пользователю не нужно было заморачиваться над заданием дополнительных дефолтных аргументов, а можно было всего лишь задать массив, который необходимо отсортировать. Так как данный алгоритм имеет схожесть с быстрей сотрировкой, то и скорость его выполнения та же — O(N*logN).

2. Greedy Algorithms

Жадный алгоритм — это подход, при котором на каждом этапе принимаются локально оптимальные решения и допускается, что конечное решение также окажется оптимальным. “Оптимальное” решение — то, которое предлагает наиболее очевидную и немедленную выгоду на определенном шаге/этапе. Чтобы рассмотреть данный алгоритм, выберем довольно распространенную задачу — о рюкзаке. Давайте на секунду представим, что вы вор. Вы вломились ночью в магазин с рюкзаком, и перед вами некоторое множество товаров, которые вы можете украсть. Но при этом вместимость рюкзака ограничена — не более 30 условных единиц. В тоже время вы хотите унести набор товаров максимальной стоимости, которые только влезут в рюкзак. Как вы определите, что положить? Итак, жадный алгоритм для задачи о рюкзаке состоит в следующих шагах (считаем, что все предметы помещаются в рюкзак):

1. Выбрать максимально дорогой предмет из еще не затронутых.
2. Если он помещается в рюкзак, положить его туда, если нет — пропускаем.
3. Все предметы перебрали? Если нет — возвращаемся к 1 пункту, если да — бежим из магазина, так как наша цель тут выполнена.

Давайте это рассмотрим, но уже в Java. Так будет выглядеть класс предмета Item:

public class Item implements Comparable<Item> {
   private String name;
   private int weight;
   private int cost;

   public Item(String name, int weight, int cost) {
       this.name = name;
       this.weight = weight;
       this.cost = cost;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getCost() {
       return cost;
   }

   @Override
   public int compareTo(Item o) {
       return this.cost > o.cost ? -1 : 1;
   }
}

Тут ничего особого: три поля — name, weight, cost — для задания характеристик предмета. Также, как вы можете видеть, тут реализован интерфейс Comparable таким образом, чтобы мы могли сортировать наши Item по цене. Дальше смотрим на класс нашего рюкзака — Bag:

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentCost;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentCost = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentCost() {
       return currentCost;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentCost += item.getCost();
   }
}

• maxWeight — вместимость нашего рюкзака, которая задаётся при создании объекта;
• items — объекты находящиеся в рюкзаке;
• currentWeight, currentCost — текущий вес и стоимость всех вещей в рюкзаке, которые мы увеличиваем при добавлении нового предмета в методе addItem.

Собственно перейдем в класс, где и происходит всё действие:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("гитара",7, 800));
       items.add(new Item("утюг",6, 500));
       items.add(new Item("чайник",3, 300));
       items.add(new Item("лампа",4, 500));
       items.add(new Item("телевизор",15, 2000));
       items.add(new Item("ваза",2, 450));
       items.add(new Item("миксер",1, 400));
       items.add(new Item("блендер",3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
               ", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
} 

Для начала мы создаем список элементов, сортируем его. Создаем объект сумки с вместимость 30 единиц. Далее отправляем элементы и объект сумки в метод fillBackpack, в котором, собственно, и заполняется рюкзак по жадному алгоритму:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

Всё предельно просто: мы начинаем проходить по отсортированному по стоимости списку элементов и складывать их в сумку, если позволяет вместимость. Если же не позволяет, элемент будет пропущен и продолжится проход по остальным элементам до конца списка. Запустив main, мы получим вывод в консоль: Собственно, это и есть пример жадного алгоритма: на каждом шагу выбирается локально-оптимальное решение, а в итоге вы получаете глобально-оптимальное решение. В нашем случае оптимальный вариант — это наиболее дорогой предмет. Но является ли это лучшим решением? Вам не кажется, что можно немного модернизировать наше решение, чтобы можно было укомплектовать рюкзак с более высокой суммарной стоимостью? Давайте взглянем, как это можно сделать:

public static void effectiveFillBackpack(Bag bag, List<Item> items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getCost() / item.getWeight(), item);
   }

   for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
           bag.addItem(entry.getValue());
       }
   }
}

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

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

Получаем вывод в консоль: Немного лучше, не правда ли? Жадный алгоритм на каждом шагу делает локально оптимальный выбор в расчете на то, что итоговое решение также будет оптимальным. Это не всегда оправдано, но для многих задач жадные алгоритмы действительно дают оптимум. Временная сложность данного алгоритма — O(N), довольно неплохо, не так ли? Что же на этом, первая часть данной статьи подошла к концу. Если вам интересно продолжение данной статьи, в которой пойдет речь уже о графах и алгоритмах, связанных с ними, вы можете найти ее вот тут.