What they ask at an interview: review of algorithms, part 1

Good afternoon everyone! Various types of algorithms are used in projects more often than you might think. For example, we need to sort some data according to certain parameters (columns) so that we can navigate through it without much effort. Therefore, there is nothing strange in the fact that during job interviews they may be asked about one or another basic algorithm, and perhaps given the task of implementing it using code. And since you are on this site, I would venture to guess that you write in Java. Therefore, today I invite you to familiarize yourself with some basic algorithms and specific examples of their implementation in Java. By some I mean:

1. Overview of array sorting algorithms:
   • bubble sort,
   • selection sort,
   • insertion sort,
   • Shell sort,
   • quick sort,
   • merge sort.
2. Greedy algorithm.
3. Pathfinding algorithms:
   • crawling in depth
   • wide crawl.
4. The transport algorithm is Dijkstra's algorithm.

Well, without further ado, let's get down to business.

1. Overview of sorting algorithms

Bubble sort

This sorting algorithm is known primarily for its simplicity, but at the same time it has one of the lowest execution speeds. As an example, consider bubble sort for numbers in ascending order. Let's imagine a chain of randomly placed numbers for which the following steps will be performed, starting from the beginning of the chain:

• compare two numbers;
• if the number on the left is greater, then swap them;
• move one position to the right.

After going through the entire chain and performing these steps, we will find that the largest number is at the end of our series of numbers. Next, exactly the same pass along the chain is performed, following the steps described above. But this time we will not include the last element of the list, since it is the largest and is already in last place, as it should be. Again, we will get the last element at the end of our series of numbers in question. Accordingly, the two largest numbers will already be in their places. And again the passage along the chain is started, excluding the elements that are already in place, until all the elements are in the required order. Let's look at the implementation of bubble sort in Java code:

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;
             }
         }
       }
   }
}

As you can see, there is nothing complicated here, and everything seems to be great, if not for one “but”... Bubble sort is very, very slow, with a time complexity of O(N²) , since we have nested loops. The external pass through the elements is performed N times, the internal one is also N times, and as a result we get N*N , N² iterations. You can study this type of sorting in more detail in this article .

Sorting by selection

This algorithm is similar to bubble sort, but it works a little faster. Again, as an example, let's take a series of numbers that we want to arrange in ascending order. The essence of the algorithm is to sequentially go through all the numbers and select the smallest element, which we take and swap places with the leftmost element (0 element). Here we get a situation similar to bubble sort, but in this case the sorted element will be the smallest one. Therefore, the next pass through the elements will begin with the element at index 1. Again, these passes will be repeated until all elements are sorted. Implementation in 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;
       }
   }
}

This algorithm is superior to bubble sort, because here the number of necessary permutations is reduced from O(N²) to O(N): we do not push one element through the entire list, but nevertheless, the number of comparisons remains O(N²) . For those wishing to learn more about this algorithm, I recommend this material .

Insertion sort

Once again, as an example, let's take a series of numbers that we want to arrange in ascending order. This algorithm consists of placing a marker, to the left of which the elements will already be partially sorted among themselves. At each step of the algorithm, one of the elements will be selected and placed at the desired position in the already sorted sequence. So the sorted part will continue to grow until all the elements have been looked at. You may ask: where can I get that part of the elements that are already sorted and after which you need to put a marker? But the array of the first element is already sorted, isn’t it? Let's look at the implementation in 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]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

This type of sorting is superior to the ones described above, because despite the fact that the running time is the same - O(N²) , this algorithm works twice as fast as bubble sort and slightly faster than selection sort. Read more here .

Shell sort

