Supplemental Materials and Enrichment Activity Form

Program: Course:
Data Structure and Algorithm BSIT

Batch Number: Week/s Covered : Inclusive Dates:

3Rd - 4th week Sept 23, 2024 to Sept 26, 2024
of September
Faculty Name: Yr. & Sec.: Time & Day:
MLDELOSSANTOS BSIT 1-21 / ACT 1-21 1:00pm-3:00pm & T-TH

MODULE 3 (Unit 1: Types of Algorithm)

Topics:
1. Sorting Algorithm
a. Bubble Sort
b. Insert Sort
c. Selection Sort
d. Quick Sort
e. Heap Sort

Course Learning Outcomes:

At the end of this lesson students should be able to:
1. Explained the concepts and performed algorithm analysis and design
Unit 1: Type of Algorithm

Algorithms can be categorized based on various criteria. Here are some of the most common types:

1. Sorting Algorithms

Sorting algorithms arrange elements in a specific order,

such as ascending or descending. They are widely used
in various applications, from databases to search
engines.

Bubble Sort repeatedly steps through the list, compares

adjacent elements, and swaps them if they are in the
wrong order. The process is repeated n-1 times for a list
of n items. In each such iteration, the

largest element is arranged in the end. For example, in

the first iteration, the largest element would be placed in
the last position of the list, and again, the same process
will be followed for the remaining n-1 items. In the second
 Supplemental Materials and Enrichment Activity Form

iteration, the second largest element will be placed at the second-to-last position in the list, and the
process will then be repeated until the list is sorted.

Let's take a list with only two elements, {5, 2}, to understand the concept of
the bubble sort, as shown in the following diagram:

To sort this list, we simply swap the values into the right positions, with 2
occupying index 0 and 5 occupying index 1. To effectively swap these
elements, we need to have a temporary storage area:

Implementation of the bubble sort algorithm starts with the swap method,
illustrated in the preceding diagram. First, element 5 will be copied to a temporary location, temp . Then,
element 2 will be moved to index 0. Finally, 5 will be moved from temp to index 1. At the end of it all, the
elements will have been swapped. The list will now contain the elements as [2, 5] .

Example: Bubble Sort

Let's consider another example to understand the working of bubble sort algorithm to sort an unordered
list of 6 elements, such as {45, 23, 87, 12, 32, 4}. In the first iteration, we start comparing the first two
elements, 45 and 23, and we swap them, as 45 should be placed after 23. Then, we compare the next
adjacent values, 45 and 87, to see whether they are in the correct order. Swap them if they are not in the
correct order. We can see, in the following diagram, that after the first iteration of the bubble sort, the
largest element, 87, is placed in the last position of the list:
 Supplemental Materials and Enrichment Activity Form

After the first iteration, we just need to arrange the remaining (n-1) elements; we repeat the same process
by comparing the adjacent elements for the remaining five elements. After the second iteration, the
second largest element, 45, is placed at the second-to-last position in the list, as shown in the following
diagram:

Next, we have to compare the remaining (n-2) elements to arrange them as shown in the following
diagram:

Similarly, we compare the remaining elements to sort them, as well:

Finally, in the last two remaining elements, we place them in the correct order to obtain the final sorted
list, as shown in the following diagram:
 Supplemental Materials and Enrichment Activity Form

The bubble sort is an inefficient sorting algorithm that provides worst-case and average-case runtime
complexity of O(n 2 ) , and a best-case complexity of O(n) . Generally, the bubble sort algorithm should
not be used to sort large lists. However, on relatively small lists, it performs fairly well.

Insertion sort algorithms

The idea of swapping adjacent elements to sort a list of items can also be used to implement the insertion
sort. An insertion sorting algorithm maintains a sub-list that is always sorted, while the other portion of the
list remains unsorted. We take elements from the
unsorted sub-list and insert them in the correct
position in the sorted sub-list, in such a way that
this sub-list remains sorted.

Let's consider an example to understand the

