B.Sc. Applied Physical Science

Part I- Sem –II

Paper V

Lecture No : 12

ELPT – 202: Data Structures

Title of Programme: Insertion Sort

Script

  1. Introduction

Hi friends, today we shall be discussing another very simple and popular sorting algorithm called insertion sort. Insertion sort is a very simple and one of the most efficient of the O(n2) internal sorting algorithms. If the first few objects are already sorted, an unsorted object can be inserted in the sorted set in proper place. This is the basic principle of insertion sort. Insertion sort is an example of anincrementalalgorithm; it builds the sorted sequence one number at a time. It is an algorithms that many people intuitively use for sorting cards and it is very easy to illustrate on the deck of cards. To sort the cards in your hand you extract a card, shift the remaining cards, and then insert the extracted card in the correct place. This process is repeated until all the cards are in the correct sequence.

This is illustrated in the following slides.

The Insertion Sort Algorithm

Key ideas:

  1. Insertion sort always maintains two zones in the array to be sorted:sortedandunsorted.
  2. At the beginningthe sorted zoneconsist of one element (the first element of array that we are sorting).
  3. On each step the algorithm expandsthe sorted zoneby one element inserting the first element fromthe unsorted zonein the proper place in thesorted zoneand shifting all larger elements one slot down.

The algorithm is :

  1. Get a list of unsorted numbers
  2. Set a marker for the sorted section after the first number in the list
  3. Repeat steps 4 through 6 until the unsorted section is empty
  4. Select the first unsorted number
  5. Swap this number to the left until it arrives in the correct sorted position.(i.e. until the next number to the left is smaller or it has reached the head of the list.)
  6. Advance the marker to the right one position
  7. Stop

As seen below in the slide, the sorted section has three elements and unsorted section has rest of the elements. We then see how the first element in the unsorted section, 45, is next picked and inserted in its correct position in sorted section, increasing the size of sorted section by

  1. An Example

We explain the algorithm with anotherexample. Consider an array of five elements with values 98, 23, 45, 6, 14. In the beginning, the sorted section has only one element 98, while other 4 elements are in the unsorted section. The first element from the unsorted section, 23 is picked and compared with 98. As 23 is smaller than 98 so they are swapped. The next element 45 is then picked from the unsorted section and compared with 98 and 23 and inserted after 23. The next element, 6, is compared with 98, 45 and 23 and inserted before 23. The last element from the unsorted section, 14, is compared with 98, 45, 23 and 6 and inserted after 6.

As can be seen there have total 10 comparisons made by the algorithm.

Now we look, how the algorithm performs if the array is already sorted. Consider an array containing 6 values 0,1,2,3,4 and 5 in ascending order. In first pass, 1 will be compared with 0 and 1 is greater than 0, it stops there. So no swap takes place and 1 comparison is made.

In second pass, the next element in unsorted section 2 is compared with last element in sorted section, 1 and as 2 is greater than 1, so it stops. Again no swap takes place and only one comparison is made. Similarly for 3, 4 and 5 only one comparison is made while shifting them from unsorted section to sorted section. Thus to sort an already sorted array of 6 elements only 5 comparisons are made.

  1. Implementation

The code in C for insertion sort is:

void insertionSort(int A[], int size)

{

int i, key, j;

for (i = 1; i < size; i++)

{

key = A[i];

j = i-1;

/* Move elements of A[0..i-1], that are greater than key, to oneposition ahead of their current position.

This loop will run at most i times */

while (j >= 0 & A[j] > key)

{

A[j+1] = A[j];

j = j-1;

}

A[j+1] = key;

}

}

There are two loops in the function. The outer loop runs size-1 times, where size is the number of elements in the array. The inner loop moves elements of sorted section, A[0..i-1], that are greater than key, to one position ahead of their current position.This loop will run at most i times, where i is the size of current sorted section and if key is greater then A[i-1], the largest element in the sorted section, the loop will not be executed even once.

  1. Performance

Insertion sort is a simple, good middle-of-the-road choice for sorting lists of a few thousand items or less.

Best, worst, and average cases

Insertion sort performs best if the element list is already sorted. In this case as already seen,during each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array and so the number of comparisons are n-1 only, giving the running timeof O(n), which is best for any sorting algorithm. Thus to sort an almost sorted array where only say a few elements are out of place, insertion sort is most efficient sorting algorithm.

The worst case input is anarraysorted in reverse order In the worst case the list must be fully traversed (we are always inserting the next-smallest item into the ascending list), shown in following slides. Thus the number of comparisons are : 1 + 2 + ... n-1, which is O(n2).

On average each insertion must traverse half the currently sorted list while making one comparison per step. Thus the number of comparisons will be roughly equal to : (1 + 2 + ... n-1)/2, which is again O(n2).

As the average and worst cases are quadratic, this makes insertion sort impractical for sorting largearray. However, insertion sort is one of the fastest algorithms for sorting small arrays, even faster than quicksort.

Advantages of insertion sort

  • Simple to code
  • Very good performance with small lists (how small is small depends on the power of the computer it is running on)
  • Very good when the list is almost sorted. In this case very few comparisons need to be performed.
  • Sort-stable which means it keeps the relative positions of the elements intact
  • Very memory efficient - it only needs one extra storage location to make room for the moving elements.
  • Good with sequential data that is being read in one at a time e.g. tape, hard disk or data being received sequentially.

