Review Note

Last Update: 03/13/2024 10:56 AM

Current Deck: IIIT Nagpur::2nd Semester::5. Data Structures::L-06 Sorting Techniques

Published

Currently Published Content

Front

Insertion Sort

Back

Insertion Sort
• In-place comparison-based sorting algorithm
• Works similar to the sorting of Playing cards
• It is assumed that the first card is already sorted in the
card game, and then we select an unsorted card
• If the selected unsorted card is greater than the first
card, it will be placed at the right side; otherwise, it will
be placed at the left side
• Similarly, all unsorted cards are taken and put in their
exact place

Cont…
• In insertion sort,
• a sub-list is maintained which is always sorted. For
example, the lower part of an array is maintained to be
sorted.
• An element which is to be 'inserted’ in this sorted sub-list, has
to find its appropriate place and then it has to be inserted
there
• The array is searched sequentially and unsorted items are
moved and inserted into the sorted sub-list (in the same
array)

Cont…
• Algorithm
• Step 1 - If the element is the first element, assume that it
is already sorted. Return 1
• Step2 - Pick the next element, and store it separately in
a key
• Step3 - Now, compare the key with all elements in the
sorted array
• Step 4 - If the element in the sorted array is smaller than
the current element, then move to the next element. Else,
shift greater elements in the array towards the right.
• Step 5 - Insert the value
• Step 6 - Repeat until the array is sorted

Cont…

No published tags.

Pending Suggestions

No pending suggestions for this note.