Sorting Arrays Using Algorithmic Sorting Methods

This blog is for software developers that are looking to broaden their knowledge regarding algorithms and time complexity, while also understanding how and when to use the Bubble Sorting method.

As a software developer, there WILL be times when you’re asked to figure out the time complexity of an algorithm or program. You may even be asked to write out an algorithm yourself with a certain time complexity. In many tech interviews that you experience, if not all of them, you will be asked these questions.

I first came across these graphs and alogrithmic problems during my time at Flatiron School for Software Engineering. I didn’t think they would be that important to understand until reaching the end of the program, which I learned that I may need to be able to solve these problems during a tech interview. You might not need to know everything about them, but understanding these problems and having a plan for solving them is going to make you stand out over other candidates you’re up against.

What is Time Complexity?

In simple terms, time complexity is the efficiency of a program, or the time it takes for a program to complete its task. As you saw from the graph above, time complexity is expressed in the “big O notation.” The mathematical representation for an algorithm is written as O(Nn). “N” is the number of inputs and “n” is the number of looping expressions. I will go over some of these time complexities with some examples below.

Bubble Sorting

When given an array of numbers, how would you sort that array so that the array is sorted out from the smallest to largest number? Well as a beginner in sorting, I would try and make a function that will check the first element of the array and check to see if that number is larger than the next element, then swap the indexes if that first element is greater than the second element, and continue that process until the array is sorted. That is essentially what bubble sorting is. Bubble sorting is accomplished by comparing adjacent elements and sorting them in ascending or descending order. Here is an example below:

Bubble Sorting Process
let arr = [2, 4, 3, 5, 1]
function bubbleSort(arr){
for(let i = 0; i < arr.length; i++){ for(let j = 0; j < ( arr.length - i -1 ); j++){ if(arr[j] > arr[j+1]){
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j+1] = temp
}
}
}
console.log(arr);
}
// expected output ===> [1, 2, 3, 4, 5]

In this code example, we are checking if the element at the current iteration is greater than the next iteration. If that comes to true, then we are going to swap those elements and move on. Touching on what the time complexity is of this function, because this array contains five elements, you will be performing four comparisons.

N = Number of elements in array
N - 1 = Number of time comparisons that occur
5 - 1 = 4

This example has a time complexity of O(n²) which means this is not the most optimized solution to sorting an array. If the array was already sorted then the time complexity would be O(n) which is obviously the fastest solution to checking to see if the array is sorted.

Selection Sorting

The sorting method is simpler in understanding because it divides the array into two sections: sorted, and unsorted. This means that while this algorithm is working, it checks to see which side is sorted and unsorted, and simply sort out the unsorted side! For the unsorted side, It’s going to check for the smallest number and put that in the sorted side. Then on the next iteration, it’s going to do the same thing and check for the smallest number again in the unsorted side and move it to the sorted side, and so on… Here is an example of what’s going on under the hood.

That is the first iteration of how it sorts through the unsorted side of the array. Once the element with the smallest value is found after iterating through the entire side of the unsorted array, it puts that value in the sorted side. This time complexity is the same as bubble sorting with a value of O(n²), but is a little easier to understand how it works. The code example for this is provided below:

function selectionSort(inputArr) {      
let n = inputArr.length;

for(let i = 0; i < n; i++) {
// Finding the smallest number in the unsorted array
let min = i;
for(let j = i+1; j < n; j++){
if(inputArr[j] < inputArr[min]) {
min=j;
}
}
if (min != i) {
// Swapping the elements
let tmp = inputArr[i];
inputArr[i] = inputArr[min];
inputArr[min] = tmp;
}
}
return inputArr;
}

Merge Sorting

Merge sorting is one of the more popular algorithms in sorting arrays because of the time complexity and effeciency of this method. The time complexity is O(n*logn) which means that logn operations will occur n times. This is a very common algorithm many developers. Merge sorting divides a given array in half, and then does that until each element is its own subarray. Here is an example of how that works below:

After dividing the array into subarrays that can be sorted, the merge process then merges those arrays into a sorted array, then continues to merge them into the final sorted array. An example of how the code would look is below:

function merge(left, right) {     
let arr = []
// Break out of loop if any one of the array gets empty
while (left.length && right.length) {
// Pick the smallest element of left and right sub arrays
if (left[0] < right[0]) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}
return [ ...arr, ...left, ...right ]
}

Summary

Hopefully this helps understand some sorting algortihms for your future and will now be able to tackle any problem involving these types of methods when you come across them. They are going to be extremely handy to understand the time complexity of these algorithms and also helpful for your tech interview!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store