What are algorithms?

The term algorithm is very familiar in the field of computer science and it acquires an important place in all computing systems.

An algorithm is any well-defined set of computational procedures that takes some value, or set of values, as input and produces some values, or set of values as output.

For example, we might need to sort a sequence of numbers in non-decreasing order.
Input: A sequence of n numbers (a1, a2, a3,..., an).
Output: A permutation (a1', a2', a3',..., an’) of input sequence such that a1'≤a2'≤...≤an’.

This problem is known as the sorting problem.

We will consider a simple sorting algorithm, that is Insertion Sort, for understanding how to design and do the analysis of any algorithm.

Insertion Sort is an efficient algorithm for sorting a small number of elements. It works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each card already in the hand, from right to left. At all times, the cards held in the left hand are sorted and these cards were originally the top cards of the pile on the table.

As we have understood the algorithm, we will write pseudo code for it.

Let input is an array A and A.length give the number of elements in an array.

Insertion-Sort
for i=2 to A.length
    key = A[i]
    j=i-1
    while j>0 and A[j]>key
        A[j+1]=A[j]
        j=j-1
    A[j+1]=key

The index i indicates the current card being inserted into the hand. At the beginning of each iteration of the for loop the subarray A[1...j-1] constitutes the currently sorted hand, and the remaining subarray A[j+1...n] represents the pile of unsorted cards.

Analyzing algorithms

Analyzing an algorithm means predicting the resources that the algorithm requires. Generally, by analyzing several algorithms candidate for a problem we can identify the most efficient one.

Analysis of Insertion Sort
The time taken by the Insertion-Sort procedure depends on the input: sorting a thousand numbers takes longer than sorting three numbers. It also depends on how nearly sorted the numbers are already for inputs of the same size.

In general, the time taken by an algorithm grows with the size of the input. So we can describe the running time of the program as a function of the size of its input.

The measure of input size depends on the problem being studied. For example, for sorting problem the most natural measure is the number of items in the input, that is the array size n.

The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. Let’s assume that a constant amount of time is required to execute each line of our pseudocode.

We start by presenting the Insertion-Sort procedure with the time cost of each statement and the number of times each statement is executed.

Insertion-Sort                         cost         times
for i=2 to A.length                    c1           n
    key = A[i]                         c2           n-1
    j=i-1                              c3           n-1
    while j>0 and A[j]>key             c4           Σtⱼ ;2<=j<=n
        A[j+1]=A[j]                    c5           Σ(tⱼ-1) ;2<=j<=n
        j=j-1                          c6           Σ(tⱼ-1) ;2<=j<=n
    A[j+1]=key                         c7           n-1

here tⱼ denote the number of times the while loop is executed for that value of j.

Let’s denote the running time of Insertion-Sort by T(n). To compute T(n) we sum the products of the cost and times columns and after solving it we will get the quadratic equation of the form an²+bn+c. Thus it is a quadratic function of n.

Some problems on insertion sort

1. Sort a linked list using insertion sort (Leetcode#147)

Example:

Input: 4->2->1->3
Output: 1->2->3->4

Solution:

public ListNode insertionSortList(ListNode head) {
	ListNode cur = head;
	ListNode dummy = new ListNode(0), i;
	while (cur != null) {
		//locate the insertion position.
		i = dummy;
		while (i.next != null &&  cur.val > i.next.val) {
			i = i.next;
		}
		//insert between i and i.next.
		ListNode iNext = i.next;
		i.next = cur;
		ListNode next = cur.next;
		cur.next = iNext;
		cur = next;
	}
	return dummy.next;
}

here ListNode is defined as

public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

References

[1] Introduction to Algorithms by Thomas Cormen, Charles Leiserson, and Ronald Rivest.