This sort, by its nature, is a modified insertion sort. What I'm talking about? Let's go in order. A step is selected, and there are many approaches to this choice. We will not go into this issue in too much detail. Let's divide our array in half and get a certain number - this will be our step. So, if we have 9 elements in the array, then our step will be 9/2 = 4.5 . We discard the fractional part and get 4 , since array indices are only integers. With this step we will create connections for our groups. If an element has index 0, then the index of the next element in its group is 0+4 , that is, 4 . The third element will have an index of 4+4 , the fourth will have an index of 8+4 , and so on. For the second group, the first element will be 1,5,9…. In the third and fourth groups, things will be exactly the same. As a result, from the array of numbers {6,3,8,8,6,9,4,11,1} we get four groups: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} They retain their places in the general array, but for us they are marked as members of the same group: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Further within these groups the insertion sort described above occurs , after which the groups will look like: I - {1,6,6} II - {3,9} III - {4,8} IV - {8,11} In the general array, the cells occupied by the groups , will remain the same, but the order within them will change, according to the order of the groups above: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } The array is a little more ordered, isn't it? The next step will be divided by 2: 4/2 = 2 We have two groups: I - {1,4,6,8,6} II - {3,8,9,11} B general array: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } We go through both groups using the insertion sort algorithm and get an array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Now our array is almost sorted. The last iteration of the algorithm remains: we divide the step by 2: 2/2 = 1. We get a group, the entire array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } By which we go through the insertion sort algorithm and get : { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Let's see how we can display this sorting in Java code:

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]) {//sorting вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

At the moment, the effectiveness of Shell sorting is not really substantiated, since the results differ in different situations. Estimates obtained from experiments range from O(N ^3/2 ) to O(N ^7/6 ) .

Quick sort

This is one of the most popular algorithms, and therefore it is worth paying special attention to. The essence of this algorithm is that a pivot element is selected from a list of elements—essentially any element against which the remaining values ​​need to be sorted. Values ​​less than it are on the left, values ​​greater than it are on the right. Next, the right and left parts are also selected by the supporting element and the same thing happens: the values ​​are sorted relative to these elements, then the supporting elements are selected from the resulting parts - and so on until we get a sorted row. This algorithm in Java is implemented using recursion:

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)// condition выхода из рекурсии,  если длина массива равна 0
           return;

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


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


       int i = min, j = max;
       while (i <= j) {  // относительно element 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) // запускаем рекурсию с elementми меньшими чем middle
           recursionFastSort(array, min, j);

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

Without a doubt, the quicksort algorithm is considered the most popular, since in most situations it runs faster than others, in O(N*logN) time .

Merge sort

This sorting is also popular. It refers to one of the types of algorithms that work on the principle of “divide and conquer”: in them we first divide tasks into minimal parts ( quick sort is also a representative of such algorithms ). So, what is the essence of this algorithm?

Divide:

The array is divided into two parts of approximately the same size, each of these two parts is divided into two more, and so on until the smallest indivisible parts remain. Least indivisible parts are when each array has one element, which means that such an array is automatically considered sorted.

Conquer:

This is where the process begins that gives the name to the algorithm - merging . To do this, take the two resulting ordered arrays and merge them into one. In this case, the smallest of the first elements of the two arrays is written to the resulting array, and this operation is repeated until there are no more elements in the two arrays. That is, if we have two minimal arrays {6} and {4} , their values ​​will be compared and the result will be written: {4,6} . If there are sorted arrays {4,6} and {2,8} , then first the value 4 and 2 will be compared , of which 2 will be written to the resulting array. After this, 4 and 8 will be compared , 4 will be written down, and at the end 6 and 8 will be compared . Accordingly, 6 will be written, and only after it - 8. As a result, we will get the resulting array: {2,4,6,8} . How will this look in Java code? To process this algorithm, it will be convenient for us to use recursion:

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;
   }
}

As in quick sort, we move the recursive method into an intermediate one so that the user does not need to bother setting additional default arguments, but can just specify the array that needs to be sorted. Since this algorithm is similar to faster erasure, its execution speed is the same - O(N*logN) .

2. Greedy Algorithms

A greedy algorithm is an approach that takes locally optimal decisions at each stage and assumes that the final solution will also be optimal. The “optimal” solution is the one that offers the most obvious and immediate benefit at a certain step/stage. To consider this algorithm, we will choose a fairly common problem - about a backpack. Let's pretend for a second that you are a thief. You broke into a store at night with a backpack, and in front of you there are a number of goods that you can steal. But at the same time, the capacity of the backpack is limited - no more than 30 conventional units. At the same time, you want to carry a set of goods with the maximum value that will fit into your backpack. How do you decide what to put in? So, the greedy algorithm for the knapsack problem consists of the following steps (we assume that all objects fit into the knapsack):

1. Choose the most expensive item from those not yet touched.
2. If it fits in your backpack, put it there; if not, skip it.
3. Have you sorted through all the items? If not, we return to point 1, if yes, we run from the store, since our goal here is completed.

Let's look at this, but in Java. This is what the Item class will look like:

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;
   }
}

There is nothing special here: three fields - name , weight , cost - for specifying the characteristics of the item. Also, as you can see, the Comparable interface is implemented here so that we can sort our Items by price. Next we look at the class of our backpack - 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 is the capacity of our backpack, which is set when creating the object;
• items — objects in the backpack;
• currentWeight , currentCost - the current weight and cost of all things in the backpack, which we increase when adding a new item in the addItem method .

Actually, let's go to the class, where all the action happens:

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());
}
}

First, we create a list of elements and sort it. Create a bag object with a capacity of 30 units. Next, we send the elements and the bag object to the fillBackpack method , in which, in fact, the backpack is filled using a greedy algorithm:

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

Everything is extremely simple: we begin to go through the list of items sorted by cost and put them in a bag, if capacity allows. If it does not allow, the element will be skipped and the passage through the remaining elements will continue until the end of the list. By running main, we get the following output to the console: Actually, this is an example of a greedy algorithm: at each step a locally optimal solution is selected, and in the end you get a globally optimal solution. In our case, the best option is the most expensive item. But is this the best solution? Don't you think we could modernize our solution a little so that we can equip a backpack with a higher total cost? Let's take a look at how this can be done:

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());
       }
   }
}

Here we first calculate the weight-price ratio for each item. So to speak, how much does one unit of a given item cost? And by these values ​​we sort our items and add them to our bag. Let's run:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

We get the output to the console: A little better, isn't it? A greedy algorithm makes a locally optimal choice at each step with the expectation that the final solution will also be optimal. This is not always justified, but for many problems greedy algorithms do provide an optimum. The time complexity of this algorithm is O(N) , which is pretty good, right? Well, with that, the first part of this article has come to an end. If you are interested in the continuation of this article, which will talk about graphs and algorithms related to them, you can find it here .