Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
CC 104: Data Structure and Algorithm REYLAN [Link] | 1
VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
Module 3
Insertion Sort and Bubble Sort Algorithm
Introduction
In this module, you shall be introduced to the sorting algorithms
which include Insertion Sort and Bubble Sort. The sorting algorithm is a
method by which students use in order to understand the different sorting
processes.
Learning Objectives:
1. To provide the knowledge of Insertion and Bubble Sort Algorithms;
2. To develop the skill in Insertion and Bubble sorting algorithms;
3. To teach how to create a representation showing the process of
Insertion and Bubble sorting algorithms.
Learning Outputs: Upon completion of this Module, you shall be able to:
1. Describe the Insertion and Bubble sorting algorithms;
2. Write a solution to a programming problem using Insertion and
Bubble sorting algorithm;
3. Create a representation showing the process of Insertion and Bubble
sorting algorithms.
Discussion
A. Insertion Sort Algorithm
Consider you have 10 cards out of a deck of cards in your hand. And
they are sorted, or arranged in the ascending order of their numbers.
If I give you another card, and ask you to insert the card in just the right
position, so that the cards in your hand are still sorted. What will you do?
Well, you will have to go through each card from the starting or the back and
find the right position for the new card, comparing its value with each card.
Once you find the right position, you will insert the card there.
Similarly, if more new cards are provided to you, you can easily repeat the
same process and insert the new cards and keep the cards sorted too.
This is exactly how insertion sort works. It starts from the index 1(not 0),
and each index starting from index 1 is like a new card, that you have to
place at the right position in the sorted sub array on the left.
Following are some of the important characteristics of Insertion Sort:
1. It is efficient for smaller data sets, but very inefficient for larger lists.
2. Insertion Sort is adaptive, that means it reduces its total number of
steps if a partially sorted array is provided as input, making it efficient.
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
3. It is better than Selection Sort and Bubble Sort algorithms. Page | 2
4. Its space complexity is less. Like bubble Sort, insertion sort also
requires a single additional memory space.
5. It is a stable sorting technique, as it does not change the relative
order of elements which are equal.
How Insertion Sort Works?
Following are the steps involved in insertion sort:
1. We start by making the second element of the given array, i.e. element
at index 1, the key. The key element here is the new card that we need
to add to our existing sorted set of cards (remember the example with
cards above).
2. We compare the key element with the element(s) before it, in this
case, element at index 0:
o If the key element is less than the first element, we insert
the key element before the first element.
o If the key element is greater than the first element, then we
insert it after the first element.
3. Then, we make the third element of the array as key and will compare
it with elements to its left and insert it at the right position.
4. And we go on repeating this, until the array is sorted.
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Let's consider an array with values {5, 1, 6, 2, 4, and 3} Page | 3
Below, we have a pictorial representation of how bubble sort will sort the
given array.
As you can see in the diagram above, after picking a key, we start iterating over the
elements to the left of the key.
We continue to move towards left if the elements are greater than the key element and
stop when we find the element which is less than the key element.
And, insert the key element after the element which is less than the key element.
Process of Insertion Sort
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Example 1. Page | 4
Input Numbers: 5 4 3 2 1
Final Output: 1 2 3 4 5
Original Sequence
5 4 3 2 1
5 4 3 2 1
You have to compare the second element of the array on its left element, if
the two numbers are not in correct position swap the numbers in right
places. Then if the two numbers are in correct arrangement there will be no
changes
4 5 3 2 1
If you already swap the smallest element, it is considered sorted. Proceed to
the succeeding elements in the array. This time you will be comparing 3 to
its left elements. Then place the 3 in the right place. Then repeat the process
until the elements are sorted.
4 5 3 2 1
4 3 5 2 1
4 3 5 2 1
3 4 5 2 1
3 4 5 2 1
3 4 5 2 1
3 4 2 5 1
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 5
3 4 2 5 1
3 2 4 5 1
3 2 4 5 1
2 3 4 5 1
2 3 4 5 1
2 3 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5 Final Output of the process
Example 2.
Input Numbers: 6 9 4 2 8 5 3 1 7
Final Output: 1 2 3 4 5 6 7 8 9
6 9 4 2 8 5 3 1 7 Original Sequence
1 7 6 and 9 are in right places so
there will be no
changes
6 9 4 2 8 5 3 1 7
This time we need to put 4 in
the right place. We need to
insert 4 before 6. This will
give you 2 iterations.
6 4 9 2 8 5 3 1 7
4 6 9 2 8 5 3 1 7
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT
4 6 9 2 8 5 3 1 7 INSTRUCTOR 3
First Semester AY 2020-21
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
This time we need to arrange Page | 6
2 in the right place. Follow the
steps above..
4 6 2 9 8 5 3 1 7
4 2 6 9 8 5 3 1 7
2 4 6 9 8 5 3 1 7
Now 8 will be placed in the
right
2 4 6 9 8 5 3 1 7 place.
2 4 6 8 9 5 3 1 7
Now 5 will be placed in the
right
2 4 6 8 9 5 3 1 7 place.
2 4 6 8 5 9 3 1 7
2 4 6 5 8 9 3 1 7
2 4 5 6 8 9 3 1 7
Now 3 will be the next to be
2 4 5 6 8 9 3 1 7 placed in the right
place
2 4 5 6 8 3 9 1 7
CC 104: Data Structure and Algorithm REYLAN B. VILI
2 4 5
NIPSCLC-BSIT 6 3 8 9 1 7 INSTRUCTOR 3
First Semester AY 2020-21
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 7
2 4 3 5 6 8 9 1 7
2 3 4 5 6 8 9 1 7
2 3 4 5 6 8 9 1 7 1 will be processed to put in the
right places
2 3 4 5 6 8 1 9 7
2 3 4 5 6 1 8 9 7
2 3 4 5 1 6 8 9 7
2 3 4 1 5 6 8 9 7
2 3 1 4 5 6 8 9 7
2 1 3 4 5 6 8 9 7
1 2 3 4 5 6 8 9 7
1 2 3 4 5 6 8 9 7 Last element will
be 7.
1 2 3 4 5 6 8 7 9
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
1 2 3 4 5 6 7 8 9
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 8
Final Output
B. Bubble Sort
Bubble Sort is a simple algorithm which is used to sort a given set
of n elements provided in form of an array with n number of elements.
Bubble Sort compares all the element one by one and sort them based on
their values.
If the given array has to be sorted in ascending order, then bubble sort will
start by comparing the first element of the array with the second element, if
the first element is greater than the second element, it will swap both the
elements, and then move on to compare the second and the third element,
and so on.
If we have total n elements, then we need to repeat this process for n-
1 times.
It is known as bubble sort, because with every complete iteration the
largest element in the given array, bubbles up towards the last place or the
highest index, just like a water bubble rises up to the water surface.
Sorting takes place by stepping through all the elements one-by-one and
comparing it with the adjacent element and swapping them if required.
Implementing Bubble Sort Algorithm
Following are the steps involved in bubble sort (for sorting a given array in
ascending order):
1. Starting with the first element (index = 0), compare the current
element with the next element of the array.
2. If the current element is greater than the next element of the array,
swap them.
3. If the current element is less than the next element, move to the next
element. Repeat Step 1.
Let's consider an array with values {5, 1, 6, 2, 4, 3}
Below, we have a pictorial representation of how bubble sort will sort the
given array.
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 9
So as we can see in the representation
above, after the first iteration, 6 is placed at the last index, which is the correct position
for it.
Similarly after the second iteration, 5 will be at the second last index, and so on.
Example 1. Bubble Sort
Input Numbers: 5 4 3 2 1
Final output: 1 2 3 4 5
5 4 3 2 1 You should have to compare the two
changes will be made. Repeat until
elements are sorted.
4 5 3 2 1
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 10
4 5 3 2 1
4 3 5 2 1
4 3 5 2 1
4 3 2 5 1
First complete Pass
4 3 2 1 5 (highest number is on the right place)
4 3 2 1 5
3 4 2 1 5
3 4 2 1 5
3 2 4 1 5
3 2 4 1 5
Second Complete Pass
3 2 1 4 5
3 2 1 4 5
2 3 1 4 5
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First
2 Semester
3 1 AY 4 2020-21
5
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 11
2 1 3 4 5 Third Complete Pass
2 1 3 4 5
1 2 3 4 5
Final Complete Pass
Example 2.
Input Numbers: 6 9 4 2 8 5 3 1 7
Final Output: 1 2 3 4 5 6 7 8 9
6 9 4 2 8 5 3 1 7
6 9 4 2 8 5 3 1 7 No changes because it’s in the
right position.
6 9 4 2 8 5 3 1 7
6 4 9 2 8 5 3 1 7
6 4 9 2 8 5 3 1 7
6 4 2 9 8 5 3 1 7
6 4 2 9 8 5 3 1 7
6 4 2 8 9 5 3 1 7
6 4 2 8 9 5 3 1 7
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 12
6 4 2 8 5 9 3 1 7
1 7
6 4 2 8 5 3 9 1 7
6 4 2 8 5 3 9 1 7
6 4 2 8 5 3 1 9 7
6 4 2 8 5 3 1 9 7
First Complete Pass
6 4 2 8 5 3 1 7 9
6 4 2 8 5 3 1 7 9
4 6 2 8 5 3 1 7 9
4 6 2 8 5 3 1 7 9
4 2 6 8 5 3 1 7 9
4 2 6 8 5 3 1 7 9
4 2 6 8 5 3 1 7 9
4 2 6 5 8 3 1 7 9
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
4
First 2 6 AY
Semester 5 2020-21
8 3 1 7 9
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 13
Second Complete Pass
4 2 6 5 3 1 7 8 9
2 4 6 5 3 1 7 8 9
2 4 6 5 3 1 7 8 9
2 4 6 5 3 1 7 8 9
2 4 5 6 3 1 7 8 9
2 4 5 6 3 1 7 8 9
2 4 5 3 6 1 7 8 9
2 4 5 3 6 1 7 8 9
Third Complete Pass
2 4 5 3 1 6 7 8 9
2 4 5 3 1 6 7 8 9
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
2 4 5 3 1 6 7 8 9
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 14
Fourth Complete Pass
2 4 3 1 5 6 7 8 9
2 4 3 1 5 6 7 8 9
2 3 4 1 5 6 7 8 9
2 3 4 1 5 6 7 8 9
2 3 1 4 5 6 7 8 9
Fifth Complete Pass
2 3 1 4 5 6 7 8 9
2 3 1 4 5 6 7 8 9
Sixth Complete Pass
2 1 3 4 5 6 7 8 9
2 104:
CC 1 Data
3 Structure
4 5 and6Algorithm
7 8 9 REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
1 2 3 4 5 6 7 8 9
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 15
Final Complete Pass
Summary
The sorting algorithm provides a complete representation on how the
different sorting algorithms work. This is also a method showing more types
of sorting which being used by the computer in sorting files.
Assessment
1. Describe in not less than 4 sentences the process of Insertion and Bubble
Sort Algorithms.
(5 points for each correct answer)
Answer the following Sorting Algorithm problems.
Instructions: Write the solution to these sorting problems using the Insertion
and Bubble Sort Algorithms. Write your answers in the space provided.
Insertion Sort
1. 987463512
2. 548762193
3. 648723519
4. KBAULEHIO
Bubble Sort
1. 987463512
2. 548762193
3. 648723519
4. KBAULEHIO
Your answers will be evaluated using these criteria.
Correct showing of process – 5 points
Correct Output – 5 points
Note: For video Tutorial just search in YouTube the Insertion and Bubble Sort
and look for Michael Sambol Channel.
Reference
[Link]
structures
-End of Module 3
CC 104: Data Structure and Algorithm REYLAN B. VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21