10

Computer
Programming
Quarter IV – Module 7:
Key concepts of Sorting Algorithms

"Designed by macrovector / Freepik"

Computer Programming– Grade 10
Self-Learning Module
First Edition, 2020

Republic Act 8293, section 176 states that: No copyright shall subsist in any work
of the Government of the Philippines. However, prior approval of the government agency or
office wherein the work is created shall be necessary for exploitation of such work for profit.
Such agency or office may, among other things, impose as a condition the payment of
royalties.

Borrowed materials (i.e., songs, stories, poems, pictures, photos, brand names,
trademarks, etc.) included in this module are owned by their respective copyright holders.
Every effort has been exerted to locate and seek permission to use these materials from
their respective copyright owners. The publisher and authors do not represent nor claim
ownership over them.

Published by the Department of Education – Regional Office VIII

Regional Director: Ramir B. Uytico EdD, CESO IV
Assistant Regional Director: Arnulfo M. Balane, CESO V

Development Team of the Module

Writers: IMELDA P. ARCILLAS; ERDENAN S. LABRADOR (New Ormoc City National
High School
Language Editor/s: RAYMUND M. PEPITO (New Ormoc City National High School)
Content Editors: LOIE APRIL JASMIN PAHOLIO / ROBIN ANDREW S. YBOA
Illustrators:
Layout Artist: Erdenan S. Labrador
Management Team:
Rosemarie M. Guino EdD,OIC – Chief, CLMD
Ryan R. Tiu EdD, EPS, CLMD – Science
Joy B. Bihag, EPS, CLMD – LRMS
Jose B. Mondido, Chief, CID
Rosario Canlas, EPS, CID – Science
Francisco Bayon-on. EPS, CID - LRMS

Printed in the Philippines by ________________________

Department of Education –Regional Office VIII

Office Address: Government Center, Candahug, Palo, Leyte

Telefax: 053 - 3233156

E-mail Address: region8@deped.go
Introductory Message
This Self-Learning Module (SLM) is prepared so that you, our dear learners,
can continue your studies and learn while at home. Activities, questions,
directions, exercises, and discussions are carefully stated for you to understand
each lesson.

Each SLM is composed of different parts. Each part shall guide you step-by-
step as you discover and understand the lesson prepared for you.

At the end of each module, you need to answer the test to self-check your
learning. Answer keys are provided for each activity and test. We trust that you will
be honest in using these.

In addition to the material in the main text, Notes to the Teacher are also
provided to our facilitators and parents for strategies and reminders on how they
can best help you on your home-based learning.

Please use this module with care. Do not put unnecessary marks on any
part of this SLM. Use a separate sheet of paper in answering the exercises and
tests. And read the instructions carefully before performing each task.

If you have any questions in using this SLM or any difficulty in answering
the tasks in this module, do not hesitate to consult your teacher or facilitator.

Thank you.

ii
For the learner:

Welcome to the Self – Learning Module on Design a flowchart of a simple program

of programming language.
The hand is one of the most symbolized part of the human body. It is often used to
depict skill, action, and purpose. Through our hands we may learn, create, and
accomplish. Hence, the hand in this learning resource signifies that you as a
learner is capable and empowered to successfully achieve the relevant
competencies and skills at your own pace and time. Your academic success lies in
your own hands!

This module was designed to provide you with fun and meaningful opportunities
for guided and independent learning at your own pace and time. You will be
enabled to process the contents of the learning resource while being an active
learner.

This module has the following parts and corresponding icons:

This will give you an idea of the skills or

Explore
competencies you are expected to learn in the
module. A brief drill or review to help you link
the current lesson with the previous one. The
new lesson will also be introduced to you in
various ways such as a story, a song, a poem, a
problem opener, an activity, or a situation.
This section provides a brief discussion of the
Learn
lesson. This aims to help you discover and
understand new concepts and skills.

What’s More This comprises activities for independent

practice to solidify your understanding and
skills of the topic. You may check the answers
to the exercises using the Answer Key at the
end of the module.
This includes questions or blank
Apply sentence/paragraph to be filled into process
what you learned from the lesson.

Assess This is a task which aims to evaluate your level

of mastery in achieving the learning
competency.
This contains answers to all activities in the
Answer Key module.

This contains the learner’s reflection. Learners

Reflect
are encouraged to think about the lessons
particularly the parts that went well (they have
understood) and the parts that were weak (they
have difficulty) and write about it briefly.

iii
 Learners can share their thoughts and feeling
about the lessons.

At the end of this module you will also find:

References This is a list of all sources used in
developing this module.
The following are some reminders in using this module:

1. Use the module with care. Do not put unnecessary mark/s on any part of
the module. Use a separate sheet of paper in answering the exercises.
2. Read the instruction carefully before doing each task.
3. Observe honesty and integrity in doing the tasks and checking your
answers.
4. Finish the task at hand before proceeding to the next.
5. Return this module to your teacher/facilitator once you are through with it.
If you encounter any difficulty in answering the tasks in this module, do not
hesitate to consult your teacher or facilitator. Always bear in mind that you are
not alone.

We hope that through this material, you will experience meaningful learning
and gain deep understanding of the relevant competencies. You can do it!

iv
 Explore

Introduction:
A Sorting Algorithm is used to rearrange a given array or list elements
according to a comparison operator on the elements. The comparison operator is
used to decide the new order of element in the respective data structure.
Sorting refers to the operation or technique of arranging and rearranging
sets of data in some specific order. A collection of records called a list where every
record has one or more fields. The fields which contain a unique value for each
record is termed as the key field. For example, a phone number directory can be
thought of as a list where each record has three fields - 'name' of the person,
'address' of that person, and their 'phone numbers'. Being unique phone number
can work as a key to locate any record in the list.
Sorting is the operation performed to arrange the records of a table or list in
some order according to some specific ordering criterion. Sorting is performed
according to some key value of each record.
The records are either sorted either numerically or alphanumerically. The records
are then arranged in ascending or descending order depending on the numerical
value of the key. Here is an example, where the sorting of a lists of marks obtained
by a student in any particular subject of a class.
Sorts are most commonly in numerical or a form of alphabetical (called
lexicographical) order, and can be in ascending (A-Z, 0-9) or descending (Z-A, 9-0)
order.
In other words, a sorted array is an array that is in a particular order. For
example, [a,b,c,d][a,b,c,d] is sorted alphabetically, [1,2,3,4,5][1,2,3,4,5] is a list of
integers sorted in increasing order, and [5,4,3,2,1][5,4,3,2,1] is a list of integers
sorted in decreasing order.
A sorting algorithm takes an array as input and outputs a permutation of
that array that is sorted.

After going through this module, you are expected to:

Understand the different sorting algorithms

Subtask:
1. Identify the different sorting algorithms
2. Evaluate sorting algorithms
3. Demonstrate the sorting algorithms
4.

1
 Learn

What is a Programming Algorithm?

You can think of a programming algorithm as a recipe that describes the

exact steps needed for the computer to solve a problem or reach a goal. We've all
seen food recipes - they list the ingredients needed and a set of steps for how to
make the described meal. Well, an algorithm is just like that. In computer lingo,
the word for a recipe is a procedure, and the ingredients are called inputs. Your
computer looks at your procedure, follows it to the letter, and you get to see the
results, which are called outputs.

A programming algorithm describes how to do something, and your

computer will do it exactly that way every time. Well, it will once you convert your
algorithm into a language it understands!

However, it's important to note that a programming algorithm is not

computer code. It's written in simple English (or whatever the programmer speaks).
It doesn't beat around the bush--it has a start, a middle, and an end. In fact, you
will probably label the first step 'start' and the last step 'end.' It includes only what
you need to carry out the task. It does not include anything unclear, often called
ambiguous in computer lingo, that someone reading it might wonder about.

It always leads to a solution and tries to be the most efficient solution we can
think up. It's often a good idea to number the steps, but you don't have to. Instead
of numbered steps, some folks use indentation and write in pseudocode, which is a
semi-programming language used to describe the steps in an algorithm. But, we
won't use that here since simplicity is the main thing. Other folks just use a
diagram called a flowchart, which we will discuss soon.

Programming Algorithm Example

An algorithm can be written as a list of steps using text or as a picture with
shapes and arrows called a flowchart. We will make one of each which you will see
here:

2
 Start

Input
Name, HrlyRate,
HrsWork, Deductn

GrossPay = HrlyRate * HrsWork

NetPay = GrossPay - Deductn

Print
Name, GrossPay,
Netpay

End

3
Notice how the top of our example is just a numbered list of steps using plain
English, stating exactly what we want the procedure to do (no more, no less). The
bottom is the very same algorithm, but this time, we used shapes and arrows in a
flowchart (like a map of the route), so that a reader can visualize the journey.
That's a nice thing here, because in one of our steps (step 7) a decision must be
made and, depending on the result of that decision, our steps may not go in order
from start to end.

Let's take a quick run through our little recipe:

1. Step 1 is really just a reminder that this is a procedure with a beginning and an
end.

2. In step 2, we make a place in the computer to store what the user types in, also
called a variable

3. In step 3, we clear this variable because we might need to use it again and don't
want the old contents mixed in with the new.

4. In step 4, we prompt the user for an email address

5. In step 5, we stick it in our nifty variable.

6. In step 6, we tell our computer to take a close look at this email address-- is it
really an email address?

7. In step 7, we have to go back to step 3 to clear the variables

8. Lastly for our step 8 it will terminate or end the program.

Categories of Sorting
The techniques of sorting can be divided into two categories. These are:

 Internal Sorting

 External Sorting

Internal Sorting: If all the data that is to be sorted can be adjusted at a time in the
main memory, the internal sorting method is being performed.

External Sorting: When the data that is to be sorted cannot be accommodated in

the memory at the same time and some has to be kept in auxiliary memory such as
hard disk, floppy disk, magnetic tapes etc, then external sorting methods are
performed.

4
The Complexity of Sorting Algorithms
The complexity of sorting algorithm calculates the running time of a function in
which 'n' number of items are to be sorted. The choice for which sorting method is
suitable for a problem depends on several dependency configurations for different
problems. The most noteworthy of these considerations are:

 The length of time spent by the programmer in programming a specific

sorting program
 Amount of machine time necessary for running the program

 The amount of memory necessary for running the program

The Efficiency of Sorting Techniques

To get the amount of time required to sort an array of 'n' elements by a
particular method, the normal approach is to analyze the method to find the
number of comparisons (or exchanges) required by it. Most of the sorting
techniques are data sensitive, and so the metrics for them depends on the order in
which they appear in an input array.
Various sorting techniques are analyzed in various cases and named these cases as
follows:

 Best case

 Worst case

 Average case

Hence, the result of these cases is often a formula giving the average time
required for a particular sort of size 'n.' Most of the sort methods have time
requirements that range from O (nlog n) to O(n2).

Types of Sorting Techniques

 Bubble Sort

 Insertion Sort

 Insertion Sort

 Merge Sort

5
Bubble Sort Algorithm
Bubble Sort is used to arrange N elements in ascending order, and for that, you
have to begin with 0th element and compare it with the first element. If the
0th element is found greater than the 1st element, then the swapping operation will
be performed, i.e., the two values will get interchanged. In this way, all the
elements of the array get compared.
Below given figure shows how Bubble Sort works:

Figure 1.1 Example of how bubble sorting works.

6
Algorithm for Bubble Sort

1. algorithm Bubble_Sort (list)

2. Pre: list != fi
3. Post: list is sorted in ascending order for all values
4. for i <- 0 to list:Count - 1
5. for j <- 0 to list:Count - 1
6. if list[i] < list[j]
7. Swap(list[i]; list[j])
8. end if
9. end for
10. end for
11. return list
12. end Bubble_Sort

Insertion Sort Algorithm

Insertion sort is a to some extent an interesting algorithm with an expensive

runtime characteristic having O(n2). This algorithm can be best thought of as a
sorting scheme which can be compared to that of sorting a hand of playing cards,
i.e., you take one card and then look at the rest with the intent of building up an
ordered set of cards in your hand.

Algorithm for Insertion Sort

1. algorithm Insertion_sort(list)
2. Pre: list 6= fi
3. Post: list has been sorted into values of ascending order
4. unsorted <- 1
5. while unsorted < list.Count
6. hold <- list[unsorted]
7. i à unsorted - 1
8. while i >= 0 and hold < list[i]
9. list[i + 1] <- list[i]
10. i <- i - 1
11. end while
12. list[i + 1] <- hold
13. unsorted <- unsorted + 1
14. end while
15. return list
16. end Insertion_sort

7
Example of Insertion Sort in Programming:
#include <iostream>
#include <conio.h>

int main()
{
int a[16], i, j, k, tmp;
cout << "enter the number of elements\n";
for (i = 0; i < 6; i++) { cin >> a[i];
}
for (i = 1; i < 6; i++) { for (j = i; j >= 1; j--) {
if (a[j] < a[j - 1]) {
tmp = a[j];
a[j] = a[j - 1];
a[j - 1] = tmp;
}
else
break;
}
}
cout << "sorted array\n" << endl;
for (k = 0; k < 6; k++) {
cout << a[k] << "\t";
}

8
*Output of the insertion sort in programming

Selection Sort Algorithm

The selection is a straightforward process of sorting values. In this method,
to sort the data in ascending order, the 0th element is compared with all other
elements. If the 0th element is found to be greater than the compared element, the
two values get interchanged. In this way after the first iteration, the smallest
element is placed at 0th position. The technique is repeated until the full array gets
sorted.

The below-given figure shows how Selection Sort works:

Figure 1.2 Selection Sort Technique

9
Example of selection sort in programming:

#include <iostream>
using namespace std;

int main()
{
int a[100], i, n, p, k, min, loc, tmp;

cout << "\n------------ SELECTION SORT ------------ \n\n";

cout << "Enter No. of Elements:"; cin >> n;

cout << "\nEnter Elements:\n";

for (i = 1; i <= n; i++) { cin >> a[i];
}

for (p = 1; p <= n - 1; p++) // Loop for Pass

{
min = a[p]; // Element Selection
loc = p;

for (k = p + 1; k <= n; k++) // Finding Min Value { if (min >

a[k]) {
min = a[k];
loc = k;
}
}

tmp = a[p];
a[p] = a[loc];
a[loc] = tmp;
}
cout << "\nAfter Sorting: \n";
for (i = 1; i <= n; i++) {
cout << a[i] << endl;
}
}

