Sorting is the process of ordering or arranging a given collection of elements in some particular order. We can sort a collection of numbers in ascending (increasing) or descending (decreasing) order. If the collection is of string, we can sort it in alphabetical order (a-z or z-a) or according to the length of the string.

Before moving forward let’s briefely understand what in-place and out-of-place algorithms are.

All algorithms can be classified into in-place and out-of-place based on the amount of extra space used.

In-place Algorithms:

These algorithms transform input without using any extra space. The input is overwritten by the output and no extra space is used.
It may require a small amount of memory for its operations. However, the amount of memory required is independent of the size of the input and its constant.

Out-of-place Algorithms:

Unlike in-place algorithms, the extra space used by out-of-place algorithms depends on the size of the input.

So coming back to sorting….

Sorting Algorithms can also be classified as in-place or out-of-place algorithms.

In-place Sorting:

In-place sorting algorithms use constant space for producing output.
It sorts the array only by modifying the order of the elements within the array.
Examples: insertion sort and selection sort (they don't use any additional space for sorting the array).

Out-of-place Sorting:

The auxiliary space complexity of these sorting algs is increased by O(n) where n is the number of elements on which the sorting has to be applied.
Example: merge sort.

Few more sorting concepts before starting algorithms

Types of sorting:

Internal Sorting:

All the data that is to be sorted is placed in the main memory or internal memory all the time while sorting is in progress.
Input beyond a certain size is not acceptable.
Example: bubble sort, selection sort and insertion sort

External Sorting:

All data is stored outside memory (like on disk) and only loaded into memory in small chunks.
It is used for a massive amount of data. In cases when data can’t fit into memory entirely.
Example: Merge sort (mostly merge sort and its variations are used for external sorting)

Sort Stability:

Stable Sorting:

When two same values appear in the same order in the sorted array without changing their positions.
Example: merge sort, insertion sort, bubble sort.

2. Unstable Sorting:

When two values appear in different orders in the sorted array.
Example: quick sort, shell sort.

Let’s learn sorting algorithms

Bubble Sort:

It is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
Every iteration through each element of a list is called a pass. For a list with n elements, the bubble sort makes a total of n - 1 pass to sort the list.
To arrange elements in ascending order, the largest element is identified after each pass and placed at the correct position in the list.
This sorted element is not considered in the remaining passes and thus the list of elements gets reduced in successive passes.

Note: After each pass, the largest element is identified and placed in the correct position. This can be considered as the largest element being ‘bubbled up’. Hence the name Bubble Sort.

Algorithm:

Start looping the array with a variable called i from the beginning of the array till i < array.length
Start an inner loop with a variable called j from the beginning of the array until j < array.length - i - 1 (since the last i elements are already sorted)
If array[j] > array[j+1] swap them
Return the sorted array

// ES6 Arrow Function

// swap function
const swap = (arr, i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}

// Bubble Sort
const bubbleSort = arr => {
    let n = arr.length;
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n-i - 1; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
            }
        }
    }

    return arr;
}

// const testArray = [2, 8, 1, 3, 6, 7, 5, 4];
// bubbleSort(testArray);
// output => [1, 2, 3, 4, 5, 6, 7, 8]

Optimized Bubble Sort

The above function always runs O(n²) time even if the array is sorted.
It can be optimized by stopping the algorithm if the inner loop didn’t cause any swap.

// ES6 Arrow Function

// swap function
const swap = (arr, i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}

// Optimized Bubble Sort
const bubbleSort = arr => {
    let n = arr.length;
    let swapped;
    for(let i = 0; i < n-1; i++) {
        swapped = false;
        for(let j = 0; j < n-i - 1; j++) {
            swap(arr, j, j+1);
            swapped = true;
        }

        if(swapped === false) {
            break;
        }
    }
    return arr;
}

// const testArray = [2, 8, 1, 3, 6, 7, 5, 4];
// bubbleSort(testArray);
// output => [1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity:

Average and Worst Cases: O(N²)
Best Case: O(N)
Note 1: Worst case occurs when the array is reverse sorted.
Note 2: Best case is when the array is sorted

Space Complexity: O(1)

Key Points:

Bubble sort is an in-place sorting algorithm.
It is a stable algorithm.
It is not used for large data sets because its average and worst time complexity is quite high.

It sorts the array from the end.

Selection Sort:

It is another sorting technique in which an array is sorted by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.
It maintains two subarrays- The sorted subarray, Remaining Unsorted subarray.
To sort an array of n elements in ascending order, all the elements in the unsorted array are traversed to find the smallest element.
The smallest element is then swapped with the leftmost element of the unsorted array. This element occupies the first position in the sorted array, and it is not considered in further passes.
In the second pass, the next smallest element is selected from the remaining elements in the unsorted array and swapped with the leftmost element of the unsorted array.
This element occupies the second position in the sorted array, and the unsorted array reduces by one element for the third pass.
This process continues until n-1 smallest elements are found and moved to their respective places. The nth element is the last, and it is already in place.

Note: To sort a list having n elements, the selection sort makes (n-1) number of passes through the list.

Algorithm:

Store the first element of the array as the smallest element so far.
Compare this item to the next element in the array until you find a smaller number.
If a smaller number is found, change the minimum to the new smaller number and continue till the end of the array.
If the minimum is not the value (index) that you initially began with then swap them.
Repeat these steps until the array is sorted.

// ES6 Arrow Function

// swap function
const swap = (arr, i, j) => [arr[i], arr[j]] = [arr[j], arr[i]]

// Selection Sort
const selectionSort = (arr) => {
    let minIdx;
    for(let i = 0; i<arr.length-1; i++) {
        minIdx = i;
        for(let j = i+1; j < arr.length; j++) {
            if(arr[minIdx] > arr[j]) minIdx = j;
        }
        swap(arr, minIdx, i);
    }

    return arr;
}

// const testArray = [2, 8, 1, 3, 6, 7, 5, 4];
// selectionSort(testArray);
// output => [1, 2, 3, 4, 5, 6, 7, 8]

Stable Selection Sort

// ES6 Arrow Function

// swap function
const swap = (arr, i, j) => [arr[i], arr[j]] = [arr[j], arr[i]]

// Selection Sort
const stableSelectionSort = arr => {
    for(let i = 0; i<arr.length - 1; i++) {
        let min = i;
        for(let j = i+1; j < arr.length; j++) {
            if(arr[min] > arr[j]) min = j;
        }

        let key = arr[min];
        while(min > i) {
            arr[min] = arr[min - 1];
            min--;
        }

        arr[i] = key;
    }

    return arr;
}

// const testArray = [2, 8, 1, 3, 6, 7, 5, 4];
// stableSelectionSort(testArray);
// output => [1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity:

O(N²)
Note 1: Worst case occurs when the array is reverse sorted.
Note 2: Best case is when the array is sorted

Space Complexity: O(1)

Key Points:

Selection sort is an in-place algorithm.
The default implementation is not stable (but can be made stable with minor modifications).
It can be useful when the memory writes is a costly operation.
Selection sort never makes more than O(N) swaps (minimum among other sorting algs).

Sorts the array from the beginning.

Insertion Sort:

This is another simple sorting algorithm where the array is split into two parts sorted and unsorted.
Each element in the unsorted array is considered one by one and is inserted into the sorted array at its appropriate position.
In each pass, the sorted list is traversed from the backward direction to find the position where the unsorted element could be inserted. Hence the sorting method is called insertion sort.

Algorithm:

Start by picking the second element in the array.
Now compare the second element with the one before and swap if necessary.
Continue to the next element and if it is in the incorrect order, iterate through the sorted portion to place the element in the correct place.
Repeat until the array is sorted.

// ES6 Arrow Function

// swap function
const swap = (arr, i, j) => [arr[i], arr[j]] = [arr[j], arr[i]]

// Insertion Sort
const insertionSort = arr => {
    for(let i = 1; i<arr.length; i++) {
        let key = arr[i];
        let j = i-1;

        while(j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
  return arr;
}


// const testArray = [2, 8, 1, 3, 6, 7, 5, 4];
// insertionSort(testArray);
// output => [1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity:

Average and Worst Cases: O(N²)
Best Case: O(N)
Note 1: Best case is when the array is sorted or almost sorted.

Space Complexity: O(1)

Key Points:

Insertion sort is an in-place algorithm.
It is a stable algorithm.
It's most efficient for small data sets.
Most efficient algorithm among other quadratic algs (O(N²)) like selection sort or bubble sort.
Useful when the input is almost sorted or only a few numbers are misplaced in the array. It takes linear time in such cases (O(N)).

Note:

This is the end of Part 1. I will continue this article here.

References:

Sorting Algorithms in JavaScript

Part 1

Bubble Sort:

Selection Sort:

Insertion Sort: