Tag: Algorithms

Insertion Sort: Implementation and Analysis

KayLeave a comment

We have already established the importance of sorting algorithms in computer science in the previous posts on Bubble and Selection sorts. Let’s continue our journey with another such algorithm: Insertion Sort.

Definition

Insertion sort works on the array data structure as follows:

  • Start from the second element in the array, and iterate till the last element
  • In each iteration, select an element, and compare this element with all the elements to its left.
  • While comparing, whenever we find a greater element than our selected element, we move the greater element one step to the right
  • At the end of each iteration, we find a vacant spot to insert the element that we selected in the beginning of the iteration.

Let’s look at this visually to get a better understanding.

We will be sorting the following array:

We have five elements from index 0 to index 4.

Passthrough 1

Step 1: The algorithm starts from the second element in the array, so let’s select the element at index 1.

Step 2: Compare the selected element to all the elements to its left. Here we have just 1 element towards the left -> “6” at index 0. Let’s do the comparison: Is 6 greater than 1 ? Yes. Then as per the algorithm, let’s move it one spot to the right:

Step 3: Since we had only one element to the left of the selected element, we are done with the comparison and movements for this passthrough. Now we need to find a spot to insert our selected element.

As we can see, the spot at index 0 became available, since we moved the element “6” from index 0 to index 1. So let’s insert our selected element there:

And that concludes our first passthrough.

Passthrough 2

Step 1: In the first passthrough, we selected the element at index 1. In this passthrough, we will move to the next element and select the one at index 2:

Step 2: We now begin the comparison process where we will compare the selected element to all the elements towards its left.

Compare selected element “0” to “6” ,the first element to its left. Since 6 is greater than 0, we will move it one step to the right

Compare selected element “0” to “1”, the second element to its left. Since 1 is greater than 0, we will move it one step to the right

Step 3: We are done with the comparisons and movements for this passthrough. Now is the time to insert our selected element back into the array at the available vacant spot. Since we moved both the elements 1 and 6, we have a vacant spot at index 0. So let’s go ahead and insert our selected element there

Passthrough 3

Step 1: Now that we have got a hang of the algorithm , we know that in this passthrough we will select the element at index 3.

Step 2: Let’s begin with our comparisons. We would be comparing our selected element “10” with all the elements to its left.

We do our first comparison with element “6”. Since “6” is not greater than 10, we do not move it to the right.

Also, from our previous passthroughs, we know that all the elements that are to the left of 6 are smaller than 6 (because of all the previous steps that we did). This means that in this passthrough, we do not need to move any element to the right.

Step 3: We need to insert our selected element to an available spot in the array. Since we moved no element in the last step, the vacant spot would be the same position at which the element was before the passthrough. Hence, we put the element back at that position, and move on to the next passthrough.

Passthrough 4

Step 1: We move to the next element in our array, and select the element at index 4. Note that this is the last element in the array, and so this will be our last passthrough

Step 2: We now begin with our comparisons. We need to compare the element “2” with all the elements to its left.

Let’s start with the element at index 3 -> “10”. Since 10 is greater than 2, we move it one step to the right.

We now compare the selected element “2” with the element at index 2. Since 6 is greater than 2, we move 6 one step to the right

We now compare the selected element “2” with the element at index 1. Since 1 is not greater than 2, we do not move it to the right.

Also, because of our previous passthroughs and steps in the algorithm, we know for sure that all the elements towards the left of “1” would be less than “1”.

Step 3: After we have completed all the comparisons, we now need to insert our selected element back to the vacant spot in the array. Since we have the spot at index 2 vacant, we insert our selected element at index 2

And with the end of this passthrough, we have sorted our array!

Recap

Insertion sort is a bit tricky to understand as it has a lot of steps, and it compares elements in the other direction (towards the left), as opposed to other “forward looking” algorithms that compare the elements to their right.

So let’s recap what we did once again:

  • We did 4 passthroughs for an array of 5 elements
  • In each passthrough, we selected one element
  • We compared the selected element to all the elements to its left
  • Whenever we found an element greater than the selected element, we moved that element to the right
  • At the end of all the comparisons and movements, we had one vacant spot available in the array. We inserted our selected element to that spot ending our passthrough.

And hopefully now it makes sense why it is called insertion sort!

Implementation in C#

Here is an implementation of the insertion sort algorithm in C#

On running the above code, we get the following output:

Growth Complexity Analysis

Before jumping to mathematical terms that involve the variable “N”, let’s first try to look how many operations we performed in our algorithm.