working of the insertion sorting algorithm. In our
example, we'll be sorting a list of 6 elements: {45,
23, 87, 12, 32, 4}. Firstly, we start with 1 element,
assuming it to be sorted, then take the next
element, 23 , from the unsorted sub-list and insert
it at the correct position in the sorted sub-list. In
the next iteration, we take the third element, 87 ,
from the unsorted sub-list, and again insert it into
the sorted sub-list at the correct position. We
follow the same process until all elements are in
the sorted sub-list. This whole process is shown in
the following diagram:

Another example, let's consider the following array:

The algorithm starts by using a for loop to run between the 1 and 4 indices. We start from index 1
because we assume the sub-array at index 0 to already be in the correctly
sorted order:

At the start of the execution of the loop, we have the following:

for index in range(1, len(unsorted_list)):

search_index = index

insert_value = unsorted_list[index]
 Supplemental Materials and Enrichment Activity Form

At the beginning of the execution of each run of the for loop, the element at unsorted_list[index] is stored
in the insert_value variable. Later, when we find the appropriate position in the sorted portion of the list,
insert_value will be stored at that index or location:

for index in range(1, len(unsorted_list)):

search_index = index

insert_value = unsorted_list[index]

while search_index > 0 and unsorted_list[search_index-1] >

insert_value :

unsorted_list[search_index] = unsorted_list[search_index-1]

search_index -= 1

unsorted_list[search_index] = insert_value

The search_index is used to provide information to the while loop; that is, exactly where to find the next
element that needs to be inserted into the sorted sub-list.

The while loop traverses the list backward, guided by two conditions: first, if search_index > 0 , then it
means that there are more elements in the sorted portion of the list; second, for the while loop to run,
unsorted_list[search_index-1] must be greater than the insert_value variable. The
unsorted_list[search_index-1] array will do either of the following things:

• Point to the element, just before the unsorted_list[search_index] , before the while loop is
executed the first time

• Point to one element before unsorted_list[search_index-1] after the while loop has been run the
first time

In our example list, the while loop will be executed because 5 > 1. In the body of the while loop, the
element at unsorted_list[search_index-1] is stored at unsorted_list[search_index] . search_index -= 1
moves the list traversal backward until it holds a value of 0.

Our list now looks like the following:

After the while loop exits, the last known position of search_index (which, in
this case, is 0 ) now helps us to know where to insert insert_value:
 Supplemental Materials and Enrichment Activity Form

On the second iteration of the for loop, search_index will have a value of 2, which is the index of the third
element in the array. At this point, we start our comparison in the leftward direction (toward index 0). 100
will be compared with 5, but because 100 is greater than 5, the while loop will not be executed. 100 will
be replaced by itself, because the search_index variable never got decremented. As such,
unsorted_list[search_index] = insert_value will have no effect.

When search_index is pointing at index 3, we compare 2 with 100, and move 100 to where 2 is stored.
We then compare 2 with 5 and move 5 to where 100 was initially stored. At this point, the while loop will
break and 2 will be stored in index 1. The array will be partially sorted with the values [1, 2, 5, 100, 10] .

The preceding step will occur one last time for the list to be sorted.

The insertion sorting algorithm is considered stable, in the sense that it does not change the relative order
of elements that have equal keys. It also only requires no more memory than that consumed by the list,
because it does the swapping in-place.

Insertion sorting algorithm gives a worst-case runtime complexity of O(n 2 ) , and a best-case complexity
O(n).

Selection Sort

Another popular sorting algorithm is the selection sort. The selection sorting algorithm begins by finding
the smallest element in the list, and interchanges it with the data stored at the first position in the list.
Thus, it makes the sub-list sorted up to the first element. Next, the second smallest element, which is the
smallest element in the remaining list, is identified and interchanged with the second position in the list.
This makes the initial two elements sorted. The process is repeated, and the smallest element remaining
in the list should be swapped with the element in the third index on the list. This means that the first three
elements are now sorted. This process is repeated for (n-1) times to sort n items.

Let's look at an example to understand how the algorithm works. We'll sort the following

