CSC 2200 Lecture Notes - Lecture 20: Sorting Algorithm, Insertion Sort

16 views3 pages
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
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.