Sorting techniques in JavaScript

In the previous article, we have already discussed the searching techniques in the JavaScript. If you want to learn the searching techniques in JavaScript, please read my medium story: Searching techniques in JavaScript. Now in this story, we discussed the sorting techniques in the JavaScript. There are several sorting techniques in JavaScript like insertion sorting, selection sorting, bubble sorting etc.

Selection Sort :

The selection sort is the type of sorting algorithm in the programming. It is the simplest type of sorting algorithm that’s why it is used for sort the small list. It takes O( n² ) time complexity, so if you use this sorting for the large list, it takes too much time and it is not suitable for the large list.

How it’s work :

1. Selection sort divides the list into two parts: sorted sub-list and unsorted sub-list.
2. Sorted sub-list is empty in the starting time and unsorted list takes all elements of the list.
3. We take the left-most item as the smallest item and compare with each item of the list and put them in sorted sub-list and removed from the unsorted list(it is called swapping technique).
4. We repeat step-3 until the whole list is sorted and every item is in sorted sub-list in sorting format and unsorted sub-list is empty.

Example :

Sorted sub-list : []
Unsorted sub-list : [5, 7, 11, 15, 3 ,1 , 2, 10]
Smallest element in unsorted sub-list : 1
================================================
Sorted sub-list : [1]
Unsorted sub-list : [5, 7, 11, 15, 3 , 2, 10]
Smallest element in unsorted sub-list : 2
=============================================
Sorted sub-list : [1, 2 ]
Unsorted sub-list : [5, 7, 11, 15, 3 , 10]
Smallest element in unsorted sub-list : 3
==========================================
Sorted sub-list : [1, 2, 3]
Unsorted sub-list : [5, 7, 11, 15, 10]
Smallest element in unsorted sub-list : 5
=========================================
Sorted sub-list : [1, 2, 3, 5]
Unsorted sub-list : [7, 11, 15, 10]
Smallest element in unsorted sub-list : 7
=========================================
Sorted sub-list : [1, 2, 3, 5, 7]
Unsorted sub-list : [11, 15, 10]
Smallest element in unsorted sub-list : 10
==========================================
Sorted sub-list : [1, 2, 3, 5, 7, 10]
Unsorted sub-list : [11, 15]
Smallest element in unsorted sub-list : 11
==========================================
Sorted sub-list : [1, 2, 3, 5, 7, 10, 11]
Unsorted sub-list : [15]
Smallest element in unsorted sub-list : 15
==========================================
Sorted sub-list : [1, 2, 3, 5, 7, 10, 11, 15]
Unsorted sub-list : []

Algorithm:

Step 1 - Create two sub lists from given list. One is sorted which is empty at the starting and another is unsorted which having all the items of the list.
Step 2 - In every iteration we picked up the smallest element of the list from left to right side and added into sorted sub-list and removed unsorted-list.
Step 3 - Runs the step 2 until the whole list becomes the sorted list.

Code snippet:

Selection Sorting

Performance Analysis :

worst-case performance -- O(n²)
best-case performance -- O(n²)
average-case performance -- O(n²)

Insertion Sort :

Insertion sorting is another type of basic sorting in computer science and programming. It takes one item from unsorted input list in every iteration and finds the place of that item in the sorted list, find the index of that item in the sorted array and put that item in the sorted list. It repeats that process until no items remain in the unsorted input list. This sorting technique is good for small list or array, but if your unsorted list is big and you want to sort that, this technique takes O(n²) time. The time complexity of this technique is O(n²). On the other hand, it has several advantages also:

1. It is the simplest sorting technique.
2. It is a very fast technique for small data list or array.
3. More efficient than other quadratic sorting algorithms like selection sort and bubble sort.

How it’s work :

1. Insertion sort takes unsorted input list and takes starting 2 input data.
2. Compare both inputs from each other
3. If the second input is smaller than first swap the values. After that, we take third input and compare that with starting 2 sorted elements. If the third element is smaller than both so place that input in arr[0], otherwise no action needed.
4. We repeat step-3 until whole no item remains in the unsorted input list.

Example :

Sorted sub-list : []
Unsorted sub-list : [5, 7, 11, 15, 3 ,1 , 2, 10]
Smallest element in unsorted sub-list : 5,7
================================================
Sorted sub-list : [5,7]
Unsorted sub-list : [11, 15, 3 ,1 , 2, 10]
Smallest element in unsorted sub-list : 11
================================================
Sorted sub-list : [5, 7, 11]
Unsorted sub-list : [15, 3 ,1 , 2, 10]
Smallest element in unsorted sub-list : 15
===============================================
Sorted sub-list : [5, 7, 11, 15]
Unsorted sub-list : [3 ,1 , 2, 10]
Smallest element in unsorted sub-list : 3
================================================
Sorted sub-list : [3, 5, 7, 11, 15]
Unsorted sub-list : [1 , 2, 10]
Smallest element in unsorted sub-list : 1
================================================
Sorted sub-list : [1, 3, 5, 7, 11, 15]
Unsorted sub-list : [2, 10]
Smallest element in unsorted sub-list : 2
===============================================
Sorted sub-list : [1, 2, 3, 5, 7, 11, 15]
Unsorted sub-list : [10]
Smallest element in unsorted sub-list : 10
================================================
Sorted sub-list : [1, 2, 3, 5, 7, 10, 11, 15]
Unsorted sub-list : [] 
================================================

Algorithm:

Step 1 - Take first two input data from unsorted list
Step 2 - Compare with each other. If A[0]> A[1], then swap each other otherwise no action needed
Step 3 - After that we take third input and compare with each element in the sorted list and place in appropriate sorted place.
Step 4- Runs the same procedure until no item remains in the unsorted input list.

