In this story am going to walk through about elementary sorting algorithm and its performance. There many type of sorting algorithm, here we are going to learn about implementing Bubble Sort, Insertion Sort & Selection sort in Javascript. Bubble Sort The bubble sort repeatedly traverse all unsorted elements and compare the consecutive elements then interchange each other when they are out of order. Pseudo Code (A is an array elements, where N is the length an array) FOR I = to N - FOR J = to N - IF A[J] > A[J + ] TEMP = A[J] A[J] = A[J + ] A[J + ] = A[J] END-FOR END-FOR of of 0 2 0 2 1 1 1 Implementation { n = a.length; ( i = ; i < (n - ); i++) { (j = ; j < (n - ); j++) { (a[j] > a[j + ]) { temp = a[j]; a[j] = a[j + ]; a[j + ] = temp; } } } a; } input = [ , , , , ]; result = bubbleSort(input); ( ) function bubbleSort a const // Iteration of array till last before element for let 0 2 // Iteration of array till last before element for 0 2 if 1 //Swap the consecutive elements let 1 1 return const 5 4 2 6 7 const // Expected Output: [ 2, 4, 5, 6, 7 ] The given program will result the For example when the given input is [5,4,2,6,7] it will return output array as [2,4,5,6,7] sorted array in ascending order. Insertion Sort Traverse all elements in an array and insert each element within a sorted array. Pseudo Code (A is an array elements, where N is the length an array) FOR I = to N - J = WHILE J > AND A[J] < A[J - ] TEMP = A[J] A[J] = A[J - ] A[J - ] = TEMP END-WHILE END-FOR of of 0 1 1 0 1 1 1 Implementation { n = a.length; (i = ; i < n; i++) { j = i; (j >= && a[j] < a[j - ]) { temp = a[j]; a[j] = a[j - ] a[j - ] = temp; j--; } } a; } ( ) function insertionSort a const // Iteration of array till last element for 0 let // Iterate over the sorted part of array and insert the element while 0 1 let 1 1 return Selection Sort Traverse all elements in an array and find the smallest element in unsorted array and swap it with the first element Pseudo Code (A is an array elements, where N is the length an array) For I = to N : leastElementIndex = I For J = I + to N : If A(J) < A(leastElementIndex) leastElementIndex = J End-If End-For Temp = A(I) A(I) = A(leastElementIndex) A(leastElementIndex) = Temp End-For of of 0 -1 do 1 -1 do Implementation { n = a.length; ( i = ; i < (n - ); i++) { leastElementIndex = i; ( j = i + ; j < (a.length - i); j++) { (a[j] < a[leastElementIndex]) { leastElementIndex = j; } } temp = a[i]; a[i] = a[leastElementIndex]; a[leastElementIndex] = temp; } a; } selectionSort([ , , , , ]) ( ) function selectionSort a const // Iteration of array till last element for let 0 1 let for let 1 // Check for least element and override least element index if // Swap elements let return 5 4 2 6 7 // Output : [ 2, 4, 5, 6, 7 ] Algorithm Time Complexity Analysis All the above mentioned sorting algorithms are inefficient algorithms, there are more advanced sorting algorithms available which will be posted in upcoming stories. The upper bound worst case complexity for all the three algorithms are Quadratic Time as per . O (n^2) Big-0 Notation Visualization In order to visualize the flow of above mentioned algorithms in animation, check out this geeky website by . It has visualization collection of many data structures and algorithms Dr Steven Halim, https://visualgo.net/en/sorting Reference https://users.csc.calpoly.edu/~jdalbey/SWE/pdl_std.html