list of 4 elements using the selection sort algorithm:

Starting at index 0, we search for the smallest item in the list that exists between index 1, and the index of
the last element. When this element has been found, it is exchanged with the data found at index 0. We
simply repeat this process until the list is fully sorted.

Searching for the smallest item within the list is an incremental process:
 Supplemental Materials and Enrichment Activity Form

A comparison of elements 2 and 5 selects 2, as it is the lesser value among these two values, and thus,
the two elements are swapped.

After the swap operation, the array looks like this:

Further, at index 0, we compare 2 with 65:

Since 65 is greater than 2, the two elements are not swapped. A further comparison is made between the
element at index 0, which is 2, and the element at index 3, which is 10. No swap takes place in this case.
When we get to the last element in the list, we will have the smallest element occupying index 0.

In the next iteration, we start comparing elements from position 1 in the index. We repeat the whole
process of comparing the element stored at index 1 with all the elements, from index 2 through to the last
index.

The second iteration starts by comparing 5 and 65, which will look like this:

Once we find out that the 5 is the smallest value in the sub-list from indices 1 to 3, we place it at index 1.
Similarly, the next smallest element from the sub-lists 2 and 3 indices is placed at index 3.

The following is an implementation of the selection sort algorithm. The argument to the function is the
unsorted list of items we want to put in ascending order of magnitude:
 Supplemental Materials and Enrichment Activity Form

The algorithm begins by using the outer for loop to go through the list, size_of_list , a number of times.
Because we pass size_of_list to the range method, it'll produce a sequence from 0 through to size_of_list-
1.

The inner loop is responsible for going through the list and swap elements if we encounter an element
less than the element pointed to by unsorted_list[i] . Notice that the inner loop begins from i+1 up to
size_of_list-1.

The inner loop begins its search for the smallest element from i+1 , but uses
the j index:

The preceding diagram shows the direction in which the algorithm searches for the next smallest item.

The selection sorting algorithm gives worst-case and best-case runtime complexities of O(n2) .

Quick sort algorithms

The quick sort algorithm is very efficient for sorting. The quick sort algorithm falls under the divide and
conquer class of algorithms, similar to the merge sort algorithm, where we break (divide) a problem into
smaller chunks that are much simpler to solve (conquer).

Quicksort is a fast sorting algorithm that works by splitting a large array of data into smaller sub-arrays.
This implies that each iteration works by splitting the input into two components, sorting them, and then
recombining them. For big datasets, the technique is highly efficient since its average and best-case
complexity is O(n*logn).

Algorithms can be categorized based on various criteria. Here are some of the most common
types:
 Supplemental Materials and Enrichment Activity Form

1. Sorting Algorithms

Sorting algorithms arrange elements in a specific

order, such as ascending or descending. They are
widely used in various applications, from databases
to search engines.

Bubble Sort repeatedly steps through the list,

compares adjacent elements, and swaps them if
they are in the wrong order. The process is repeated
n-1 times for a list of n items. In each such iteration,
the

largest element is arranged in the end. For example,

in the first iteration, the largest element would be
placed in the last position of the list, and again, the
same process will be followed for the remaining n-1
items. In the second iteration, the second largest element will be placed at the second-to-last
position in the list, and the process will then be repeated until the list is sorted.

Let's take a list with only two elements, {5, 2}, to understand the
concept of the bubble sort,

as shown in the following diagram:

To sort this list, we simply swap the values into the right positions, with 2 occupying

index 0 and 5 occupying index 1. To effectively swap these elements, we need to have a

temporary storage area:

 Supplemental Materials and Enrichment Activity Form

Implementation of the bubble sort algorithm starts with the

swap method, illustrated in the preceding diagram. First,
element 5 will be copied to a temporary location, temp .
Then, element 2 will be moved to index 0. Finally, 5 will be
moved from temp to index 1. At the

end of it all, the elements will have been swapped. The list
will now contain the elements as [2, 5] .

Example: Bubble Sort

