Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
Data structure and Algorithms are one of the most important topics to understand. In this blog, we will take a quick look at the problem statement and discuss how to Sort an Array with and without inbuilt methods and then discuss its complexities.
Problem Statement
We are given an array of numbers and we need to arrange them in ascending order i.e., a smaller number followed by a higher number.
Sample Examples
Example
Input
Array
Output
Explanation: The sorted array in the ascending order would be: 0, 1, 2, 3, 4
Approach Using Inbuilt method
In this approach, we will sort an array using inbuilt methods available in javascript.
We are provided with an inbuilt sort() function in javascript. It makes our work easier just by calling the function and the number then gets arranged in ascending order and we print the result.
It’s quite easy to use the inbuilt sort function right? But What if in some scenario you are not allowed to use the inbuilt method to sort the array? In that case, you have to write the sorting algorithm by yourself. We have plenty of Sorting algorithms available like the bubble sort, insertion sort, selection sort, and many more. Also, the sort method available in many programming languages uses one of these sorting algorithms under the hood. So, Let’s discuss them one by one.
Bubble sort
Bubble sort is one of the most straightforward sorting algorithms that involve repeatedly swapping adjacent elements for the correct order.
We traverse the whole array checking whether the next element from the current index is greater or not. If it is greater than the current element we swap both of the elements. We keep on repeating this process until our array is sorted.
Algorithm
BubbleSort(arr)
for i->0 to arr.size():
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
Implementation in JavaScript
arr = [5, 2, 7, 1, 0]
function bubbleSort(arr){
for (let i = 0; i < arr.length - 1; i++){
let swapped = false
for (let j = 0; j < arr.length - i - 1; j++){
// swapping the elements
if (arr[j] > arr[j+1]){
let temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
swapped = true
}
}
// if no elements are swapped
// that means our array is sorted
if(!swapped) break;
}
return arr
}
console.log("Before sorting: ", arr)
console.log("After sorting: ", bubbleSort(arr))
You can also try this code with Online Javascript Compiler
The selection sort method sorts an array by repeatedly selecting the smallest element from the unsorted portion and inserting it at the beginning. In a given array, the method maintains two subarrays.
Already sorted.
Not sorted subarray.
Every time a selection sort is performed, the smallest element from the unsorted subarray is chosen and moved to the sorted subarray.
Algorithm
selectionSort(arr):
for i <- 0 to arr.length - 1:
minIndex <- i
for j <- i+1 to arr.length:
if arr[minIndex] > arr[j]:
minIndex <- j
end if
end for
swap(arr[minIndex], arr[i])
end for
return arr
Implementation in JavaScript
arr = [5, 2, 7, 1, 0]
function selectionSort(arr) {
for (let i = 0; i < arr.length-1; i++){
// Finding the minimum element
let minIndex = i;
for (let j = i + 1; j < arr.length; j++){
if (arr[j] < arr[minIndex]) minIndex = j;
}
// Swapping the minimum element with the first element
let temp = arr[minIndex]
arr[minIndex] = arr[i]
arr[i] = temp
}
return arr
}
console.log("Before sorting: ", arr)
console.log("After sorting: ", selectionSort(arr))
You can also try this code with Online Javascript Compiler
The straightforward sorting algorithm known as insertion sort functions similarly to how you would arrange playing cards in your hands. In a sense, the array is divided into sorted and unsorted parts. Values are chosen and assigned to the appropriate positions in the sorted part of the array from the unsorted part.
Algorithm
insertionSort(arr):
for i <- 1 to arr.length:
key <- arr[i]
j <- i - 1
while j >= 0 and arr[j] < key:
arr[j+1] <- arr[j]
j = j+1
end while
arr[j+1] <- key
end for
return arr
Implementation in JavaScript
arr = [5, 2, 7, 1, 0];
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
// Moving elements of arr[0..i-1], that are
// greater than key, to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
return arr
}
console.log("Before sorting: ", arr);
console.log("After sorting: ", insertionSort(arr));
You can also try this code with Online Javascript Compiler
Which sorting algorithm does the javascript sort function use?
The sorting function varies from engine to engine. Mostly, it uses quicksort or insertion sort.
Is javascript sort() fast?
Yes, the javascript sort function is faster. It takes the most suitable path to sort the array.
Why is sorting required?
The sorted array makes the work done faster and in a much easier way. By default, the array gets sorted in ascending order.
Conclusion
In this article, we have extensively discussed a coding problem on how to Sort an Array with and without inbuilt methods and then discussed its complexities.