Hello friends, in this article we will learn about the basics of sorting. Sorting means arranging data in a specific manner, such as ascending or descending. For sorting, we have many pre-defined algorithms like Bubble sort, Selection Sort, Merge Sort and Quick Sort. In this tutorial, we will learn all these basic sorting techniques in Javascript.
1. Bubble sort
Suppose you want to start the journey of learning the sorting algorithm. Bubble sort will be the first algorithm because its mirrors our brain for sorting by comparing.
We can understand the bubble sort in these basic four steps
- In array, it starts with the first element. It compares the current element with the next element in the array.
- If the starting element is greater than the following element in the array. It swaps the position of both numbers.
- Suppose the current element is smaller than the following number. It just moves to the following number.
- Just start from the first step.
Let see our first approach
function bubbleSort(inputArr){
let len = inputArr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (inputArr[j] > inputArr[j + 1]) {
let tmp = inputArr[j];
inputArr[j] = inputArr[j + 1];
inputArr[j + 1] = tmp;
}
}
}
return inputArr;
}
Our Second Approach
function bubbleSortArr(inputArr) {
let isSortedArray = false;
let counter = 0;
while(!isSortedArray){
isSortedArray = true;
for( let i = 0; i < inputArr.length - 1 - counter; i++){
if(inputArr[i] > inputArr[i + 1]){
swapElement(i, i+1, inputArr);
isSortedArray = false;
}
}
counter++
}
return inputArr;
}
function swapElement(i, j, array){
let temp = array[j];
array[j] = array[i];
array[i] = temp;
}By seeing both of the approaches second approach is a little bit better than the first. In the second approach, we have used counter and other variables to check whether the array is sorted or not. Please run both of the programs in your console by adding the debugger, and it will help you understand the concept.
Time Complexity:
In Best scenario: O(n)
In Average and worst scenario: O(nˆ2)
Space Complexity will be O(1) for all the scenario.
2. Selection Sort
We mainly focus on finding the smallest value in the array in selection sort, unlike in bubble sort. Following are the consideration in the selection sort.
- We assume that the first item in the array will be the smallest one.
- We will compare the item of array to the next item in the array
- If we find a smaller value than the first one we have started, we will swap their position.
- We will keep making the comparison and moving to the next item. Until the entire array is sorted.
Approach 1
function selectionSort(inputArr) {
let n = inputArr.length;
for(let i = 0; i < n; i++) {
// Finding the smallest number in the subarray
let min = i;
for(let j = i+1; j < n; j++){
if(inputArr[j] < inputArr[min]) {
min=j;
}
}
if (min != i) {
// Swapping the elements
swap(i, min, inputArr);
}
}
return inputArr;
}
function swap(i, j, array){
const temp = array[j];
array[j] = array[i];
array[i] = temp;
}Approach 2
function selectionSort(arr) {
// Write your code here.
let startId = 0;
while(startId < arr.length- 1){
let smallID = startId;
for(let i = startId + 1; i < array.length; i++ ){
if(arr[smallID] > arr[i]) smallID = i;
}
swap(startId, smallID, arr);
startId++;
}
return array;
}
function swap(i, j, array){
const temp = array[j];
array[j] = array[i];
array[i] = temp;
}Time Complexity and Space complexity
Best Time Complexity : O(nˆ2) (Time complexity will be same for best, average and worst)
Best Space Complexity : O(1)(space complexity will be same for all)
3. Merge Sort
We can say that merge sort will be the first sorting algorithm in which we will use recursion. In simple word, we can say that in recursion function call itself again and again until it met specific exit condition. So basically, the merge sort used the divide and conquered technique to sort the elements in the array. Let see the steps involved in that.
- It will split the given array into two parts. It is roughly equal to half.
- It will continue to divide the array into the subarray until you have left one single element left in the array.
- Starting with the single element array, it merges the subarray so that each merged subarray is sorted.
- Repeat step 3 until we end up with a single sorted array.
function mergeSort(array) {
if(array.length <= 1){
return array;
}
const middleItem = Math.floor(array.length / 2);
const leftArr = array.slice(0, middleItem);
const rightArray = array.slice(middleItem);
return merge(mergeSort(leftArr), mergeSort(rightArray));
}
function merge(leftArr, rightArr){
const outPut = [];
let leftIndex = 0;
let rightIndex = 0;
while(leftIndex < leftArr.length && rightIndex < rightArr.length){
const leftEl = leftArr[leftIndex];
const rightEl = rightArr[rightIndex];
if(leftEl < rightEl){
outPut.push(leftEl);
leftIndex++
} else {
outPut.push(rightEl);
rightIndex++
}
}
return [...outPut, ...leftArr.slice(leftIndex), ...rightArr.slice(rightIndex)];
}Time Complexity
Best, Average and Worst : O(n log(n))
Space Complexity
Best, Average and Worst : O(n log(n))
4.Quick Sort
Quick Sort algorithm uses the Divide and Conquer approach. It divides the array into smaller parts based on some condition. It will perform the sort operations on those divided smaller parts for performing the sort. We can approach this solution either recursively or iteratively. However, we will go with the recursive approach.
We will do the following steps to sort the array using Quick Sort.
- First, we will select an element that is to be called Pivot.
- We will compare all elements in the array with the Pivot element.
- After that, we will arrange them so that less than the Pivot will go the left and greater that will go the right side.
- After, that we will perform the same procedure with the right and left arrays.
Approach 1
function quickSort(array) {
if(array.length < 1){
return array;
}
const pivot = array[array.length - 1];
let leftArray = [];
let rightArray = [];
for(let i = 0; i< array.length - 1; i++){
if(array[i] < pivot){
leftArray.push(array[i]);
}else{
rightArray.push(array[i]);
}
}
return [ ...quickSort(leftArray), pivot, ...quickSort(rightArray)];
}Second Approach
function partition(arr, start, end){
// Taking the last element as the pivot
const pivotVal = arr[end];
let pivotIn= start;
for (let i = start; i < end; i++) {
if (arr[i] < pivotVal) {
// Swapping elements
[arr[i], arr[pivotIn]] = [arr[pivotIn], arr[i]];
// Moving to next element
pivotIn++;
}
}
// Putting the pivot value in the middle
[arr[pivotIn], arr[end]] = [arr[end], arr[pivotIn]]
return pivotIn;
};
function quickSortRecursive(arr, start, end) {
// Base case or terminating case
if (start >= end) {
return;
}
// Returns pivotInd
let index = partition(arr, start, end);
// Recursively apply the same logic to the left and right subarrays
quickSort(arr, start, index - 1);
quickSort(arr, index + 1, end);
}
// Call this function as follows
let arr = [8, 5, 2, 9, 5, 6, 3];
quickSortRecursive(arr, 0, arr.length - 1);
Time Complexity
Best, Average : O(n log(n))
Worst : O(nˆ2)
Space Complexity
Best, Average and Worst : O(n log(n))
Conclusion
In this article, we have gone through the theory and concept behind Bubble sort, Selection Sort, Merge Sort and Quick Sort. Firstly, we have tried to understand the basic concept. In the second phase, we have tried to solve those algorithms with two approaches using Javascript language.
Thanks for the such detail tutorial.