CSC 2200 Lecture Notes - Lecture 20: Sorting Algorithm, Insertion Sort
16 views3 pages
19 Jul 2018
School
Department
Course
Professor
CSC 2200 Lecture 20
Insertion Sort
• Insertion Sort
o In-place comparison-based sorting algorithm
o Sublist is maintained which is always sorted
o The lower part of an array is maintained to be sorted
o An element which is to be inserted in this sorted sub-list, has to find its
appropriate place an then it has to be inserted there
o The array is searched sequentially and unsorted items are moved and inserted
into the sorted sub-list (in the same array)
o This algorithm is not suitable for large data sets as its average and worst case are
of O(n^2), where n is the number of items
• How it works?
o We take an unsorted array for example
▪
o Compares the first two elements
▪
o It finds that 14 and 33 are in order. For now, 14 is in the sorted sub-list
o IT then moves ahead and compares 33 with 27, since 33 is not in the correct
position it swaps with 27