Sorting Algorithms Explained With Examples In JavaScript | DroidTechKnow

Sorting is the fundamental algorithm in computer science to arrange(ascending or descending) the data elements in the list. It is also one of the most common algorithms that computers performed on data. In this tutorial, we will try to explain some basic as well as advanced sorting algorithms. We will start with the native sorting algorithms and then explore efficient sorting algorithms with their time and space complexity.

Why Sorting Algorithms are necessary?

There are lots of advantages if you keep your data in the sorted form in the database.

• For faster searching of elements in the database.

• Remove the code complexity for data retrieval.

Types Of Sorting Algorithms

There are mainly two types of sorting algorithms.

1. Comparison-based sorting algorithms: In this type of sorting algorithm, we need to compare the elements in order to sort the elements.

2. Linear sorting algorithms: In this type of algorithm, we use some techniques other than comparing the elements to sort the list.

Comparison-based Sorting Algorithms

1. Bubble Sort

Bubble sort is one of the simplest algorithms for sorting the array in ascending or descending form. It iterates the array elements from 1st element to last and swaps every consecutive pair of elements if they are not in the correct order.

Algorithm

1. Repeat Step 2 For i = 0 to N-1

2. Repeat For J = i + 1 to N – I

3. IF A[J] > A[i]
   SWAP A[J] and A[i]
   [END OF INNER LOOP]
   [END OF OUTER LOOP

4. EXIT

Complexity

Worst Case Time complexity: O(N2)

Worst Case Space complexity: O(1)

JavaScript Code Implementation

2. Selection Sort

This algorithm repeatedlyfinds the smallest element in the unordered list and places it in the appropriate position.

Algorithm

1. Repeat Step 2 and 3 For i = 0 to N-1

2. Select the smallest element(MinIndex)

3. Repeat For J = i + 1 to N – I

4. IF A[J]< A[MinIndex]
   SWAP A[J] and A[MinIndex]
   [END OF INNER LOOP]
   [END OF OUTER LOOP

5. EXIT

Complexity

Worst Case Time complexity: O(N2)

Worst Case Space complexity: O(1)

JavaScript Code Implementation

3. Insertion Sort

Insertion sort selects an element and places it in the correct position. In this sort, we first choose the key element usually 0th element(keyIndex) and compare it with all elements from keyIndex to 0.

Algorithm

1. Repeat steps 2 and 3 For i = 0 to N-1

2. Select key index starting from 0.

3. Repeat For J = i – 1 to i

4. IF A[J] > A[key]
   SWAP A[J] and A[key]
   key = i
   [END OF INNER LOOP]
   [END OF OUTER LOOP

5. EXIT

JavaScript Code Implementation

Complexity

Worst Case Time complexity: O(N2)

Worst Case Space complexity: O(1)

4. Shell Sort

Shell sort is thegeneralization of insertion sort. In the insertion sort, consecutive elements are compared to get the sorted list but in the shell sort, wecomparing elements separated by a gap of several positions. The gap between the elements gradually decreases based on the sequence that we are using.

Shellsort’s key concept is that it compares distant elements first rather than adjacent elements unlike insertion sort.

Some optimal sequences for Sheel Sort

• Shell’s original sequence: N/2, N/4, ... 1

• Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1

• Knuth’s increments:1, 4, 13, …, (3k– 1) / 2

JavaScript Code

Complexity

Worst Case Time complexity: O(N2)

Worst Case Space complexity: O(1)

5. Quicksort

Suppose there are lots of students in a class and the teacher wants to arrange them according to their height. So there are 2 methods to arrange them in increasing order of height.

1. The teacher arranges them one by one.

2. The teacher asks students to arrange themself.

The second way is more efficient and faster which is the idea behind the Quicksort algorithm.

Quicksort is based on a divide and conquer algorithm where an array is divided on the basis of pivot element such that all the elements less than pivot element are on the left side and all the elements greater than pivot element are on the right side.

Algorithm

1. First, we have to choose a pivot element(Usually the first element is used).

2. Split the array into two part – the left part which contains all the elements which are less than pivot element and the right part which contains all the elements greater than the pivot. Or we can say that place the pivot element at the correct position and return it.

3. Recursively repeat the algorithm for both the halves.

JavaScript Code

Complexity

Worst Case Time complexity: O(N2)

Worst Case Space complexity: O(1)

6. Merge sort

Merge sort is another perfect example of a divide and conquer algorithm where we split the array into a single-element array and merge them using two-way merging method to find the ordered list.

Algorithm

1. Divide the array list into the smaller lists until we got the single element in the array. Let us say the last divided array into two subarrays called left array and right array.

2. Compare each element of the left array to the right array and prepare a third array which having the sorted elements.

3. Repeat until all the subarray is merged into one array.

Complexity

Worst Case Time complexity: O(N*Log(N))

Worst Case Space complexity: O(N)

JavaScript Code

Linear Sorting Algorithms

1. Counting sort

The counting sort algorithm is a linear sorting algorithm that works by counting the occurrence of unique elements in the array.

Algorithm

1. Find the minimum and maximum elements in the array.

2. Create a countArray that stores the count of each element.

3. Iterate over the countArray and find the non-negative integers. Push the index of a non-negative integer into the resultarray and decrease the value by 1 until it becomes 0.

Complexity

Worst Case Time complexity: O(N + K)

Worst Case Space complexity: O(K)

JavaScript Code

2. Bucket sort

Bucket sort is a linear sorting algorithm that first divides the elements into groups called buckets. Then each bucket elements are sorted using any sorting algorithm.

Algorithm

1. Find the maximum number in the given array and how many digits in this maximum number.

2. Create a 2D array(Buckets) index from 0 to 10.

3. Insert elements into the buckets according to the range of the bucket. As we find how many digits are present in the maximum number. Suppose there are 2 digits are there. So we need to insert the elements into the bucket on the basis of Ten’s place of the number.

4. Sort Each bucket element internally and remove them to make the array sorted.

Complexity

Worst Case Time complexity: O(N2)

Worst Case Space complexity: O(n + k)

JavaScript Code

3. Radix sort

Bucket sort is a linear sorting algorithm that first divides the elements into groups called buckets. Then each bucket elements are sorted using any sorting algorithm.

Algorithm

1. Find the maximum number in the given array and how many digits in this maximum number.

2. Create a 2D array(Buckets) index from 0 to 10.

3. From 0 to Number of digits in maximum number.Suppose there are 2 digits in the maximum number then there will be 2 passes in the radix sort

   • Insert the elements into the bucket on the basis of Ten’s place of the numbers. Remove all the elements and form a new array.

   • Insert the elements into the bucket on the basis of One’s place of the numbers.

Complexity

Worst Case Time complexity: O(nd) -> d is a number of passes.

Worst Case Space complexity: O(N)

JavaScript Code

Time complexity Comparison Of Different Sorting Algorithms

Algorithm	Average case complexity	Worst-case complexity
Bubble Sort	O(N2)	O(N2)
Selection Sort	O(N2)	O(N2)
Insertion Sort	O(N2)	O(N2)
Shell Sort	O(n*log n)	O(N2)
Quicksort	O(n*log n)	O(N2)
Merge Sort	O(n*log n)	O(n*log n)
Counting Sort	O(n + k)	O(n2)
Bucket Sort	O(n2)	O(n+k)
Radix Sort	O(dn)	O(dn)

Find the complete source code on Github

Happy Sorting!

Next Article: Introduction To Searching Algorithms - Linear Search | Binary Search