Let's consider another example to understand the working of bubble sort algorithm to sort an
unordered list of 6 elements, such as {45, 23, 87, 12, 32, 4}. In the first iteration, we start
comparing the first two elements, 45 and 23, and we swap them, as 45 should be placed after
23. Then, we compare the next adjacent values, 45 and 87, to see whether they are in the
correct order. Swap them if they are not in the correct order. We can see, in the following
diagram, that after the first iteration of the bubble sort, the largest element, 87, is placed in the
last position of the list:
 Supplemental Materials and Enrichment Activity Form

After the first iteration, we just need to arrange the remaining (n-1) elements; we repeat the
same process by comparing the adjacent elements for the remaining five elements. After the
second iteration, the second largest element, 45, is placed at the second-to-last position in the
list, as shown in the following diagram:

Next, we have to compare the remaining (n-2) elements to arrange them as shown in the

following diagram:
 Supplemental Materials and Enrichment Activity Form

Similarly, we compare the remaining elements to sort them, as well:

Finally, in the last two remaining elements, we place them in the correct order to obtain the

final sorted list, as shown in the following diagram:

The bubble sort is an inefficient sorting algorithm that provides worst-case and average-case
runtime complexity of O(n 2 ) , and a best-case complexity of O(n) . Generally, thebubble sort
algorithm should not be used to sort large lists. However, on relatively small lists, it performs
fairly well.
 Supplemental Materials and Enrichment Activity Form

Insertion sort algorithms

The idea of swapping adjacent elements to sort a list of items can also be used to implement
the insertion sort. An insertion sorting algorithm maintains a sub-list that is always sorted, while
the other portion of the list remains unsorted. We take elements from the unsorted sub-list and
insert them in the correct position in the sorted sub-list, in such a way that this sub-list remains
sorted.

Let's consider an example to understand the

working of the insertion sorting algorithm. In
our example, we'll be sorting a list of 6
elements: {45, 23, 87, 12, 32, 4}. Firstly, we
start with 1 element, assuming it to be sorted,
then take the next element, 23 , from the
unsorted sub-list and insert it at the correct
position in the sorted sub-list. In the next
iteration, we take the third element, 87 , from
the unsorted sub-list, and again insert it into
the sorted sub-list at the correct position. We
follow the same process until all elements are
in the sorted sub-list. This whole process is
shown in the following diagram:

Another example, let's consider the following array:

The algorithm starts by using a for loop to run between the 1 and 4 indices. We
start from index 1 because we assume the sub-array at index 0 to already be in
the correctly sorted order:
 Supplemental Materials and Enrichment Activity Form

At the start of the execution of the loop, we have the following:

for index in range(1, len(unsorted_list)):

search_index = index

insert_value = unsorted_list[index]

At the beginning of the execution of each run of the for loop, the element at unsorted_list[index]
is stored in the insert_value variable. Later, when we find the appropriate position in the sorted
portion of the list, insert_value will be stored at that index or location:

for index in range(1, len(unsorted_list)):

search_index = index

insert_value = unsorted_list[index]

while search_index > 0 and unsorted_list[search_index-1] >

insert_value :

unsorted_list[search_index] = unsorted_list[search_index-1]

search_index -= 1

unsorted_list[search_index] = insert_value

The search_index is used to provide information to the while loop; that is, exactly where to find
the next element that needs to be inserted into the sorted sub-list.

The while loop traverses the list backward, guided by two conditions: first, if search_index > 0 ,
then it means that there are more elements in the sorted portion of the list; second, for the while
loop to run, unsorted_list[search_index-1] must be greater than the insert_value variable. The
unsorted_list[search_index-1] array will do either of the following things:

• Point to the element, just before the unsorted_list[search_index] , before the while loop
is executed the first time

• Point to one element before unsorted_list[search_index-1] after the while loop has been
run the first time
 Supplemental Materials and Enrichment Activity Form
In our example list, the while loop will be executed because 5 > 1. In the body of the while loop,
the element at unsorted_list[search_index-1] is stored at unsorted_list[search_index] .
search_index -= 1 moves the list traversal backward until it holds a value of 0.