10
 Output:

Figure 1.3. Output of the selection sort in programming

Merge Sort Algorithm

Merge sort is another sorting technique and has an algorithm that has a
reasonably proficient space-time complexity - O(n log n) and is quite trivial to
apply. This algorithm is based on splitting a list, into two comparable sized lists,
i.e., left and right and then sorting each list and then merging the two sorted lists
back together as one.

Merge sort can be done in two types both having similar logic and way of
implementation. These are:

 Top down implementation

 Bottom up implementation

11
Below given figure shows how Merge Sort works:

Figure 1.4. Merge Sort Technique

Algorithm for Merge Sort

1. algorithm Merge_Sort(list)
2. Pre: list 6= fi
3. Post: list has been sorted into values of ascending order
4. if list.Count = 1 // when already sorted
5. return list
6. end if
7. m <- list.Count = 2
8. left <- list(m)
9. right <- list(list.Count - m)
10.for i <- 0 to left.Count - 1
11.left[i] <- list[i]
12.end for
13.for i <- 0 to right.Count -1
14.right[i] <- list[i]
15.end for
16.left <- Merg_Sort(left)
17.right <- Merge_Sort(right)
18.return MergeOrdered(left, right)

12
19.end Merge_Sort

Engage

Directions: Choose only the letter of your choice. Write your answers on a ¼
piece intermediate paper.

