## What is Insertion Sort?

Introduction

When we need to perform sorting on a list of elements then Insertion Sort is one of the basic algorithms which can be used. It’s simple but as we will see it’s not very efficient.

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists. –Wiki

It’s quite similar to the way we sort playing cards in our hand. It involves comparison and movement for each of the elements. It uses two loops. That’s the reason worst case complexity is O(N²) (you can read about “Big O” notation here). The best case scenario means that the list is already sorted. So we only perform comparison and no movements. That gives us a time complexity of O(N).

Let’s look at the Algorithm

Suppose we have a list of numbers  4,2,3,5,1,7 and we want to sort these.

• Put elements in an Array. Say array name is input. Code : int input = {4,2,3,5,1,7};
• Start with the second index i.e. input which has a value 2. Let’s denote this as “current_number“.
• Run a loop in reverse.
• Compare current_number with each of the numbers prior to it. If it’s less than any then shift or move the element to right. At the end of this iteration we will find a place for current_number.
• Repeat this Procedure for all elements in the Array.

## Traversing a Graph using Breadth First Traversal

Earlier I have shown you how to build a simple Graph using Adjacency List. We used a Friendship Graph to demonstrate that. If you haven’t read that I will recommend you to take a look at the following two posts that cover Graphs and Queues, since we will make use of both these structures. Building on that we are going to see how to traverse that Graph using a very popular approach known as “breadth first traversal”, or BFS.

At the end of this Post I have presented code written in C to show you how can BFS be implemented. After all we should be able to write the code and not just talk about the approach.

Few applications of Breadth First Traversal (BFT)

• BFT can be used to generate a Tree. This tree can help us find out shortest distances from root node to other nodes. Also it can be used to find Paths between vertices.
• BFT can be used to determine the connected components in a Graph. A connected component means that any vertex in that component can be reached from any other vertex in the same component.
• It can help us solve Vertex Coloring problem, which has applications like assigning resources etc.

Understanding BFT

Let’s start by understanding BFT. In BFT we pick a vertex to start with. In our example friendship graph we start with Ankur. We insert this in a Queue (Q) and mark it as visited.

## A simple QuickSort Program in Java

Introduction to Quick Sort

QuickSort algorithm is based on the Divide and Conquer Approach.

For a given sequence S there are 4 basic steps involved:

• Pick a number X from S. This program picks the last element.
• Create two Lists. One list will store elements less than X and the other will store greater than X.
• Sort the two lists recursively.
• Combine the left list elements with X and the right list elements.

The program below sorts a sequence of Integers. After which another version has been provided which can be used to sort a sequence of characters.These are my own versions of the QuickSort Algorithm.