V-Lab @ ANDC

Insertion Sort

Aim

As sorting is a fundamental task in computing, the need is to understand its functionality, working and implementation. Different methods of sorting are available. The aim of this virtual lab is to explain the simplest incremental sorting method insertion sort, with the help of examples.

Theory

The working of insertion sort is similar to that of sorting of playing cards in hands. Cards are divided into two parts viz. sorted and unsorted. Initially, first card in hand is the only card in sorted part and remaining cards constitute the unsorted part. Subsequently, the first card from the unsorted part is picked and placed in sorted part at the appropriate position that leads to expansion of sorted part and reduction of the unsorted part of the cards.



Team

Mr. Nilesh Pandey, B.Sc(H) Computer Science, II year,
Ms. Ananya Shukla, B.Sc(H) Computer Science, II year,
Mr. Amitesh Kumar Singh, B.Sc(H) Computer Science, II year.

Mentors:
Prof. Sharanjit Kaur,
Ms. Gunjan Rani

  • A stable algorithm because of maintaining the relative order of elements.
  • An incremental algorithm as it places the elements in sorted position incrementally in the order of their appearance in the list
  • Time complexity in worst case is O(n2) when the input list is in reverse order
  • Time complexity in best case is O(n) where the input list is already sorted.
  • The space complexity is O(1).

    • Insertion Sort Algorithm

    In order to sort a list/array arr with n: number of elements in ascending order, observe the following points.
    • Initially sorted part is arr[0] and unsorted part of the array is arr[1] to arr[n-1].
    • For each element in the unsorted part, do the following in the order of their appearance:
      • Take the first element in the unsorted part as Key and compare with its predecessor (the last element in the sorted part)
      • In case Key is equal or greater than the predecessor, no change is required as elements are already in arranged order.
      • Else, keep on shifting the sorted list by one position to the right till the smaller element in the sorted list is found or end of sorted list is reached
      • Place the Key element just after the smallest element found or at beginning of the list, otherwise.
    • After each iteration, sorted part is expanded by one element by its placement at the appropriate position and the unsorted part is reduced by one element

    Example

    Input: 15, 9, 30, 10, 1
    Expected Output: 1, 9, 10, 15, 30
    Sorting cards

    Working

    Let's go
    Please switch to larger screen to understand this section!

    Procedure

    Simulation is divided into two modules. The first module allows the user to step-by-step analyze the working of the algorithm on arrays. In the next module, some exercises are provided so that the user can have a hands-on experience with the algorithm.

    Steps of Simulator:

    1. The screen consists of three partitions, the input partition, the algorithm's code on the second partition, and the output on the third partition.
    2. Read the simulator details and enter the desired input for the number of elements in the array.
    3. Enter the array size (maximum allowed size is 10).
    4. Click on Random elements to generate the array randomly.
    5. Click on Enter elements manually to manually enter the elements of the array.
    6. Click Nextin output section to see execution of code step by step.
    7. The relevant line of the code will be highlighted as it executes.
    8. The local variables will be shown in the Output Panel with their values.
    Procedure

    Try Yourself Module:

    1. Click on Try Yourself to try some exercises based on the algorithm.
    2. Select the exercise number from the left navigation pane.
    3. Type your answer in the highlighted text box.
    4. Click Submit Answer to submit the answer.
    5. Click Show Answer to display the correct answer.
    Procedure

    Simulation

    Benifits Of
    Our Simulation

    You will see a line by line execution of code i.e. how each line of insertion sort algoritm affects the unsorted array in order to sort it.

    Try Yourself section presents some incomplete code snippets. You will try and complete those.

    Try It

    Quiz

    Welcome to our quiz preparation module! We want you to feel confident and well-prepared before you attempt our quiz. By completing the listed sections, you'll be well-prepared to tackle our quiz with confidence. We'll be with you every step of the way, providing clear instructions and guidance to help you succeed. Good luck, and have fun!

    Please check the boxes, only if you have gone through these sections else complete first.





    LET'S TACKLE

    References

    reference

    Team

    Mr. Shahnawaj Khan, B.Sc(H) Computer Science.

    Mentors:
    Prof. Sharanjit Kaur,
    Ms. Nishu Singh