We did the following operations on our array of 5 elements:

  1. 4 passthroughs
  2. 1 comparison and 1 movement operation in the first passthrough
  3. 2 comparison and 2 movement operations in the second passthrough
  4. 1 comparison and no movement in the third passthrough
  5. 3 comparisons and 2 movements in the fourth passthrough
  6. We also did 1 selection and 1 insertion operation in each passthrough, giving us a total of 4 selection and 4 insertion operations

This gives us a total of 4 passthrough + 7 comparisons + 5 movements + 4 selections + 4 insertions

Or a grand total of 24 operations for our array of 5 elements. Which is closer to (5) squared.

Let’s now try and derive a generalized complexity in terms of “N”.

Let’s focus on a worst case scenario – a case where all the elements in the array are in descending order.

For 1 passthrough we will do approximately: 1 selection + 1 insertion + (N-1) comparisons + (N-1) movements

And so for (N-1) passthroughs we would do approximately:

(N-1) * (1 + 1 + (N-1) + (N-1)) operations

If we ignore all the constants, we get something like:

(N) * (N)

which is equal to (N)^2 (n squared) operations

Thus we can say that the worst case complexity of an insertion sort is O(N^2) or order of N squared.

Summary

Insertion sort begins with the second element and iterates the array till the last element. In each iteration or passthrough, we select one element and compare it with the elements to its left. Whenever the elements to the left are greater than the selected element, we move them one step to the right. We then insert our selected element back to the array at the vacant spot.

This whole process would take a time complexity of O(N^2) in a worst case scenario.

feature image source: https://www.pexels.com/@digitalbuggu

Selection Sort: Implementation and Analysis

Kay1 Comment

Sorting plays an important role in any computer application. When processing large amounts of data, by using efficient sorting algorithms we can bring order to our data, which streamlines our data analysis process. Today, we will dive deep into one such sorting algorithm – selection sort (for more algorithms, head over to https://getsetcode.blog/algorithms/)

Selection sort – Definition

Selection sort is one of the easier algorithms to understand. Let’s first look into how this algorithm works, then analyze the time it takes to process data, and finally understand how this efficiency changes as we pump in more data. We will also implement the algorithm in C#.

Selection sort works on the Array data structure, and a simple definition would be as follows – “For N elements in an array, loop N-1 times, and in each iteration, select the smallest element and bring it to the first index of that iteration”

Let’s jump right into an example and work our way through to understand the algorithm.

We wish to sort the following array:

As per the definition,

  1. We are going to loop 4 times (N-1 times). Let’s call 1 loop as 1 iteration of the array
  2. In every iteration, we are going to find the smallest element, and bring it to the starting position of the iteration.

In order to accomplish the above, let’s define the variable start to track the start position of every iteration, and also let’s define the variable min to track the minimum element in one iteration.

To begin, Let’s initialize start at index 0, and also min equal to the element at index 0:

Iteration 1

We now start iterating the array. Whenever we move to the next element, we check if that element is less than our min element. If yes, we assign that element to min. If not, min remains unchanged and we keep moving forward to the next element. We will do this till we reach the last element of the array:

note that start will always point to the first position of the array

We have now reached the last element of the array, and have identified the smallest element “0” at index 3.

As a last step in this iteration, we will swap the minimum element, with the element at the start position:

This will give us the following array, with the minimum element at the first position. Note that at this point we have sorted the first element. Let’s gray out the first element to highlight that it has been sorted and from the next iteration we do not need to look at this element.

Iteration 2

We were able to sort one element in the last iteration, but we have four more elements to go! Since, the element at index 0 is already sorted, we will begin this iteration from index 1. Let’s initialize our start and min variables again:

Like we did last time, we will iterate through the array, checking for the minimum element at each index, until we reach the end of the array:

We have now reached the last element of the array, and have identified the smallest element at index 4. As we did in the last iteration, we will swap this smallest element with the element at the start position of this iteration:

After this step, we now have the first two elements in our array at correct or sorted positions:

Now that we have got a hang of the algorithm, let’s quickly do all the remaining iterations.

Iteration 3

Iteration 4

Note that in this iteration, the minimum element identified is “5”, which is at index 3, which is also the start index of this iteration. Thus, the minimum element is already at its correct position, and we do not need to swap it with any other element:

The 4th iteration was our last iteration. We sorted 4 elements in these iterations. We are just left with the last element, and since all the other elements are sorted, we can safely say that the last element is also in the correct position. This is why the selection sort runs N-1 iterations for N elements.

Quick Recap

  1. For N elements, the algorithm runs N-1 iterations
  2. For each iteration, we identify the start position and assign the min element to be equal to the element at that start position
  3. We iterate through the array till the last element. For every element we check if it is less than the min element. If yes, we replace the min element
  4. At the end of the iteration, we have identified the min element and we swap it with the element at the start position

Implementation in C#

Here’s an implementation of the algorithm in C#.

  • arr represents the array to be sorted
  • start represents the start position of the array. With every iteration, we will increment start by 1. The algorithm will run until start reaches the end of the array
  • min represents the index of the minimum element. We initialize this equal to the start position.

Let’s break the code into pieces to understand it better:

  1. We will run the algorithm until start reaches the end of the array:

2. The for loop below represents one iteration. We initialize min to be equal to the start index. We then go through each and every element starting from “start + 1” index and until the end of the array. We compare each element with the element at the “min” index. If we find a smaller element, we re-assign the min index

3. Finally, if the min index is different from the start index, we swap the elements at both these indexes to bring the smallest element to the first position:

on running the above algorithm, we get the sorted array:

Complexity Analysis

We have three primary operations in selection sort:

  1. Iterations – In our example of 5 elements, we did 4 iterations. Thus we can say that for N elements, selection sort will run N-1 iterations
  2. Swaps – At the end of every iteration, we performed one swap – the minimum element was swapped with the element at the first position
  3. Comparisons – comparison is the operation when we check if each element is smaller than the minimum element. For our first iteration, we did 4 comparisons, for the second iteration we did 3, for third iteration we did 2 comparisons and for the 4th iteration we did 1 comparison. In other words we did: (N-1) + (N-2) + (N-3) … + 1 comparisons.

For 1 iteration, we did: 1 swap + N-1 comparisons

For (N-1) iterations, we will do approximately: (N-1) * (1 swap + N-1 comparisons )

If we ignore all the constants in the above equation, we will get N * N, or N squared (N^2).

Thus, the complexity of selection sort is O(N^2).

Efficiency of Algorithm with increasing data

We derived the complexity of the algorithm as N squared. If we plug in numbers, we can see how the number of operations that the algorithm takes increases:

N = 5, N^2 = 25

N = 10, N^2 = 100

N = 15, N^2 = 225

This shows that by increasing the number of elements by 5, we are increasing the number of operations at a really fast pace. Just by going from 5 to 10 elements, we increased the number of operations by 75! When we went from 10 to 15 elements, we increased the number of operations by 125!

Thus, as the data increases, the algorithm efficiency decreases and so selection sort is not a good choice when it comes to sorting huge amounts of data.

Summary

  • Selection sort works on array data structures. It loops through the array N-1 times, and in each loop finds the smallest element. This element is swapped by the element at the first position.
  • The primary operations in this algorithm are iterations, swaps and comparisons. By calculating the number of operations, we can derive the complexity of selection sort as O(N^2)
  • As we increase input data, the number of operations done by the algorithm increases at a much faster rate, making selection sort a bad choice for large amounts of data.

Bubble Sort: Implementation and Analysis

Kay1 Comment

Sorting is the lifeline of coding. We almost always want things in a natural order. An alphabetical order of a list of items is easier to comprehend. Going over your bank transaction history, ordered by date, is much better to analyze.

Today we have high-level, easy to read and write programming languages which usually have a built-in sort function. For instance, in C# you just need to call the Array.Sort() method, and C# would do the rest for you.

But understanding what is happening behind the scenes makes you a much better programmer. You can analyze how fast or slow your data is being sorted and what impact that algorithm is having on your application.

In this article we will look at the most basic sorting algorithm – Bubble sort. It has a fun name, and is easy to understand. We will first learn what bubble sort is and analyze the complexity of the algorithm. Then we will write some code in C#. We will also try to improve the performance of our code with the help of a boolean variable.

Bubble Sort – Definition

Bubble sort to sorting algorithms is like learning A-B-C-D to understand the English language! Let’s jump write into an example and learn the algorithm step by step. Consider the following array of numbers:

Start with the first two elements in the array and compare them. If the first element is greater than the second element, swap the elements.

Compare:

Swap:

Move on to the next two elements. Compare and Swap again as we did in the last step:

Compare:

Since these two elements are already sorted, we do not swap and move on to the next two elements

Compare:

Swap:

And finally compare and swap the last two elements:

Compare:

Swap:

We worked our way till the last index. And now our array looks like this:

I will pause here to point out that this is just one pass of the array. We went from index 0 to index 4, comparing and swapping along the way, and the outcome of this pass is that the highest element in the array (6) is at the last position. In other words, we have bubbled the highest element out to the last position – hence the name, bubble sort.

As you might have guessed, the algorithm does not stop here, as after the first pass, we have just brought one element to its correct position, and we still have the first four elements in wrong positions.

And so, we do another pass, but this time we go from index 0 to index 3 (as our last element has already been sorted). Let’s gray out the last element to make things clearer. Now that we have got a hang of how the comparison and swapping works, lets quickly go through the second pass:

After this pass, we have now brought the second highest element in our array to the correct position:

We are already down 2 passes, but our array is still not sorted. Let’s do another pass, but this time only till index 2, as the last two elements have been sorted:

After the third pass, our third highest element is in position:

We have one more pass to go, as the first two elements are still not sorted. This fourth pass will have only one comparison and swap operation:

and after this step, we have our sorted array:

Analysis and Complexity

Let’s stop here and note a few things that happened along the way:

  1. We had 5 elements in our array, and we were able to sort the array in 4 passes. This means that for N elements, bubble sort will walk through the array N-1 times.
  2. With every pass we are able to sort 1 element. When you look from this perspective, we can again conclude that for an array of N elements, we will need N-1 pass-throughs of the array.
  3. In pass 1, we did 4 comparisons. In pass 2, we did 3 comparisons. In pass 3, we did 2 comparisons. In pass 4, we did 1 comparison. Thus, for an array of N elements, a bubble sort will do (N-1) + (N-2) + (N-3) +……+ 1 comparisons. In our example of 5 elements, we did 4+3+2+1 = 10 comparisons.
  4. In pass 1, we did 3 swaps, In pass 2, we did 2 swaps, in pass 3, we did 1 swap and in pass 4 we did 1 swap again. This sums up to 3+2+1+1 = 7 swaps.
  5. To summarize, to sort our array of 5 elements, we did 4 passes + 10 comparisons + 7 swaps = or a total of 21 steps or operations. We can also say that the total number of steps are close to (5)^2 (5 squared).
  6. The worst case scenario would be when we have the array sorted in reverse order (descending). In that case we will have a swap with every comparison. In our above example, if all the elements were in descending order, then to sort our array we would have done 4 passes + 10 comparisons + 10 Swaps for a total of 24 operations. (again almost equal to 5^2)

If you followed and understood all the 6 steps that we just did, then you just solved the complexity of a bubble sort! For an array with N elements, a bubble sort will take close to N^2 steps to fully sort the array. In other words, the complexity of a bubble sort is O(N^2) or order of N squared. That means if we have an array of 6 elements, a bubble sort will take close to 36 steps, for 10 elements 100 steps, for 20 elements 400 steps. As you might have guessed, bubble sort is not a great choice when we have huge amounts of data. But by learning bubble sort, and by understanding why it gets in-efficient as the data increases, we can develop better and faster algorithms!

Implementation

Following is an implementation of bubble sort in C#:

  • sortedIndex is initialized to point to the last element of the array. With every pass we will reduce the sortedIndex by 1
  • Pass variable will track the number of passes of the array we do to fully sort the array
  • ComparisonSteps variable will track the number of comparisons we do
  • SwapSteps variable will track the number of swaps we do
  • While (sortedIndex > 0) represents each pass of the array.
  • The for loop covers all the comparisons and swaps in one pass

As you can see, we have initialized an array of 10 elements, and the array is in descending order. This case represents a worst case scenario. On running the above code, we get the following:

The algorithm takes 9 passes, 45 comparison steps and 45 swap steps to give a total of 99 steps, which is close to 10 squared. Thus giving a great example of the complexity of the algorithm.

A slightly better implementation

The implementation that we did earlier will take N-1 passes and compare every two elements along the way. Now consider a case when some elements of the array are already sorted. For example:

Here, the last three elements are already sorted, but according to the algorithm we will still need to compare all the elements.

We can slightly improve the implementation of our algorithm to first check if we already have a sorted array. In a pass, we will track if there were any swaps made. If not, it implies that we already have all the elements sorted, and we no longer need to pass through the entire array again.

We will declare a boolean variable “sorted” which will be set to false. During 1 pass, if we make a swap, we set the variable to true. Now, if we complete the pass, but we did not do any swap (because all elements were already sorted), the boolean variable “sorted” will still be set to false. This will indicate that the array has been sorted, and we can safely end the algorithm.

Our modified code will be as follows:

On running the above code on the array [1,0,2,5,6], we get the following output:

Note that we took only 1 pass and 1 swap step!! All because we checked along the way if the rest of the array is sorted, and exited the while loop when we no longer needed to go through each and every element.

Summary

In this article we did a deep dive to understand the bubble sort algorithm. It is a simple sorting algorithm which compares each and every element in an array, moving the greater element to the right with every pass.

The complexity of bubble sort is O(N^2), and we did an in-depth analysis and implemented code to understand that. Bubble sort might not be a good algorithm to sort large amounts of data.

Feature Image: https://www.pexels.com/@padrinan