CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

TOPIC NO: 2.2

Common Computing Algorithms

Common Computing Algorithms:

Different problems need different step-by-step methods (algorithms) to solve them. Programmers use different
algorithms for the same problem, depending on their choice. Some algorithms are already developed because
they are useful in solving everyday problems. A few of them are explained below.

Sorting Algorithms:
Sorting algorithms help arrange data in order, either from smallest to largest (ascending) or largest to smallest
(descending). Some common sorting methods include Insertion Sort and Bubble Sort.

a. Insertion Sort Algorithm:

Insertion Sort works by comparing two nearby numbers and placing them in the correct order. The
smallest number is picked and moved to the first position. This process continues until all numbers are
sorted in order.

i. How Insertion Sort Works

Here is a group of numbers that we need to sort in ascending order (smallest to largest).

To make it easier to understand, we use four colors:

 Yellow → Unsorted numbers

 Blue → Numbers being compared
 Green → Sorted numbers
 Red → Numbers that are in the wrong place

At the beginning, all numbers are unsorted:

10 30 22 7 35 15

Since the first number (10) is already correct, we keep it as is.

10 30 22 7 35 15

We pick the second element (30) and compare it with the adjacent element in the sorted array.

10 30 22 7 35 15

Because 30 is larger than 10, it means that the first element is already in the correct order.

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

10 30 22 7 35 15

Now, move to the next element (22) and compare it with the adjacent element in the sorted array
(22 with 30).

10 30 22 7 35 15

Here, 22 is smaller compared to 30. It means 30 is not in the correct position. So, we swap both
elements, 22 with 30.

10 22 30 7 35 15

Along with swapping, we also need to check and compare it with all elements in the sorted array.
Till now, the sorted array contains only one element (10). So, 22 is compared with 10. Here, 22
is greater than 10, so the sorted array remains the same.

Now, we move forward to the next element, which is 7, and compare it with its adjacent element
in the sorted array (30).

10 22 30 7 35 15

Here, 30 is greater than 7, so we swap them.

10 22 7 30 35 15

After swapping, we notice that elements 22 and 7 are not in the correct order.

10 22 7 30 35 15

So, we swap them accordingly.

10 7 22 30 35 15

The elements 10 and 7 are also not in the correct order.

10 7 22 30 35 15

So, we swap them accordingly.

7 10 22 30 35 15

Now, we move to the next element, 35, and compare it with the adjacent element in the sorted
array, which is 30.

7 10 22 30 35 15

Similarly, 35 is compared with the previous element in the sorted array, but there is no change
because they are already sorted.

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

No swapping is required because they are already sorted.

7 10 22 30 35 15

Here we will take the next element that is 15 and compared with its adjacent element which is 35
7 10 22 30 35 15

35 is greater than 15. So, swap them

7 10 22 30 15 35

This swapping will make 15 and 30 unsorted

7 10 22 30 15 35

So, swap them too.

7 10 22 15 30 35

Now, this will make 15 and 22 unsorted

7 10 22 15 30 35

So, swap them again.

7 10 15 22 30 35

Now, the sorting process is complete and array is in correct order.

ii. Insertion Sort in context of Computational Thinking:

Let's solve the Insertion sort by applying the computational thinking properties.

Abstraction (Simplifying the Problem):

Insertion Sort arranges a list by picking one item at a time and placing it in the correct
position among the already sorted items. This process continues until the whole list is
sorted.

Breaking it down (Decomposition):

Steps Involved:

 Pick and Insert: Take an item and place it in the correct position in the sorted
part of the list.
 Finding the Right Spot: Compare the item with others to find where it belongs.
SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)
SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

Recognizing Patterns (Pattern Recognition):

 Repetition: The same steps are repeated for every item.

 Building Step by Step: The list is sorted gradually by inserting items in
order.
 Comparison: Each item is compared to find its correct position.

Algorithm Steps:

1. Start with the second element:

Begin with the second element of the array (assuming the first element is already
“sorted”).
2. Pick the current element:
Select the current element and remember it.
3. Compare with sorted elements:
Compare the current element with the elements in the "sorted" part of the array.
4. Shift larger elements to the right:
If the current element is smaller than the elements in the "sorted" part, shift those
larger elements to the right to create space.
Insert the current element:
5. Place the current element in its correct position in the "sorted" part.
6. Repeat for each element:
Follow these steps for every element, gradually expanding the "sorted" part.

b. Bubble Sort Algorithm:

In the Bubble Sort algorithm, we repeatedly compare and swap adjacent elements if they are not in the
correct order.

 If we want to sort an array in ascending order, the algorithm starts by comparing the first
element with the second.
 If the first element is greater than the second, they are swapped.
 Then, it moves forward to compare the second element with the third, continuing this process
until the largest element reaches the last position in the array.
 This process is repeated (iteration) until the entire list is sorted.

i. Working of Bubble Sort Algorithm:

Consider the following array of elements:

11 30 25 40 7

First Iteration:

Take the first element and compare it with adjacent element.

11 30 25 40 7

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

Here, the first element 11 is smaller than second element 30, so it is already sorted.
Now compare second element 30 with its adjacent element 25.
11 30 25 40 7

Here, 30 is greater than 25, swap them both.

11 25 30 40 7

Now take third element 30 and compare it with next adjacent element 40.
11 25 30 40 7

No Swapping is required because 30 is not greater than 40.

11 25 30 40 7

Now, compare 40 with 7.

11 25 30 40 7

Here, 40 is greater than 7, so swapping is needed.

11 25 30 7 40

(Note: The greatest number 40 has reached at the last place of the array at the end of first
iteration)

Second Iteration:

In second iteration, we will follow the same process.

11 25 30 7 40

11 25 30 7 40

11 25 30 7 40

Here, 30 is greater than 7, so perform swapping.

11 25 7 30 40

11 25 7 30 40

Similarly, second iteration is done.

Third Iteration:

In, third iteration we will perform the same process again.

11 25 7 30 40

11 25 7 30 40

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

Here, 25 is greater than 7, so swapping is needed.

11 7 25 30 40

11 7 25 30 40

11 7 25 30 40

Now, move to next iteration.

Fourth Iteration:

Again follow the same process, here 11 is greater than 7 so swapping is needed.
11 7 25 30 40

The array is completely sorted now.

7 11 25 30 40

ii. Bubble Sort in Context of Computational Thinking:

Abstraction:

Bubble Sort organizes a group of items by repeatedly comparing and swapping two adjacent
items if they are out of order. This process continues until the entire list is sorted.

Decomposition:

Steps Involved:

1. Compare two side-by-side items.

2. Swap them if they are not in the correct order.
3. Keep repeating this process until the list is fully sorted.

Pattern Recognition:

Comparing Pairs: The algorithm focuses on checking and fixing two items at a time.

Repeating Steps: The process of comparing and swapping is done again and again until the list
is sorted.

Multiple Rounds: The algorithm goes through the list several times to sort it completely.

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

Algorithm:

1. Start with the first item in the list.

2. Compare it with the next item:

 If the first item is larger, swap them.

 If the first item is smaller or equal, move to the next pair.

3. Repeat this for every pair in the list until you reach the end.
4. After one round, the biggest item will be at the correct position at the end of the list.

 You don’t need to check this item in the next rounds.

5. Do the same process for the remaining unsorted items in the list.
6. Keep repeating until the entire list is sorted.

 The number of rounds needed is one less than the total number of items.

Comparison of Insertion Sort and Bubble Sort:

Aspect Insertion Sort Bubble Sort

A sorting algorithm that builds A sorting algorithm that
the sorted list one element at a repeatedly compares adjacent
Definition time. elements and swaps them if
needed.
Places each element in its correct Pushes the largest element to the
Approach position by comparing it with end in each pass by swapping
sorted elements. adjacent elements.
Suitable for small or nearly Simple but inefficient for large
Usage sorted data. datasets.
Arranging Playing Cards: Sorting Bubbles in a Glass:
When sorting a hand of cards, Larger bubbles rise to the top of a
you pick one card at a time and glass faster than smaller ones,
place it in its correct position much like the largest element
relative to the cards already "bubbling" to the end of the list.
Real Life sorted.
Examples Organizing Books on a Shelf: Checking Test Scores:
If books are added one by one, Comparing adjacent scores on a
each book is inserted into its whiteboard and swapping them
proper position among already until the list is sorted.
organized books.

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

Searching Algorithms:
Searching algorithms are methods used to find a specific element in a group of items. Common examples are
Binary Search and Linear Search.

a) Binary Search Algorithm:

Binary Search is a fast method for finding an item in a sorted list. It works by repeatedly dividing the
list into two parts until the desired item is found.

i. How does it Work?

1. Start by comparing the middle element of the list with the item you are searching for.
2. If it matches, you’ve found your item.
3. If it’s smaller than the middle element, search in the left half of the list.
4. If it’s larger, search in the right half of the list.
5. Repeat this process until the item is found or the list is fully checked.