1. What are the correct intermediate steps of the following data set when it
is being sorted with the bubble sort? 15,20,10,18

A. 15,10,20,18 -- 15,10,18,20 -- 10,15,18,20

B. 10, 20,15,18 -- 10,15,20,18 -- 10,15,18,20

C. 15,20,10,18 -- 15,10,20,18 -- 10,15,20,18 -- 10,15,18,20

D. 15,18,10,20 -- 10,18,15,20 -- 10,15,18,20 -- 10,15,18,20

2. In a bubble sort structure, there is/are?

A. A single for loop B. Three for loops, all separate

C. A while loop D. Two for loops, one nested in the other

3. What is the maximum number of comparisons if there are 5 elements in array x?

A. 10 B. 2 C. 5 D. 25

4. What is the max. number of comparisons that can take place when a bubble sort
is implemented? Assume there are n elements in the array?

A. (1/2)(n-1) B. (1/2)n(n-1) C. (1/4)n(n-1) D. None of the above

5. What are the worst case and best case time complexity of bubble sort
consequently?

A. O(n), O(n2) B. O(n2), O(n3) C. O(n), O(n3) D. None of the above

13
 Apply

Directions: Sort this array in an increasing order. Write the correct

answer with appropriate solution.

Problem1:

1 9 11 6 15 2

