Scribd
Upload
27 views14 pages

Insertion Sort

The document discusses three sorting techniques: insertion sort, selection sort, and merge sort. Insertion sort builds a sorted array from left to right by inserting each element into its correct position in the sorted portion. Selection sort repeatedly selects the smallest element from the unsorted portion and swaps it with the first element. Merge sort divides a list into single element sublists and then repeatedly merges the sublists in sorted order until one list remains.

Uploaded by

Senthil Kumar Madhavan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
27 views14 pages

Insertion Sort

The document discusses three sorting techniques: insertion sort, selection sort, and merge sort. Insertion sort builds a sorted array from left to right by inserting each element into its correct position in the sorted portion. Selection sort repeatedly selects the smallest element from the unsorted portion and swaps it with the first element. Merge sort divides a list into single element sublists and then repeatedly merges the sublists in sorted order until one list remains.

Uploaded by

Senthil Kumar Madhavan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Sorting Techniques

Unit 4
Topics

• Insertion Sort

• Selection Sort

• Merge Sort
INSERTION SORT
IDEA:

 Build a sorted array from the left to right

 At each step, the algorithm takes an element from the unsorted portion and

inserts it into its correct position in the sorted portion.

 The process is repeated until the entire array is sorted.


WORKING

Initial State Iterative Process Repeat

 The first element is  Take an element from  Repeat these steps


the unsorted portion.
considered to be in  Compare it with until all elements are
elements in the
the sorted portion sorted, moving from in the sorted portion,
 And the rest of the right to left, until the and the array is fully
correct position is
array is considered found. sorted.
 Insert the element
unsorted. into its correct
position in the sorted
position.
EXAMPLE

 Example: [12, 11, 13, 5, 6]

 Initial state 12 is sorted, 11, 13, 5, 6 are unsorted.

 Take 11 from the unsorted portion, compare with 12 and insert it before
12. [11,12] is sorted, [13, 5, 6] are unsorted.

 Take 13, compare with 12, insert after 12. [11, 12, 13], [5,6]

 Take 5, compare with 13, 12 & 11, insert before 11. [5, 11, 12, 13], [6]

 Take 6, compare with 13, 12 insert before 12. [5, 6, 11, 12, 13]
EXAMPLE:
 insertion_sort:
 Takes a lst as input & sorts it in-place
using insertion sort algorithm.
 The outer loop iterates over the
elements of the list, starting from
second element (i=1)
 The inner ’while’ loop compares the
current element (key) with the
elements before it,
 Moving larger elements to the right
until the correct position for ‘key’ is
found.
 The key is then placed at its correct
position in the array.
SELECTION SORT
IDEA

 Select repeatedly the smallest/largest element from the unsorted portion of the
list and swaps it with the first element of unsorted part.

 Repeat this for remaining unsorted portion.


WORKING

SELECTION SWAP REPEAT & CONTINUE

 Find the minimum  Swap the minimum  Move the boundary


element in the between the sorted &
element with the first
unsorted array. unsorted portions one
element of the element to the right.

unsorted array.  Repeat steps 1 – 3 until


the entire array is
sorted.
SELECTION SORT
MERGE SORT
IDEA

 Divide the unsorted list into n sublists, each containing one element.

 Repeatedly merge sublists to produce new sorted sublists until there is only one
sublist remaining.
MERGE SORT

You might also like