Example of Binary Search Algorithm:

We have a sorted list of numbers:

0 1 2 3 4 5 6 7 8
5 8 15 20 30 40 50 60 70

Divide the array into two parts, the middle element is 30

0 1 2 3 4 5 6 7 8
5 8 15 20 30 40 50 60 70

Task: Find the number 50.

Compare 50 with the middle element (30).

50 > 30, so check the right half.

5 6 7 8
40 50 60 70
Again divide the array into two parts.

5 6 7 8
40 50 60 70

Here, middle element = 50. So, match found on 6th Location!

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

ii. Binary Search in Context of Computational Thinking:

Abstraction:
Search for a specific item in a sorted collection by repeatedly dividing the search space in
half until the target item is found or the search space is empty. It efficiently narrows down
the search space by half in each iteration.

Decomposition:

Sub-Processes:

1. Middle Item Check: Examine the middle item to determine if it matches the target.
2. Search Space Division: Divide the search space based on the comparison result.
3. Recursive Process: Repeat the process on the narrowed-down search space.

Pattern Recognition: The core concept is repeatedly reducing the search space by half.

Algorithmic Design:

1. Start with the entire sorted array.

2. Check the middle element of the array.
 If it’s equal to the target value, you're done.
 If it’s greater than the target value, ignore the right half.
 If it’s less than the target value, ignore the left half.
3. Repeat the process on the remaining half.
4. Continue until you find the target value, or the array becomes empty.
b) Linear Search Algorithm:

This is a simple search algorithm; we go through the complete list and match the elements one
by one until the required item is found. If the item is found, then the location of that element is
returned; otherwise, a NULL is returned. This search is also called a sequential search algorithm.
However, there is no compulsion that the array should be sorted.

Example of Linear Search:

Consider the given unsorted array, and we need to find the location of item 77.
0 1 2 3 4
12 7 34 77 100

Start from the first element. Compare the required item 77 with required item 12.
0 1 2 3 4
12 7 34 77 100

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

If it matches, stop; otherwise, continue to the next element. Repeat this process until the
item is found or the entire array is checked.
0 1 2 3 4
12 7 34 77 100

0 1 2 3 4
12 7 34 77 100

0 1 2 3 4
12 7 34 77 100

We found the element 77 on location 3. S0, the output of this algorithm is 3.

Linear Search in Context of Computational Thinking:

Abstraction:
Search for a specific item in a list by checking each item one by one until either
the item is found or the end of the list is reached. This method goes through each
item sequentially.

Decomposition:

1. Starting Point: Begin the search from the first item in the list.
2. Item Checking: Check each item to see if it matches the one you’re looking
for.
3. Stopping Condition: Stop the search when the target item is found or when
the end of the list is reached.

Pattern Recognition:

 Sequential Nature: The search progresses item by item, in order.

 Linear Progression: Moves through the list in a straight line.
 Termination Condition: Stops when the target is found or all items have
been checked.

Algorithmic Design:

1. Start at the beginning of the list.

2. Check if the current item matches the target.

 If it matches, you’ve found the target.

 If not, move to the next item.

3. Repeat this process until the target is found or you reach the end of the list.
4. If you reach the end without finding the item, it means the item is not in
the list.

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

Comparison of Binary Search and Linear Search:

Aspect Binary Search Linear Search

Search Divides the list into halves and Checks each item one by one.
searches.
Method
Requires Yes, the list must be sorted. No, works on both sorted and
unsorted lists.
Sorted List?
Speed Faster for large lists (less Slower for large lists (more
comparisons). comparisons).
How It Works Repeatedly splits the list and Starts from the first item and goes
focuses on the relevant half. to the last.
Number of Reduces the list size by half with Goes through the list item by item.
each step.
Steps
Best for Large sorted lists. Small or unsorted lists.

Real-Life Finding a name in a sorted Searching for your misplaced keys

phonebook or searching for a by checking every room one by
Example word in a dictionary. one.

MULTIPLE CHOICE QUESTIONS (MCQs)

Question A B C D A B C D

Which sorting algorithm