Problem 2:

2 7 4 1 5 3

Problem 3:

8 2 4 1 3

Problem 4:

15 20 10 18

Problem 5:

5 1 6 2 4 3

14
 Assess

Instructions: Solve the following and write your answer on 1 whole piece of
paper.

1. What are the correct intermediate steps of the following data set
when it is being sorted with the Bubble Sort? 5,6,1,9,7, 12?
Write your solution.

2. What are the correct intermediate steps of the following data set
when it is being sorted with the Selection Sort? 2,8,5,3,9,4,1?
Write your solution.

3. What are the correct intermediate steps of the following data set
when it is being sorted with the Merge Sort? 2,8,5,3,9,4,1,7?
Write your solution.

4. What are the correct intermediate steps of the following data set
when it is being sorted with the Insertion Sort? 2,8,5,3,9,4?
Write your solution.

Reflect

Guide Questions:
1. How important is the sorting algorithm?
2. Which algorithm finds you the easiest way? Why?

15
Answer Key

Engage

1. A
2. D
3. A
4. C
5. A

Apply

Solution no. 1

10 9 11 6 15 2

9 10 11 6 15 2

9 10 6 11 15 2

9 10 6 11 2 15

Solution no. 2

2 7 4 1 5 3
2 4 7 1 5 3
2 4 1 7 5 3
2 4 1 5 3 7