Our list now looks like the following:

After the while loop exits, the last known position of search_index (which, in this case, is

0 ) now helps us to know where to insert insert_value:

On the second iteration of the for loop, search_index will have a value of 2, which is the index of
the third element in the array. At this point, we start our comparison in the leftward direction
(toward index 0). 100 will be compared with 5, but because 100 is greater than 5, the while loop
will not be executed. 100 will be replaced by itself, because the search_index variable never got
decremented. As

such, unsorted_list[search_index] = insert_value will have no effect.

When search_index is pointing at index 3, we compare 2 with 100, and move 100 to where 2 is
stored. We then compare 2 with 5 and move 5 to where 100 was initially stored. At this point,
the while loop will break and 2 will be stored in index 1. The array will be partially sorted with the
values [1, 2, 5, 100, 10] .
 Supplemental Materials and Enrichment Activity Form

The preceding step will occur one last time for the list to be sorted.

The insertion sorting algorithm is considered stable, in the sense that it does not change the
relative order of elements that have equal keys. It also only requires no more memory than that
consumed by the list, because it does the swapping in-place.

Insertion sorting algorithm gives a worst-case runtime complexity of O(n 2 ) , and a best-case
complexity O(n) .

Selection Sort

Another popular sorting algorithm is the selection sort. The selection sorting algorithm begins by
finding the smallest element in the list, and interchanges it with the data stored at the first
position in the list. Thus, it makes the sub-list sorted up to the first element. Next, the second
smallest element, which is the smallest element in the remaining list, is identified and
interchanged with the second position in the list. This makes the initial two elements sorted. The
process is repeated, and the smallest element remaining in the list should be swapped with the
element in the third index on the list. This means that the first three elements are now sorted.
This process is repeated for (n-1) times to sort n items.

Let's look at an example to understand how the algorithm works. We'll sort the following

list of 4 elements using the selection sort algorithm:

Starting at index 0, we search for the smallest item in the list that exists between index 1, and
the index of the last element. When this element has been found, it is exchanged with the data
found at index 0. We simply repeat this process until the list is fully sorted.

Searching for the smallest item within the list is an incremental process:
 Supplemental Materials and Enrichment Activity Form

A comparison of elements 2 and 5 selects 2, as it is the lesser value among these two values,
and thus, the two elements are swapped.

After the swap operation, the array looks like this:

Further, at index 0, we compare 2 with 65:

Since 65 is greater than 2, the two elements are not swapped. A further comparison is made
between the element at index 0, which is 2, and the element at index 3, which is 10. No swap
takes place in this case. When we get to the last element in the list, we will have the smallest
element occupying index 0.

In the next iteration, we start comparing elements from position 1 in the index. We repeat the
whole process of comparing the element stored at index 1 with all the elements, from index 2
through to the last index.

The second iteration starts by comparing 5 and 65, which will look like
this:
 Supplemental Materials and Enrichment Activity Form

Once we find out that the 5 is the smallest value in the sub-list from indices 1 to 3, we place it at
index 1. Similarly, the next smallest element from the sub-lists 2 and 3 indices is placed at index
3.

The following is an implementation of the selection sort algorithm. The argument to the function
is the unsorted list of items we want to put in ascending order of magnitude:

The algorithm begins by using the outer for loop to go through the list, size_of_list , a number of
times. Because we pass size_of_list to the range method, it'll produce a sequence from 0
through to size_of_list-1.

The inner loop is responsible for going through the list and swap elements if we encounter an
element less than the element pointed to by unsorted_list[i] . Notice that the inner loop begins
from i+1 up to size_of_list-1.

The inner loop begins its search for the smallest element from i+1 , but
uses the j index:

The preceding diagram shows the direction in which the algorithm searches for the next
smallest item.

The selection sorting algorithm gives worst-case and best-case runtime complexities of O(n2) .
 Supplemental Materials and Enrichment Activity Form

Quick sort algorithms

