Що запитують на співбесіді: огляд алгоритмів, частина 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) , досить непогано, чи не так? Що ж на цьому, перша частина цієї статті добігла кінця. Якщо вам цікаво продовження цієї статті, в якій йтиметься вже про графи та алгоритми, пов'язані з ними, ви можете знайти її ось тут .