What is Insertion Sort?



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[1] 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.

The C Program below will help you understand this better.

Continue reading “What is Insertion Sort?”

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.

Continue reading “A simple QuickSort Program in Java”