Theory: Sorting arrays

Array sorting is a basic algorithmic task you often have to do in job interviews. In real coding, however, arrays are sorted using ready-made functions from the standard library. In JavaScript, sorting is done using the sort() array method:

const numbers = [8, 3, 10];
// sort changes the array!
numbers.sort((a, b) => a - b); // sorting in ascending order
console.log(numbers); // => [3, 8, 10]

// You can reverse the array using reverse() after performing sort()
// Also changes the array
numbers.reverse();
console.log(numbers); // => [10, 8, 3]

Then why do they as these questions? Usually the interviewer wants to know the following:

1. Is the candidate actually aware of the existence of different algorithms.
2. Can they program (i.e., make a program themselves using only their head).
3. How does their algorithmic thinking work.

Knowing algorithms really affects how we think and how fast we work things out. And although it's impossible to know all the algorithms, you should at least have an idea of the most important ones, and ideally, be able to implement them. Our list of recommended books includes at least one book entirely devoted to algorithms.

In addition, Robert Martin, in his book "The Clean Coder" , talks about the Kata approach, a concept taken from martial arts.

The principle behind learning a martial art based on kata is that by repeating kata many thousands of times, a martial arts practitioner makes their body accustomed to certain kinds of movements, essentially having it in their muscle memory. Thus, when having to fight, their body works "by itself" on the basis of reflexes embedded in the constant repetition of the kata. It's also believed that kata has a meditative effect.

Robert Martin recommends solving classic algorithmic problems from time to time to stay in shape. This topic has become so popular that if you google javascript github kata, you will see many repositories with similar tasks.

Sorting

There are many ways to sort an array. The most popular one when learning is bubble sort.

The algorithm involves repeatedly passing through the array to be sorted. For each iteration, the elements in the sequence are compared in pairs, and if the order of the pair is wrong, the elements exchange places. Passes through the array are repeated N-1 times, or until the next pass is no longer needed, which means the array is sorted. Each time the algorithm passes through the inner loop, the next largest element of the array is put in its place at the end of the array next to the previous “largest element”, and the smallest element moves one position to the beginning of the array (going up to the desired position as though it were a bubble in water. Hence the name of the algorithm).

// The function changes the incoming coll array
const bubbleSort = (coll) => {
  let stepsCount = coll.length - 1;
  // Declaring a variable called swapped, the value of which indicates whether
  // the elements swapped places while the array was being searched
  let swapped;
  // do...while loop. while works almost identically
  // The difference in test condition Here it is done not before the loop body, but after
  // Such a loop is useful if the body needs to be executed at least once in any case
  do {
    swapped = false;
    // Rearrange the array and swap the elements if the previous one
    // is bigger than the next
    for (let i = 0; i < stepsCount; i += 1) {
      if (coll[i] > coll[i + 1]) {
        // temp is a temporary constant for storing the current item
        const temp = coll[i];
        coll[i] = coll[i + 1];
        coll[i + 1] = temp;
        // If "if" worked, and the elements were swapped,
        // set swapped to true
        swapped = true;
      }
    }
    // Decrease the counter by 1, since the largest element is already
    // at the end of the array
    stepsCount -= 1;
  } while (swapped); // continue until swapped === true

  return coll;
};

console.log(bubbleSort([3, 2, 10, -2, 0])); // => [ -2, 0, 2, 3, 10 ]

The entire code of this function is divided into two levels:

1. An internal for loop that traverses the array from beginning to end, swapping elements in pairs if they need to be sorted.
2. An external do...while loop that determines when to stop. Note that in the worst case this loop will be executed coll.length times, any time this algorithm is used, the worst case is in which the largest or smallest element is at opposite ends of the array from where it is in the sorted version.

Bubble sorting is the simplest and most intuitive sorting algorithm. It's very useful to be able to implement it from memory. Try it on your own computer without looking up the theory.