# Sorting Algorithms

If you google sorting Google will tell you that sorting is any process of arranging items systematically either in descending or ascending order.
sorting can be achieved in so many ways but my goal is to show how the various sorting algorithms are executed and help you understand the logic behind them.

First, there are many sorting algorithms out there I will go through the common ones. This will be a two-part series. In the first part, we will talk about Bubble sort, selection sort, and insertion sort. These are relatively slow Algorithms mainly because they make comparisons while sorting.

1. Bubble Sort

This sorting algorithm basically pushes the largest to the end after every iteration. That's why it is called bubble sort, the largest value bubbles up.
The logic involved is below:-

1. initiate a loop i and iterate through from the end to the beginning

2. initiate an inner loop j and iterate from the beginning to i-1
   this is because when the loop runs the first time the largest value will bubble to the end hence this last value is already in its right position hence no need to move it. After the 2nd iteration, the 2nd largest value will bubble to the 2nd last place, and so on. Hence for the optimal operation, we don't have to keep making comparisons to the end of the array because after ith iteration the arr. length -i values will always be in their correct place. You can test this by logging the arr, j, j+1 after every iteration.

3. if value arr[j] > arr[j+1] swap the two values

4. repeat as long asi>0 and j<i-1
   

function bubbleSort(arr) {
for(let i= arr.length;i>0;i--){
    for (let j =0;j<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,j,j+1)
        }
    }

}
return arr
}

The swap portion is simple, we first store arr[j] in temp then we overwrite the arr[j] with arr[j+1] then we simply overwrite arr[j+1] with arr[j] which we stored in temp.
Another method is by using the swap function below which does the same thing.

const swap =(arr,index1,index2)=>{
     [arr[index1],arr[index2]] =[arr[index2],arr[index1]]
}

Hence our Bubble function would now resemble the function below;

function bubbleSort(arr) {

const swap =(arr,index1,index2)=>{
     [arr[index1],arr[index2]] =[arr[index2],arr[index1]]
}
//first loop
for(let i= arr.length;i>0;i--){
//2nd loop
    for (let j =0;j<i-1;j++){
        if(arr[j]>arr[j+1]){
            //swap fn
           swap(arr,j,j+1)
        //console.log(arr,j,j+1)
        }
    }

}
return arr
}

You will note these are two loops or nested for loops hence the time complexity will be O(n^2). We can make a slight optimization though it will not change the Time complexity. That is if uncomment the console.log and run the functions you will note that if you have an array that is nearly sorted i.e [1,3,2,5] here only 2 needs to be moved to its correct position but 6 comparisons will still occur instead of 3.
Here is how you test initiate counter and add 1 to it every time comparison occurs.

function bubbleSort(arr) {
    let counter=0
for(let i= arr.length;i>0;i--){
    sorted =true
    for (let j =0;j<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,j,j+1)
        }
        counter+=1

    }

}
console.log(counter)
return arr
}

console.log(bubbleSort([1,3,2,5]))

The counter will be 6 but if you initiate a value sorted and when the first loop is initiated set the sorted variable to true and set it to false after every swap. Then in the outside loop check if sorted is true and break if the condition is satisfied. This is because if a swap does not happen the array is already sorted and the sorted variable will always be true hence it's not necessary to make the extra comparisons. The Final code for bubble sort will be as follows.

function bubbleSort(arr) {
    let counter=0
    let sorted
for(let i= arr.length;i>0;i--){
  sorted =true
  counter=0
    for (let j =0;j<i-1;j++){
        if(arr[j]>arr[j+1]){
            let temp = arr[j]
                arr[j]=arr[j+1]
                arr[j+1]=temp
                sorted = false
             console.log(arr,j,j+1)
        }
        counter+=1
        if(sorted) break
    }

}
console.log(counter)
return arr
}

console.log(bubbleSort([1,3,2,5]))

The counter variable can be commented out after testing that the optimization worked.

2. Selection Sort

• Selection sort algorithm on the other hand initiates a variable let's call it lowest then the first for i loop sets the value for lowest from the 1st value,2nd,3rd... until n.

• after lowest is set a 2nd loop j inside the 1st loop is initiated also starting from i+1 inside this loop a comparison is made between jth iteration value and the current lowest value.