Disadvantage of insertion sort compared to alternatives

  • Poor performance with large lists.
  • Not as quick as merge sort or quicksort
  1. Conclusion

With this we come to end of today’s lecture. Today we had discussed insertion sort, a very simple but efficient algorithm for sorting small number of elements. Though its average and worst case running time is O(n2), but it is still in general much faster than selection sort and bubble sort.

We conclude our lecture by showing an excellent video created by Sapientia University, in which insertion sort has been nicely depicted in form of Romanian folk dance.

Thanking you.

B.Sc. Applied Physical Science

Part I- Sem –II

Paper V

Lecture No : 17

ELPT – 202: Data Structures

Title of Programme: Insertion Sort

Objective

The main objective of the lecture is to introduce Insertion Sort algorithm and its implementation. The strengths and weakness of the algorithm are also discussed in detail.

B.Sc. Applied Physical Science

Part I- Sem –II

Paper V

Lecture No : 12

ELPT – 202: Data Structures

Title of Programme: Insertion Sort

Summary

•Insertion sort is a simple sorting algorithm that is appropriate for small inputs.

–Most common sorting technique used by card players.

•The list is divided into two parts: sorted and unsorted.

•In each pass, the first element of the unsorted part is picked up, transferred to the sorted sublist, and inserted at the appropriate place.

•A list of n elements will take at most n-1 passes to sort the data.

B.Sc. Applied Physical Science

Part I- Sem –II

Paper V

Lecture No : 12

ELPT – 202: Data Structures

Title of Programme: Insertion Sort

FAQs

Q1. What are the strengths of insertion sort algorithm?

Ans :The main strengths of insertion sort are:

  1. It is very simple to understand and easy to implement.
  2. It does not use any extra space.
  3. It performs very well on almost sorted data items.

Q2. What are the limitations of insertion sort algorithm?

Ans :The major weakness of insertion sort is that it is very slow. As the size of data increases, this becomes its major limitation

Q3. What is the performance of insertion sort algorithm?

Ans :Insertion sort algorithm's best performance is O(n), while average and worst case performance is O(n2) .

Q4. In which situations do we prefer to useinsertion sort algorithm over other sorting algorithms?

Ans :Insertion sort algorithm is commonly used where the size of the data is not large and programming effort is to be kept to a minimum. Insertion sort may also be used for sorting an almost sorted array or an array in which majority of elements are in place.

B.Sc. Applied Physical Science

Part I- Sem –II

Paper V

Lecture No : 12

ELPT – 202: Data Structures

Title of Programme: Insertion Sort

Glossary

Insertion Sort : A sorting algorithm that inserts each item in the proper place into an initially empty list by comparing it with each item in the list until it finds the new element's successor or the end of the list.

Adaptive Sorting Algorithm : A sorting algorithm is adaptive if it takes advantage of the order of the input list to facilitate sorting

Assignments:

  1. Give a sequence of 5 numbers, which can be sorted by insertion sort using exactly seven comparisons.
  2. Consider the list {24, 20, 10, 75, 70, 18, 60, 35}. Suppose that list is sorted using the insertion sort. What is the resulting list after four passes of the sorting phase, that is, after fouriteration of the outer for loop?
  3. While running a computer program to sort student exam scores using insertion sort, the power goes out. Fortunately, the program was designed so it saved the scores after each swap. Just from looking at the saved scores, can you tell about number of passes completed?
  4. Implement Insertion Sort and determine the running time to sort 10,000 integers sorted in ascending, desceding and random order.

Quiz

Q.1) What are the correct intermediate steps of the following data set when it is being sorted with the Insertion sort? 15,20,10,18

A. 15,20,10,18 -- 10,15,20,18 -- 10,15,18,20 -- 10,15,18,20

B. 15,18,10,20 -- 10,18,15,20 -- 10,15,18,20 -- 10,15,18,20

C. 15,10,20,18 -- 15,10,18,20 -- 10,15,18,20

D. 10, 20,15,18 -- 10,15,20,18 -- 10,15,18,20

Q.2) If all the elements in an input array is equal for example {1,1,1,1,1,1}, What would be the running time of the Insertion Algorithm?

A.O(log n)

B.O(n^2)

C.O(n)

D.O(1)

Q.3) Consider the following operations on an ordered set of

elements:

(3 7 5 1)

(1 7 5 3)

(1 3 5 7)

(1 3 5 7)

Which of the sorting algorithms would best describe the above process?

A. Bubble sort

B. Selection sort

C. Insertion sort

D. All of above

Q.4) What kind of data structure would make insertion sort particularly inefficient?

A. A memory intensive data structure.

B. A linear data structure.

C. A data structure for which shifts are inefficient.

D. None of above

B.Sc. Applied Physical Science

Part I- Sem –II

Paper V

Lecture No : 12

ELPT – 202: Data Structures

Title of Programme: Insertion Sort

References

  1. Data structures, Algorithms and Applications in C++ (2nd Edition) by Sartaj Sahni
  1. Data Structures and Algorithm Analysis in C++ (3rd Edition) by Mark A. Weiss
  1. Data Structures Using C and C++ (2nd Edition) by Yedidyah Langsam, Moshe J. Augenstein and Aaron M. Tenenbaum

Links :