Alexandra

Posted on

DSA: Sorting like a boss with JS

One of the most common operations in programming is sorting a collection. Generally, this is a costly operation for most algorithms, as sorting has the notion of comparing every element with each other. We will see which algorithms overcome this with divide and conquer techniques, and how the simpler linear sorting algorithms are implemented. We will also discuss the complexity of each algorithm.

Bubble Sort

Bubble sort is a very simply sorting algorithm. This algorithm doesn't have particular use cases other than have an introduction to the sorting algorithms for education purposes.

Bubble Sort algorithm loops through an array and compares two adjacent elements. Depending a condition, we determine if we require to switch the elements. In this way it is bubbling up the maximum value to the end of the array.

For each pair, we compare if the first element is greater than the second then the two elements are swapped. Otherwise, we continue with the next pair of elements.

Pseudocode

``````Look at each adjacent pair
If two adjacent elements are not in order
Swap them and set swap counter to falsy value
``````

Time complexity

Bubble sort is not an ideal sorting algorithm. From the pseudocode, we see that we have to compare pairs. This leads us to think we will have one nested loop! A nested loop makes our time complexity O(n²).

In the best-case scenario, the array is already sorted. With a small optimisation in the algorithm, we can reach a best-case of O(n) (if the array is already sorted.).

Implementation

``````const bubbleSort = (arr) => {
if (!arr) return;
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
``````

Optimization

``````const bubbleSort = (arr) => {
let swapped;
for (let i = 0; i < arr.length; i++) {
swapped = false;
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}

if (swapped == false)
break;
}

return arr;
}

``````

Selection Sort

One more algorithm that is used for educational purposes is Selection sort. The selection sort algorithm sorts an array by repeatedly finding the minimum element (or maximum, depending the order) from the unsorted part and putting it at the beginning. In every iteration, the minimum (or maximum) element from the unsorted subarray is picked and moved to the sorted subarray.

Pseudocode

Repeat in the unsorted array:
Search the unsorted data to find the smallest value
Swap the smallest value with the first unsorted element

Time Complexity

This search algorithm compares elements in an array to the first element. When it finds the smaller of the two elements, it swaps it to the first position. The algorithm repeats this pattern until the array is sorted. We can see again that we will need two nested loops to achieve that as we require comparison of pairs. That makes our complexity O(n²).

Implementation

``````
const selectionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}

if (arr[min] < arr[i]) {
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}

return arr;
}

``````

Insertion Sort

Insertion sort is a sorting algorithm that works similar to how you sort playing cards in your hands. Weird eh?

The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Insertion sort is efficient for small data values or almost sorted arrays.

The algorithm is simple. We iterate through the array, we pick an element from the unsorted part and we insert it to the correct place.

Pseudocode

The first element of the array is 'sorted'
Repeat to the unsorted part of the array
Find the position of the next unsorted item
Insert into the 'sorted' position by shifting elements

Time complexity

In worst case the array is sorted with the opposite order. And we have to compare and insert in the appropriate position all the elements. That will be a O(n²).

Implementation

``````
const insertionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
if (arr[i] < arr[0]) {
arr.unshift(arr.splice(i, 1)[0])
} else {

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

}
}

return arr
}

``````

Merge Sort

Merge sort is using the divide and conquer technique. We will have a mergeSort function that partitions the array and a merge function that merge the partitions.

The main algorithm of merge sort divides the input array into two halves and calls itself with the two halves. This recursion continues until we reach granular components that are sorted. Then we proceed with merging these individual pieces into one result array.

Pseudocode

• Find the mid element of the array. mid = Math.floor((array.length)/2)
• Splice the array in left and right parts
• Call merge sort on (left,mid)
• Call merge sort on (mid+1,right)
• Continue until left is less than right
• Then call merge function to perform a merge of the arrays.

Time Complexity

Merge sort is a complicated algorithm. Dividing the algorithm into halves gives us a great time complexity of O(nlogn). We need an auxiliary result array, and this results in a space complexity of O(n)

Implementation

``````
const mergeSort = (arr) => {
if (arr.length === 1) {
return arr;
}

const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle)
const right = arr.slice(middle)

return merge(mergeSort(left), mergeSort(right))
}

const merge = (left, right) => {
let arr = []
// Break out of loop if any one of the array gets empty
while (left.length && right.length) {
if (left[0] < right[0]) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}

return [...arr, ...left, ...right]
}

``````

Quick Sort

QuickSort is a Divide and Conquer sorting algorithm. It's much faster than linear sorting algorithms. Quick-sort is a comparison sorting algorithm, meaning that the sorting occurs by iterating through the array and comparing two defined values to a pivot. This pivot determines how to partition the collection. We have different ways to pick the pivot value, and this can affect the complexity of the algorithm.

Pseudocode

While the collection is unsorted
Pick a pivot
Partition the array
All values smaller than pivot to the left and larger to the right
Perform pivot and partition on the left and the right partition

Time complexity

The performance of this algorithm heavily depends on the pivot. If you always choose the first element as a pivot and we have an already sorted array, the quicksort will try to sort it. Choosing the first element as a pivot will make the call stack really long. This worst-case can reach a complexity of O(n²). The average case though, with a performant pivot is O(nlogn)

``````
const quickSort = (arr, low, high) => {
if (low < high) {
const pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}

return arr;
}

const partition = (arr, low, high) => {

const pivot = arr[high];
let i = (low - 1);

for (let j = low; j <= high - 1; j++) {

// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}

const swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

``````

Other sorting algorithms

Other famous sorting algorithms are:

1. Heap Sort

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort algorithm where we first find the minimum element and place it at the beginning. We repeat the same process for the remaining elements. Time complexity: O(N log N).

1. Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects that are having distinct key-values. Then do arithmetic to calculate the position of each object in the output sequence. Time complexity: O(n)