Algorithms – Insertion sort

Hope everyone gained some fundamental view of Data structure and algorithm. Let’s see about algorithms.

Definition

“Algorithm is a very well defined and finite number of computational procedures that takes certain value or set of values as input and produces certain value as corresponding output.”

Characteristics of an Algorithm

  • Must have minimal number of procedures for a specified task in order to be efficient.
  • Should terminate at some point
  • Must be finite

For example assume that we have to sort a given sequence of numbers in ascending order. This is a common problem can be found in many standard design techniques and analysis tools. So here

Input – a sequence of numbers < a1, a2, a3… an>

Output – a reordered sequence of given set < b1, b2, b3… bn>

For example given sequence of numbers are <21, 6, 14, 3, 7, 10, 5>, a sorting algorithm returns as output <3, 5, 6, 7, 10, 14, 21>, such an input is called an instance if the algorithm. In general an instance of a problem is consist of the input needed to compute a solution to the problem.

Which algorithm is best for a given application…?

  • The number of process to be done
  • The extent which the problem has already solved
  • Possible restrictions on the input, output and procedures
  • Architecture of the computer
  • Kind of storage devices to be used

 

Practical – 01

Insertion algorithm is one of the most popular algorithms used to sort given set of number. Let’s have a brief look on this algorithm.

1. Assume the first element is already sorted

Insertion algorithm example pic 01

2.  Pick the next element from the unsorted portion of the set and compare it with the first element. If it is less than the first element then swap them. Else move to next step.

Insertion algorithm example pic 02

3. Again pick the third element (value) from the set and compare it with second if it is less than second element assign that element in third element’s index. Now again check that number with the first element if it is  less than first element then place the first element value in second element’s index. Likewise repeat the task until there is that less than condition is being false and place that value in the false occurring index

Insertion algorithm pic_04

 

5. Process continues until the list is sorted

Task: Write a java program to sort a given set of Numbers using the Insertion Sort

Mathanraj Sharma
University of Jaffna

Add Comment