Code snippet:

Insertion Sorting

Performance Analysis :

worst-case performance -- O(n²)
best-case performance -- O(n)
average-case performance -- O(n²)

Bubble Sort :

Bubble sort is also known as sinking sort. In this type of sorting, compare each pair of adjacent items and swap them if they are not in the sort order. This process is called PASS. The PASS is repeated through the list until there is no swapping is needed in the list and after that list is sorted. This technique of sorting is very slow and impractical and used only when the most of the items of the list are sorted and some of the items are in the wrong place.

How it’s work :

1. In the bubble sort, we compare the adjacent items and if they are in the wrong place then swap it.
2. When this swapping process covers one loop. It is called PASS
3. We repeat the PASS through the list until there is no swapping is needed.

Example :

First Pass
===========
[5, 7, 11, 15, 3 ,1 , 2, 10] ==> [5, 7, 11, 15, 3 ,1 , 2, 10]
[5, 7, 11, 15, 3 ,1 , 2, 10] ==> [5, 7, 11, 15, 3 ,1 , 2, 10]
[5, 7, 11, 15, 3 ,1 , 2, 10] ==> [5, 7, 11, 15, 3 ,1 , 2, 10]
[5, 7, 11, 15, 3 ,1 , 2, 10] ==> [5, 7, 11, 3, 15, 1 , 2, 10]
[5, 7, 11, 3, 15 ,1 , 2, 10] ==> [5, 7, 11, 3, 1, 15 , 2, 10]
[5, 7, 11, 3, 1 ,15 , 2, 10] ==> [5, 7, 11, 3, 1, 2 , 15, 10]
[5, 7, 11, 3, 1 ,2 , 15, 10] ==> [5, 7, 11, 3, 1, 2 , 10, 15]
=============================================================
Second Pass
===========
[5, 7, 11, 3, 1, 2 , 10, 15] ==> [5, 7, 11, 3, 1, 2 , 10, 15]
[5, 7, 11, 3, 1, 2 , 10, 15] ==> [5, 7, 11, 3, 1, 2 , 10, 15]
[5, 7, 11, 3, 1, 2 , 10, 15] ==> [5, 7, 3, 11, 1, 2 , 10, 15]
[5, 7, 3, 11, 1, 2 , 10, 15] ==> [5, 7, 3, 1, 11, 2 , 10, 15]
[5, 7, 3, 1, 11, 2 , 10, 15] ==> [5, 7, 3, 1, 2, 11 , 10, 15]
[5, 7, 3, 1, 2, 11 , 10, 15] ==> [5, 7, 3, 1, 2, 10 , 11, 15]
[5, 7, 3, 1, 2, 10 , 11, 15] ==> [5, 7, 3, 1, 2, 10 , 11, 15]
=============================================================
Third Pass
==========
[5, 7, 3, 1, 2, 10 , 11, 15] ==> [5, 7, 3, 1, 2, 10 , 11, 15]
[5, 7, 3, 1, 2, 10 , 11, 15] ==> [5, 3, 7, 1, 2, 10 , 11, 15]
[5, 3, 7, 1, 2, 10 , 11, 15] ==> [5, 3, 1, 7, 2, 10 , 11, 15]
[5, 3, 1, 7, 2, 10 , 11, 15] ==> [5, 3, 1, 2, 7, 10 , 11, 15]
[5, 3, 1, 2, 7, 10 , 11, 15] ==> [5, 3, 1, 2, 7, 10 , 11, 15]
[5, 3, 1, 2, 7, 10 , 11, 15] ==> [5, 3, 1, 2, 7, 10 , 11, 15]
[5, 3, 1, 2, 7, 10 , 11, 15] ==> [5, 3, 1, 2, 7, 10 , 11, 15]
=============================================================
Fourth Pass
===========
[5, 3, 1, 2, 7, 10 , 11, 15] ==> [3, 5, 1, 2, 7, 10 , 11, 15]
[3, 5, 1, 2, 7, 10 , 11, 15] ==> [3, 1, 5, 2, 7, 10 , 11, 15]
[3, 1, 5, 2, 7, 10 , 11, 15] ==> [3, 1, 2, 5, 7, 10 , 11, 15]
[3, 1, 2, 5, 7, 10 , 11, 15] ==> [3, 1, 2, 5, 7, 10 , 11, 15]
[3, 1, 2, 5, 7, 10 , 11, 15] ==> [3, 1, 2, 5, 7, 10 , 11, 15]
[3, 1, 2, 5, 7, 10 , 11, 15] ==> [3, 1, 2, 5, 7, 10 , 11, 15]
[3, 1, 2, 5, 7, 10 , 11, 15] ==> [3, 1, 2, 5, 7, 10 , 11, 15]
=============================================================
Fifth Pass
==========
[3, 1, 2, 5, 7, 10 , 11, 15] ==> [1, 3, 2, 5, 7, 10 , 11, 15]
[1, 3, 2, 5, 7, 10 , 11, 15] ==> [1, 2, 3, 5, 7, 10 , 11, 15]

Algorithm:

Step 1 - Take adjacent items of the list and compare them. Swap them if they are in wrong position.
Step 2 - When you complete all the adjacent comparison. It complete one PASS.
Step 3 - We repeat the PASS until there is no swapping is needed.

Code snippet:

Bubble Sorting

Performance Analysis :

worst-case performance -- O(n²)
best-case performance -- O(n)
average-case performance -- O(n²)

Conclusion:

This article covers the basic sorting techniques in the JavaScript. If you have any doubts and want to take any help from me please mail me to vsvaibhav2016@gmail.com.