Computing Students - Computer Science Degree Notes
Home Contact Shop Notes Questions Programming Links Dictionary Coursework FORUM Tutors
  Recommended Amazon Searches: Computer Science | Computing | Computer Systems | Database | Computing Revision  

Notes > Computation and Algorithms > Insertion Sort and Sorting

An insertion sort involves processing a single value in each step. An order list is maintained throughout the sort process and a new element is added to that list each step. After each step, the inserted element will be in is correct place in the list. The following example shows how the insertion sort works:

The list "9,7,3,5,6" needs to be sorted from lowest to highest. The following steps are carried out:

  • Step 1 - get first value from list (9)
  • Step 2 - get second value from list (7) and compare to first value (9)
    • If second value smaller than first value, place second value in front of first value (7,9)
  • Step 3 - get third value from list (3) and compare to tail value (9) of current ordered list (7,9)
    • If new element (3) smaller than tail value (9), place new element in front of tail value (7,3,9)
    • If new element (3) smaller than first value (7), place new element in front of first value (3,7,9)
  • Step 4 - get fourth value from list (5) and compare to each element in current ordered list (3,7,9) in a similar fashion to Step 3
    • New ordered list is (3,5,7,9)
  • Step 5 - get fifth value from list (6) and compare to each element in current ordered list (3,5,7,9) in a similar fashion to Step 3
    • When 6 is compared to 5, 6 is placed in the list to create the final sorted list: 3,5,6,7,9

Note that in the last step, 6 does not need to be compared to 3. This is because it is known that any value before 5 will be less than 5 due to the previous steps being carried out.

Search for "Insertion Sort" on: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "Insertion Sort" on the rest of Computing Students: Insertion Sort






Home | Contact | Shop | Notes | Questions | Programming | Links | Dictionary | Coursework | Tutors Sponsored Links: Affiliate Program Articles | Computer Science Definitions | CS Degree Notes
Copyright © 2005-2009 ComputingStudents.com
This site is to be used in accordance with the ComputingStudents.com User Agreement
High Wycombe Web Design