• If the jth value is less than the lowest value, the lowest is set to jth and the loop continues until the end of the inner loop.

• At this point, the inner loop ends

• if the current lowest is not equal to the initial value set which is i. the swap occurs.

The code is as below:-

function selectionSort(arr){
    //swap function
    const swap = (arr,index1,index2)=>{
        [arr[index1],arr[index2]] = [arr[index2],arr[index1]]
    }
    let lowest ;
    //iterate seeting a value i to lowest variable
    //initiate an inner loop iterating thorugh checking if 
    for(var i=0;i<arr.length;i++){
         lowest =i
        for(var j=i+1;j<arr.length;j++){
            if(arr[j]<arr[lowest]){
                lowest=j


            }
        }

        if(i !== lowest){
            swap(arr,i,lowest)
         // console.log(arr,arr[i],arr[lowest])
        }
    }
return arr
}

selection conclusion

The code above is already optimized because of the check to see if the values i and lowest are still equal after the inner loop finishes running. The time complexity is still O(n^2) but if think about bubble performs slightly better because if no swap occurs it break from the loop since everything will be sorted but selection sort both loops have to run to the end, hence if your values are almost sorted this algorithm's performance will be poor.

3. Insertion sort

• a current value variable is initiated in the function
• a 1st loop is with i=1 initiated with the currentValue variable set to the ith value iteration.
• The inner loop is initiated with j starting from i-1
• The loop will run as long as j>=0 and arr[j]>currentValue with j-- This is because with insertion sort a value is set in its correct position from always, hence the name. Then the comparisons happen from the right to left since after every iteration j--j reduces by 1 each time while i goes up .the code is below. Uncomment the console. logs to see what is actually happening for a better understanding.

function insertion (arr){

    //intiatiate a loop
    //set the current value to the 2nd element
    // compare with the current value with the previous 
     element swap if necessary
    // continue with the next element checking against the 
     ////left side if all values are in the correct place

    let currentValue;
    for(let i=1;i<arr.length;i++){
        currentValue =arr[i]
        for(var j=i-1;j>=0 && arr[j]>currentValue;j--){
            arr[j+1] = arr[j]

        }
        arr[j+1] = currentValue
    }

    return arr
}

Insertion sort also has time complexity O(n^2). It generally performs better than selection sort and bubble sort.
The commented console.logs() lines just log the arr after each iteration with the two values that were compared. I would suggest you uncomment them and take a look at the values logged in the console.

conclusion

I would suggest you running these algorithms through the javascript call stack to see how they work exactly. The simplest way to install an extension called snippets to chrome and use the call stack there. Here is an article on how to use the call stack with snippets in Chrome. This website shows a visual of the performance of the different sorting algorithms. In the next post, I will go through quick sort, radix sort, and finally merge sort and why their performance is better than these first three. Hint: they take advantage of different properties of floats, integers, in general, to sort them.

Comments

[cubiclesocial]

Years ago I wrote a hybrid sorting algorithm that combined Quick, Heap, Shell, and Insertion sorts. Combining algorithms allowed resulted in outperforming the C++ std::sort routine implementation by over 25% across multiple compilers, platforms, and architectures (up to 40% gains in some cases) - a fairly impressive feat given that std::sort was already magnitudes faster than the old C library standby qsort() function. My general-purpose hybrid algorithm demonstrated that even Quicksort/Quicksort3 presents opportunities for major performance gains by combining multiple algorithms.

Basically, it boils down to big-O. Each sorting algorithm has strengths and weaknesses. Some are better at locality while others are better as broad strokes. For example, Quicksort doesn't work well at locality and/or if the data is in reverse order but works well enough otherwise while Insertion sort is generally terrible for almost everything except for small numbers of items (~3-5) where it dramatically outperforms all other sorting algorithms. It you break the problem into "sort large swaths of data but eventually sort smaller amounts of data" then it makes sense that no single algorithm is suitable for all situations and a hybrid approach that plays to each algorithm's strengths is going to have better overall performance metrics.

In fact, some standard C/C++ library authors understand this and dynamically switch between Quick and a Heap or Mergesort if they detect certain conditions that turn a Quicksort into no better than Bubblesort.