fzn0x

Opening#

Hello, this time I will explain two simple sorting algorithms, namely Insertion Sort and Selection Sort.

But before that, I will explain what sorting algorithms are and why you need to know about them.

Content#

Sorting Algorithms#

Sorting Algorithms are algorithms to arrange elements in a specific order, which can be ascending (from smallest to largest), descending (from largest to smallest), or random.

Why do you need to know about these algorithms? These algorithms help determine the distance from nearest to farthest, alphabetical order from smallest to largest, and numerical order from smallest to largest.

For JavaScript programmers like me, we might rarely use these algorithms because JavaScript provides a built-in method sort(). However, did you know that some JavaScript engines that build the built-in sort() method use different sorting algorithms? For example:

You can see the history of sorting algorithm implementations in one of the engines, namely V8, in the sort() method here.

For this reason, I decided to use JavaScript as an example of implementing these algorithms. I initially planned to use C++, but because I wanted to talk about this built-in method algorithm, so why not? I said.

Now I will explain the two simple sorting algorithms below.

Insertion Sort#

Insertion Sort is an insertion method that builds the final array by sorting each value one by one.

The formula used for insertion sort is:

O(n + j), where j is the value of inversions#

The for loop starts from the first index, with the insertion sort check starting in reverse from before the index arr[n] and so on until index zero.

For checking in JavaScript, I use a while loop inside a for loop for each index before index arr[n], starting in reverse with the auxiliary variable j containing n - 1.

The while loop inside the for loop here checks whether the auxiliary variable has a result or not from j >= 0 and arr[j] > arr[n], if so, then the value of arr[j + 1] is replaced with arr[j] and continue the checking process inside the while loop inside that for loop while decreasing the value of j by 1, if not, then nothing changes from the array value (arr[n]).

If simplified:

1. array with index having a loop value (arr[n]).
2. checking starts from the index before arr[n].
3. n is the value of the for loop.
4. the while loop inside the for loop ends at arr[arr.length - 1].
5. auxiliary variable j containing n - 1.
6. value checking starts in reverse from the index before arr[n] to index zero in the while loop inside the for loop.

Once the for loop iteration is completed, the final result of array restructuring in this insertion sort algorithm is obtained.

Example code you can study:

function insertionSort(arr){
    for(n = 1; n < arr.length; n++){
        let current = arr[n];
        let j = n - 1;

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

    return arr;
}

let sortedArray = insertionSort([5,13,4,7,8]);
console.log(sortedArray);

Selection Sort#

Selection Sort is a sorting method by arranging values in an array from smallest to largest or vice versa.

The formula used for selection sort is:

О (n^2)#

The for loop starts from index zero, with the selection sort check starting sequentially from index arr[n] and so on until the last index.

For checking in JavaScript, I use a for loop inside another for loop for each index after index arr[n], starting sequentially with the auxiliary variable min containing n.

The for loop inside another for loop here checks whether the auxiliary variable min has a result greater than the value of arr[n + 1] or not, if so, then the value of arr[min] and min are replaced with that value, if not, then nothing changes from the array value (arr[min]).

If simplified:

1. array with index having a loop value (arr[n]).
2. checking starts from index zero.
3. n is the value of the for loop.
4. the for loop ends at arr[arr.length - 1].
5. auxiliary variable min containing n.
6. value checking starts from arr[n + 1] to the last index in the for loop inside another for loop.

Example code you can study:

function selectionSort(arr) { 
    for(let n = 0; n < arr.length; n++) {
        let min = n;

        for(let j = n+1; j < arr.length; j++){
            if(arr[j] < arr[min]) {
                min=j; 
            }
        }

        if (min !== n) {
            let current = arr[n]; 
            arr[n] = arr[min];
            arr[min] = current;      
        }
    }

    return arr;
}

let sortedArray = selectionSort([5,13,4,7,8]);
console.log(sortedArray);

Conclusion#

That's all the writing I can share, hopefully it's useful.

References for this writing:

• Wikipedia
• StackAbuse