The quick sort algorithm is very efficient for sorting. The quick sort algorithm falls under the
divide and conquer class of algorithms, similar to the merge sort algorithm, where we break
(divide) a problem into smaller chunks that are much simpler to solve (conquer).

Quicksort is a fast sorting algorithm that works by splitting a large array of data into smaller sub-
arrays. This implies that each iteration works by splitting the input into two components, sorting
them, and then recombining them. For big datasets, the technique is highly efficient since its
average and best-case complexity is O(n*logn).

Benefits of Quicksort

• It works rapidly and effectively.

• It has the best time complexity when compared to other sorting algorithms.

• Quick sort has a space complexity of O(logn), making it an excellent choice for situations
when space is limited.

Limitations of Quicksort

• This sorting technique is considered unstable since it does not maintain the key-value
pairs initial order.

• When the pivot element is the largest or smallest, or when all of the components have
the same size. The performance of the quicksort is significantly impacted by these worst-
case scenarios.

• It’s difficult to implement since it’s a recursive process, especially if recursion isn’t
available.
 Supplemental Materials and Enrichment Activity Form

The Quicksort Algorithm in Action

In this example, the array(shown in graphic below) contains unsorted values, which we will sort
using Quicksort.

1). Selecting Pivot

The process starts by selecting one element (known as the pivot) from the list; this can be any
element. A pivot can be:

• Any element at random

• The first or last element

• Middle element

For this example, we’ll use the last element, 4, as our pivot.

2). Rearranging the Array

Now, the goal here is to rearrange the list such that all the elements less than the pivot are
towards the left of it, and all the elements greater than the pivot are towards the right of it.

• The pivot element is compared to all of the items starting with the first index. If the
element is greater than the pivot element, a second pointer is appended.

• When compared to other elements, if a smaller element than the pivot element is found,
the smaller element is swapped with the larger element identified before.
 Supplemental Materials and Enrichment Activity Form

• Every element, starting with 7, will be compared to the pivot(4). A second pointer will be
placed at 7 because 7 is bigger than 4.

• The next element, element 2 will now be compared to the pivot. As 2 is less than 4, it will
be replaced by the bigger figure 7 which was found earlier.

• The numbers 7 and 2 are swapped. Now, pivot will be compared to the next element, 1
which is smaller than 4.

• So once again, 7 will be swapped with 1.

• The procedure continues until the next-to-last element is reached, and at the end the
pivot element is then replaced with the second pointer. Here, number 4(pivot) will be
replaced with number 6.

As elements 2, 1, and 3 are less than 4, they are on the pivot’s left side. Elements can be in any
order: ‘1’,’2’,’3’, or ‘3’,’1’,’2’, or ‘2’,’3’,’1’. The only requirement is that all of the elements must be
less than the pivot. Similarly, on the right side, regardless of their sequence, all components
should be greater than the pivot.

In simple words,the algorithm searches for every value that is smaller than the pivot. Values
smaller than pivot will be placed on the left, while values larger than pivot will be placed on the
right. Once the values are rearranged, it will set the pivot in its sorted position.
 Supplemental Materials and Enrichment Activity Form

3). Dividing Subarrays

Once we have partitioned the array, we can break this problem into two sub-problems. First,
sort the segment of the array to the left of the pivot, and then sort the segment of the array to
the right of the pivot.

• In the same way that we rearranged elements in step 2, we will pick a pivot element for
each of the left and right sub-parts individually.

• Now, we will rearrange the sub-list such that all the elements are less than the pivot
point, which is towards the left. For example, element 3 is the largest among the three
elements, which satisfies the condition, hence the element 3 is in its sorted position.

• In a similar manner, we will again work on the sub-list and sort the elements 2 and 1. We
will stop the process when we get a single element at the end.

• Repeat the same process for the right-

side sub-list. The subarrays are
subdivided until each subarray consists
of only one element.

Implementation:
 Supplemental Materials and Enrichment Activity Form

Quicksort Applications