1. repeatedly swaps adjacent Quick Sort Insertion Sort Bubble Sort Merge Sort
elements to sort a list?
Elements are
Elements
What is the key Divide-and- inserted into Recursively
are
2. characteristic of Insertion conquer their correct splits the array
compared in
Sort? approach position in a into halves
pairs only
sorted portion
It performs
Why is Bubble Sort It requires It only works unnecessary
It skips over
3. inefficient for large extra on unsorted comparisons
sorted elements
datasets? memory arrays even in
sorted arrays
In Insertion Sort, what
It is swapped
happens when the element It is inserted at
It is left in with every Sorting
4. being sorted is smaller the beginning
place element in the stops
than all elements in the of the list
sorted portion
sorted portion?
If the array [5, 3, 8, 6, 2] is
sorted using Insertion Sort,
5. [3, 5, 8, 6, 2] [2, 3, 8, 6, 5] [3, 5, 6, 8, 2] [5, 8, 6, 2, 3]
what is the result after the
first two passes?
SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)
SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

Question A B C D A B C D

How many swaps are

6. needed to sort [4, 3, 2, 1] 4 5 6 7
using Bubble Sort?
Which search algorithm
Linear Exponential None of
7. works on both sorted and Binary Search
Search Search These
unsorted lists?
What condition must be Array must
Array must Array must be Array must be
8. true for Binary Search to have distinct
be unsorted sorted of even length
work? elements
Why is Linear Search less It checks It divides the
It requires It uses
9. efficient than Binary every element search space in
sorted data recursion
Search for large datasets? sequentially half
How many comparisons
are required to find the
10. 4 3 2 1
target 40 in [10, 20, 30, 40,
50] using Binary Search?

SHORT RESPONSE QUESTIONS (SRQs)

1. Define Insertion Sort and write its key characteristic. [K.B]
Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. Its
key characteristic is that it places each element in its correct position within the already sorted portion of
the array.
2. What is Bubble Sort, and why is it called a comparison-based algorithm? [K.B]
Bubble Sort is a sorting algorithm that repeatedly compares adjacent elements in an array and swaps
them if they are in the wrong order. It is called a comparison-based algorithm because it compares
elements to decide their order.
3. Describe the advantage of using Insertion Sort for small datasets. [U.B]
Insertion Sort is simple to implement and performs well for small datasets due to its low overhead and
fewer comparisons, especially when the array is nearly sorted.
4. Define how the "swapping" mechanism in Bubble Sort works with an example. [A.B]
In Bubble Sort, if two adjacent elements are out of order, they are swapped.

For example, in [5, 3, 8], compare 5 and 3 → swap them → [3, 5, 8].

5. Why does Binary Search fail on unsorted data? [U.B]

Binary Search assumes the data is sorted to decide which half of the array to search. If the data is
unsorted, the algorithm cannot accurately determine where the target might be.

6. Describe the behavior of Linear Search when the target element is not in the list. [ U.B]

Linear Search will check every element in the list. If the target is not found after scanning all elements,
it returns -1 or "not found."

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE
CHAPTER 2 COMPUTATIONAL THINKING & ALGORITHM

For example, if the array is [1, 2, 3, 4] and the target is 5. Linear Search will check all elements: 1, 2, 3,
and 4. After reaching the end of the array without finding the target, it will return "not found.

7. Differentiate between Linear Search and Binary Search in Computational Thinking. [U.B]
Aspect Linear Search Binary Search
Breaks the problem into smaller
Problem steps by checking each element
Divides the search space into halves
Decomposition repeatedly.
sequentially.
Sequential approach: starts from
Algorithmic the first element and continues Uses a divide-and-conquer approach
Thinking until the target is found or the list to locate the target.
ends.
No abstraction required; works
Requires the abstraction of sorting
Abstraction directly on the list regardless of
the data before searching.
order.

8. Differentiate between Bubble Sort and Insertion Sort in Computational Thinking. [U.B]
Aspect Bubble Sort Insertion Sort
Decomposition Compare and swap adjacent Insert elements into the correct
elements. position.
Pattern Largest element "bubbles up."
Elements to the left are always
Recognition sorted.

Efficiency High number of unnecessary More efficient for nearly sorted

comparisons. arrays.

EXTENDED RESPONSE QUESTIONS (ERQs)

1. Describe the steps of Bubble Sort with a detailed example.

2. Why is Insertion Sort more efficient than Bubble Sort for partially sorted datasets? Explain with an
example.

3. Sort the array [8, 4, 6, 2, 5] step-by-step using Bubble Sort and show all intermediate results.

4. Search for the element 25 in the sorted array [10, 20, 25, 30, 35] using Binary Search and show all steps.

5. Demonstrate Linear Search on the array [15, 10, 5, 20, 45] to find the element 10, showing each
comparison.

SCHOLARS LECTURE NOTES – 1st YEAR (COMPUTER SCIENCE)

SCHOLARS RESEARCH CENTRE