Sorting Algorithms

Overview

Sorted array is an array that has its elements in some particular order. This may be an array of numbers [1,2,3,..], characters [a,b,c,..], words [aaa,abb,abc,..],... Examples in this article will sort array in ascending order.

Insertion sort

1. STEP 1: Start at array index i = 1.
2. STEP 2: Iterate from current index i until where previous element is larger than current or until index doesn't equal i = 0
3. STEP 3: Swap where previous element is larger than current.
4. STEP 4: Increment current index i++, and repeat from STEP 2.

                    
// step 1
for (let i = 1; i < array.length; i++) {
    let j = i;
    // step 2
    while (j >= 0 && array[j - 1] > array[j]) {
        // step 3
        let s = array[j - 1];
        array[j - 1] = array[j];
        array[j] = s;
        j--;
    }
}
                

Selection sort

1. STEP 1: Start at array index i = 0.
2. STEP 2: Iterate from current index i to the end of array.
3. STEP 3: If smallest element found - save its index.
4. STEP 4: Swap current element at array[i] with smallest element in array at array[k].
5. STEP 5: Increment current index i++, and repeat from STEP 2.

                    
// step 1
for (let i = 0; i < array.length - 1; i++) {
    let k = i;
    // step 2
    for (let j = i; j < array.length; j++) {
        // step 3
        if (array[j] < array[i]) {
            k = j;
        }
    }
    // step 4
    let current = array[i];
    array[i] = array[k];
    array[k] = current;
}
                

Bubble sort

1. STEP 1: Keep track if any elements were swapped in the last iteration.
2. STEP 2: Iterate from start i = 1 to the end of array i = array.length.
3. STEP 3: If current element smaller than previous element, swap these two elements. Mark that you have performed a swap in this iteration.
4. STEP 4: Repeat from STEP 2

                    
// step 1
let swapped = true;
while (swapped) {
    swapped = false;
    // step 2
    for (let i = 1; i < array.length; i++) {
          // step 3
          if (array[i] < array[i - 1]) {
                let element = array[i];
                array[i] = array[i - 1];
                array[i - 1] = element;
                swapped = true;
          }
    }
}