Insertion Sort


What is sorting?
Suppose you are playing a multiplayer game with your friends on a computer. Each player is rewarded some points at the end of the game. As the game finishes, we need to display the score of each player on the screen with the lowest score at the bottom and the score gradually increases as we move toward the top. So, the process of arranging the numbers in this order is called sorting.
How can we arrange numbers in such order? Well, there are different algorithms to do so but, here we discuss a basic algorithm called insertion sort. The concept of insertion sort can be easily understood with the following example. This example is taken from the CLRS book Introduction to Algorithms. Suppose we have to sort a hand of playing cards. Initially, the left hand is empty and the cards are facing down on the table. We then, remove a card from the table at a time and place it in the right position on the hand. To do so, we compare the card (say X) which we picked with the rightmost card on the left hand. If it is greater than the rightmost card, then the new card (card X) is now the rightmost card. Otherwise, the new card is compared with the next card left to the rightmost card. In this way, the card is compared from right to left until a card smaller than the card X is found on the hand. We can see that the cards on the left hand are sorted at all times.

Input to the algorithm: The sequence of numbers, a1, a2, a3, …, an.
Output from the algorithm: The reordering of numbers, a1’, a2’, a3’, …, an’ such that a1’ < a2’ < a3’ < … < an’.
Here is the pseudocode for the insertion sort.
Insertion-Sort (A)                              // A is the array of numbers to be sorted
      1.   for j = 2 to A.length
            2.                  key = A[j]
3.                              i = j – 1                        //A[j] is inserted into the sorted sequence A[1 … j-1]
4.                              while i > 0 and A[i] > key
5.                                                         A[i+1] = A[i]
6.                                                         i = i -1
7.                              A[i+1] = key
The worst case running time of insertion sort is θ(n2) where n is the length of the array. To see this, let us consider a barometer instruction (the instruction which is executed most). Here, we consider instruction in line 5 as a barometer instruction. Considering the outer for loop, line 5 is executed (n-1) times. With the while loop, line 5 is executed (j – 1) times which is equal to (n-1) in the worst case i.e. when the given array is sorted in reverse order then, the last element to be inserted to the array A[1…j-1] will take (n-1) times. This is just an intuition behind the fact that running time of insertion sort is bounded by θ(n2). For detail proof, see Introduction to Algorithms book by CLRS.



Comments

Post a Comment

Popular posts from this blog

Binary Search

Image
Binary search is used to locate an element in an array efficiently than the linear search. To use a binary search, the array must be sorted in non-decreasing order. If T[1…n] is the sorted array, then the binary search returns an index i at which the element(say x) is found. If the element is not in the array then, it returns a possible index where the element might be inserted. Here, we wish to find the index i such that 1 < i < n + 1 and T[i - 1] < x < T[i]. At first, let’s see how do we locate an element in an array using linear or sequential approach. LINEAR-SEARCH (T[1…n], x) for i = 1 to n if T[i] > x return i return n + 1 From the above algorithm, we can see clearly that the algorithm takes the time in θ(n) in the worst case where n is the number of elements. Now, let’s see how binary search algorithm will improve this running time. Basically, a binary search algorithm works like this. First, we compare the element x with the middle element of...
Read more

System Bus

Image
Have you ever wondered how the microprocessor communicates with the devices connected to it? Well, there are a group of wires (communication path) between microprocessor and its peripherals (and memory) to carry bits which are known as system bus. The system bus performs the following steps to communicate with the peripheral: i.         Identify the peripheral or the memory location (with its address). ii.       Transfer data and instructions in the form of bits. iii.     Provide timing and synchronization signals. According to the above functions, system bus can be classified into three types which are described below: Address Bus: It is a set of wires that is used to transmit address from the microprocessor to its peripheral devices (or memory. It is unidirectional. Each peripheral or memory is identified by its address. This is similar to the postal address of the house. For example...
Read more

Differences between hardwired and micro-programmed control unit

S.N. Hardwired Control Unit Micro-programmed Control Unit 1. It is implemented through the use of sequential logic circuit. Its input logic signals are transformed into a set of output logic signals which are control signals. It is implemented through the use of micro-programs. Micro-programs (control information) are organized as a sequence of micro-instructions stored in a special control memory. 2. This design uses a fixed architecture so, it require changes in wiring if the instruction set is modified. It is easy to reconfigure and modify instruction set. 3. It is difficult to build a circuit that satisfies all the operations. It is simple in structure. 4. It has faster mode of operation. It is comparatively slower. 5. It is comparatively expensive. It is cheaper. 6. It is preferred for less number of instruction sets. I...
Read more