The sorting algorithm is used to find information, and since Quicksort is the fastest, it is
frequently used as a more efficient search approach.

It’s applied wherever a stable sort isn’t required. Since it is tail-recursive, every call optimization
can be done. It is useful in event-driven simulation and operational research.

Heap Sort Algorithm

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is
similar to the selection sort where we first find the minimum element and place the minimum
element at the beginning. Repeat the same process for the remaining elements.

To solve the problem follow the below idea:

First convert the array into heap data structure using heapify, then one by one delete the root
node of the Max-heap and replace it with the last node in the heap and then heapify the root of
the heap. Repeat this process until size of heap is greater than 1.

• Build a heap from the given input array.

• Repeat the following steps until the heap contains only one element:

◦ Swap the root element of the heap (which is the largest element) with the last
element of the heap.

◦ Remove the last element of the heap (which is now in the correct position).

◦ Heapify the remaining elements of the heap.

• The sorted array is obtained by reversing the order of the elements in the input array.

Consider the array: arr[] = {4, 10, 3, 5, 1}.

Transform into max heap: After that, the task is to construct a tree from that unsorted array and
try to convert it into max heap.

• To transform a heap into a max-heap, the parent node should always be greater than or
equal to the child nodes
 Supplemental Materials and Enrichment Activity Form
◦ Here, in this example, as the parent node 4 is smaller than the child node 10, thus,
swap them to build a max-heap.

• Now, 4 as a parent is smaller than the child 5, thus swap both of these again and the
resulted heap and array should be like this:

Perform heap sort: Remove the maximum element in each step (i.e., move it to the end position
and remove that) and then consider the remaining elements and transform it into a max heap.

Delete the root element (10) from the max heap. In order to delete this node, try to swap it with
the last node, i.e. (1). After removing the root element, again heapify it to convert it into max
heap.

• Resulted heap and array should look like this:

• Repeat the above steps and it will look like the following:

• Now remove the root (i.e. 3) again and perform heapify.

 Supplemental Materials and Enrichment Activity Form
• Now when the root is removed once again it is sorted. and the sorted array will be like
arr[] = {1, 3, 4, 5, 10}.

Implementation:

Complexity Analysis of Heap Sort

Time Complexity: O(N log N)

Auxiliary Space: O(log n), due to the recursive call stack. However, auxiliary space can be
O(1) for iterative implementation.
 Supplemental Materials and Enrichment Activity Form
A comparison of the complexities of different sorting algorithms is given in the following table:

==================================================================
References:

[Link]
sort/

[Link]

[Link]

==================================================================
Exercise 2 Optimized Bubble Sort

1.) Access the source code here:

[Link]
[Link]

1.) Rename the function as optimized_bubble_sort

2.) Introduce a 'swapped' variable before the inner loop to track any swaps made during
each iteration of the outer loop.
3.) Set 'swapped' to 'True' inside the inner loop whenever a swap is performed.
4.) After each iteration of the inner loop, check the value of 'swapped'. If it remains
'False', it signifies that no swaps were made, indicating that the list is already sorted and
the algorithm can terminate early.

Exercise 2.1 Bubble Sort

#Convert each string element to a reference character, often the first character of the
string.
#Compare the Unicode value of these reference characters to decide the order of the
two strings.
#Swap the strings if they are found in the incorrect order based on their reference
characters.
#Iterate through the list of strings, repeatedly sorting and swapping until the entire list is
arranged in alphabetical order.

#output: ['apple', 'banana', 'cherry', 'grape', 'orange']

Exercise 3 Insertion Sort

 Supplemental Materials and Enrichment Activity Form

#Convert each string element to a reference character, often the first character of the
string.
#Compare the Unicode value of these reference characters to decide the order of the
two strings.

#Swap the strings if they are found in the incorrect order based on their reference
characters.
#Iterate through the list of strings, repeatedly sorting and swapping until the entire list is
arranged in alphabetical order.

#output: ['BSIT', 'BSOA', 'ACS', 'ACT', 'BSEN', 'BSAIS']