As I continue my journey of learning Data Structures and Algorithms, my next topic is sorting algorithms! These algorithms have been a real sticking point for me in my learning process. In this blog, I will attempt to aid my learning through teaching. I will begin with some of the basic sorting algorithms and work my way up to more advanced methods in later blogs. As always, these topics are new to me so I welcome any and all feedback!

Sorting Algorithms

Sorting algorithms are a fundamental tool in coding and computer science. They are used to "rearrange a given array or list elements", often in order to aid searching. This is most frequently accomplished by making a series of comparisons. Though there are some other methods that do not involve comparison, which I will discuss in a later blog.

Bubble Sort

Bubble sort is considered one of the most basic sorting algorithms. Though it is not very efficient or commonly used, it establishes a key foundation for other sorting algorithms. It "works by repeatedly swapping the adjacent elements if they are in the wrong order." The best use case for Bubble Sort is when the data set is very small or nearly sorted. To implement:

1. Create a function that accepts an array
2. Develop logic for swapping values - use indices to make swaps
3. Begin looping from the END of the array toward the beginning with a variable i
4. Begin an inner loop with a variable j that loops from the beginning until i-1
5. Compare neighboring values - so check is arr[j] is greater than arr[j+1]
   • If it is greater - swap values!
6. Return the fully sorted array The code is implemented as follows:

function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}

The best possible time complexity for Bubble Sort is O(N). The worst and average time complexity is O(N^2). If time complexity is a concern, Bubble Sort should really only be used if the data is nearly sorted. The space complexity is O(1).

Selection Sort

Another basic sorting algorithm is Selection Sort. Selection Sort is similar to Bubble Sort, however, instead of placing large values into a sorted position - it places small values into a sorted position. It also only compares the lowest value to the entire data set vs. comparing two values at a time. To implement:

1. Create a function that accepts an array *with the same swapping logic used in Bubble Sort
2. Store the first element as the smallest value *It is considered the smallest value because it is the only value you have seen so far
3. Continue to compare it to the next value until you find a smaller value
4. Once you find a smaller value - save the index of that value as the new minimum
5. If the new minimum is not the value(index) that you started with then - SWAP
6. Repeat this process with each element until the array is fully sorted

function selectionSort(arr) {
  const swap = (arr, idx1, idx2) =>
    ([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);

  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowest] > arr[j]) {
        lowest = j;
      }
    }
    if (i !== lowest) swap(arr, i, lowest);
  }

  return arr;
}

Similarly to Bubble Sort, this algorithm is not very efficient. Its best, average, and worst time complexity is O(N^2). It can be useful if you are trying to minimize the number of swaps you are making. The space complexity is also O(1).

Insertion Sort

The final basic sorting algorithm I will be covering in this blog is Insertion Sort. Similar to Bubble Sort, this algorithm is efficient if your data is ALMOST sorted. This makes it so it also works well if your data needs to be continually sorted over time. Insertion Sort is unique in that instead of focusing on swapping individual elements, it continually builds up the sorted array by creating a larger portion that is already sorted. Instead of making a series of swaps, you place the data where it needs to go when you first look at the individual element. A nice comparison is that it "works the way we sort playing cards in our hands." To implement:

1. Create a function that accepts an array
2. Select the second element in the array (the first element will be considered already sorted until we look at other elements)
3. Compare the second element to the one before - if necessary - SWAP
4. Continue to the next (third) element and if it is in the incorrect order, iterate through the sorted portion (i.e. the left side of the array) until you find the correct placement
5. Repeat this process until the array is fully sorted The code is implemented as follows:

function insertionSort(arr){
  let currentVal;
    for(let i = 1; i < arr.length; i++){
        currentVal = arr[i];
        for(let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

Similarly to some of the other algorithms we have looked at, the best possible time complexity is O(N) - this is if the data is almost sorted. The average and worst time complexity is O(N^2). The space complexity is O(1).

Conclusion

These three sorting algorithms are often considered the basic or beginner sorting algorithms. In general, they are not very efficient. However, there are some cases where they may be more preferable to more complex methods - such as if your data set is small or nearly sorted. These algorithms also offer improved readability when compared to the more complex algorithms. It is also important to learn them as they offer a strong foundation as you move through the more efficient sorting methods. In the coming blogs, I will attempt to tackle a few more advanced sorting algorithms.

Sources

1. For more detailed information, checkout this Udemy course I am currently taking! JavaScript Algorithms and Data Structures Masterclass
2. Geeks for Geeks - Sorting Algorithms
3. Geeks for Geeks - When to use Sorting Algorithms