Sorting algorithms

There are many different sorting algorithms, each with its own set of advantages and disadvantages depending on the type of data being sorted and the desired outcome.

Bubble Sort

Compares an item with the next item and swaps them if the first item is greater than the next item. Doing this for one time will move the biggest item of the array to the last position. For the remaining items we need to do the same thing but this time only until we reach the last item since the last item is already been sorted.

for (let j = items.length - 1; j > 0; j--) {
  for (let i = 0; i < j; i++) {
	  if (items[i] > items[i + 1]) {
		const temp = items[i];
		items[i] = items[i + 1];
		items[i + 1] = temp;
	  }
  }
}

Since we need two nested loops to perform this sort it's from \(O(n^2)\). But the more accurate number of comparisons is as below:

(n-1) + (n-2) + (n-3) + ... + 1 = n(n - 1)/2

We only use bubble sort when we want to implement a sort from scratch quickly, but it's not a good sort for real scenarios.

Bubble sort is a stable algorithm which means identical elements will appear in the same order as they appear in the input.

Selection Sort

We set the first item equal to the minimum item. We loop through the array and compare this minimum variable to all the items. If we could find an item less than the minimum then we update the minimum index to be the new item. After the first loop, we will find the smallest item in the array. We swap this minimum item with the first item in the array so the first item of the array is now the smallest item. Similar to bubble sort we need to perform this process for all the items in the array.

for (let j = 0; j < items.length - 1; j++) {
  let minIndex = j;
  for (let i = j + 1; i < items.length; i++) {
	if (items[i] < items[minIndex]) {
	  minIndex = i;
	}
  }

  const temp = items[minIndex];
  items[minIndex] = items[j];
  items[j] = temp;
}

Similar to bubble sort, since we have two nested for loops, the time complexity of this algorithm is \(O(n^2)\). However, in bubble sort for moving an item to its right position we had to swap those items one by one until it reaches its correct position but in selection sort, we just compare the items and only swap the item once. Hence if the cost of writing to memory matters this algorithm is a better choice compared to bubble sort. This algorithm writes to the memory \(n\) times, but bubble sort writes to the memory \(n^2\) times. Still, not a good sorting algorithm and only use it when you want to implement something from scratch with minimum code.

Insertion Sort

Very similar to bubble sort but in this method, we select the second item as the key and compare this key with all the items before it. For the first iteration, we just compare the second item (key) with the first item. If the item is greater than the key then we move the item to the right and at the end of this loop, we place the key wherever the loop is finished.

for (let j = 1; j < items.length; j++) {
  let key = items[j];
  let index = j;
  
  for (let i = j - 1; i > -1; i--) {
	index = i;
	if (items[i] > key) {
	  items[i + 1] = items[i];
	} else {
	  index = i + 1;
	  break;
	}
  }

  items[index] = key;
}

Similar to bubble and selection sorts, two nested loops then \(O(n^2)\).

Merge Sort

One of the most popular sort algorithms that is based on divide and conquer. Its time complexity for best, worst and average is \(O(nlog{n})\). In this algorithm, we select the midpoint of an array and divide the array into two sub-arrays and we do this again in a recursive function until we reach the base state in which the array length is 1 that doesn't need to be sorted. Once the left and right sub-arrays only have one member it's easy to sort them, we simply compare them and the smaller item goes behind the bigger item. However, the result of this merge is a sorted array of size two which needs to be merged with another array of any size from other iterations. We use double pointers to compare the two arrays and create a single sorted array from them.

  const sort = (start, end) => {
    if (start === end) return [items[start]];
    
    const mid = Math.floor((end - start) / 2);
    const left = sort(start, start + mid);
    const right = sort(start + mid + 1, end);

    return merge(left, right);
  }

  function merge(left, right) {
    const result = [];
    let l = 0;
    let r = 0;

    while (l < left.length && r < right.length) {
      if (left[l] < right[r]) {
        result.push(left[l]);
        l++;
      } else {
        result.push(right[r]);
        r++;
      }
    }

    for (let i = l; i < left.length; i++) {
      result.push(left[i]);
    }

    for (let i = r; i < right.length; i++) {
      result.push(right[i]);
    }

    return result;
  }

The space complexity of this algorithm is \(O(n)\) and whenever we need better memory usage combined with a good time complexity similar to merge sort we can use quick sort which it's average and best case time complexity is \(O(nlogn)\) and its space complexity is also \(O(logn)\). The only scenario that merge sort works better than quick sort is when the array is sorted in the reverse order which for merge sort is still \(O(nlogn)\) but for quick sort is \(O(n^2)\).

Quick Sort

This algorithm also works by "divide and conquer" method. Instead of selecting the midpoint of the array, it selects a pivot that is any item in the array and then compares all the items with this pivot and puts the smaller items on the left and greater items on the right of the pivot. This process is called partitioning that partitions the array into two subarrays. It continues doing this for every sub-array until the sub-array size is one which means it's already sorted.