Solution no. 3

8 2 4 1 3
2 8 4 1 3
2 4 8 1 3
2 4 1 8 3
2 4 1 3 8

Solution no. 4

8 2 4 1 3
2 8 4 1 3
2 4 8 1 3
2 4 1 8 3
2 4 1 3 8

Solution no. 5

15 20 10 18
15 10 20 18
15 10 18 20
10 15 18 20

16
 Assess:

1. Bubble Sort Solution

5 6 1 9 7 12
5 6 1 9 7 12
5 1 6 9 7 12
5 1 9 6 7 12
1 5 9 6 7 12
1 5 6 9 7 12
1 5 6 7 9 12

2 Selection Sort Solution

2 8 5 3 9 4 1
1 8 5 3 9 4 2
1 2 5 3 9 4 8
1 2 3 5 9 4 8
1 2 3 4 9 5 8
1 2 3 4 5 9 8
1 2 3 4 5 8 9

3. Merge Sort Solution

2 8 5 3 9 4 1 7
2 8 5 3 9 4 1 7
2 8 3 5 9 4 1 7
2 8 3 5 4 9 1 7
2 3 5 8 1 4 7 9
1 2 3 4 5 7 8 9

4. Insertion Sort Solution

2 8 5 3 9 4
2 5 8 3 9 4
2 3 5 8 9 4
2 3 5 8 9 4
2 3 4 5 8 9

References

17
Meinecke, Lonny. "What Is An Algorithm In Programming? - Definition, Examples & Analysis".
Study.Com. Accessed 10 February 2021. https://study.com/academy/lesson/what-is-an-algorithm-
in-programming-definition-examples-analysis.html.

"Merge Sort Quiz - Proprofs Quiz". Proprofs.Com. Accessed 10 February 2021.

https://www.proprofs.com/quiz-school/story.php?title=merge-sort-quiz.

"Sorting Techniques In Data Structures". W3schools.In. Accessed 10 February 2021.

https://www.w3schools.in/data-structures-tutorial/sorting-techniques/.

18
For inquiries or feedback, please write or call:

Department of Education – Regional Office VIII – Curriculum and Learning

Management Division (CLMD) - Learning Resources Management Section (LRMS)

Government Center, Candahug, Palo, Leyte, 6501

Telefax: (053) 323-3156; 323-3854; 824-4627

Email Address: *region8@deped.gov.ph

*clmd.region8@deped.gov.ph *lrmds.region8@deped.gov.ph

19