2/15/25

ALGORITHMS AND
COMPLEXITY G
Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

1 2

WHAT IS SORTING?
- is a process that is required in many places and is

INTERNAL to be handled properly in order to use efficiently.

- is a simple process of swapping two or more
numbers in an ordered manner both ascending
SORTING and descending order.
-divided into two types: Internal sorting and
ALGORITHMS external sorting.

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

3 4

1
 2/15/25

INTERNAL SORTING ALGORITHM TYPES OF INTERNAL SORTING

ALGORITHM
- is a sorting algorithm uses the main memory • BUBBLE SORT
exclusively during the sort. • SELECTION SORT
- the data can be accessed extremely fast and • INSERTION SORT
randomly. • MERGE SORT
- is used when data items are less than enough to • QUICK SORT
be held in the main memory (RAM). • HEAP SORT
• COUNTING SORT
• RADIX SORT
Prepared by: Maxil S. Urocay MSCS ongoing • BUCKET SORT Prepared by: Maxil S. Urocay MSCS ongoing

5 6

BUBBLE SORT BUBBLE SORT

- repeatedly steps through the list, compares Time complexity:

adjacent elements, and swaps them if they are in Best case: O(n) = when the list is already sorted.
the wrong order.
*If the array is already sorted, bubble sort only
- this algorithm is not suitable for large datasets makes one full pass without swapping elements.
as its average and worst case time complexity are
quite high.

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

7 8

2
 2/15/25

BUBBLE SORT BUBBLE SORT

Time complexity: Time complexity:

Average case: O(n2) = random order list Worst case: O(n2) = Reverse sorted list

*each element is compared with adjacent element *if the array is sorted in descending order, every
multiple times. element needs to be moved to the other end.

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

9 10

BUBBLE SORT BUBBLE SORT

Given 5 3 8 4 2
Space complexity:
O(1)
Pass 1:
1. Compare 5,3 3 5 8 4 2 Swap
* is an in-place sorting algorithm, meaning it does
not require extra space proportional to the input 2. Compare 5,8 3 5 8 4 2 No swap
size. 3. Compare 8,4 3 Swap
5 4 8 2
4. Compare 8,2 3 5 4 2 8 Swap
Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

11 12

3
 2/15/25

BUBBLE SORT BUBBLE SORT

Pass 2: 3 5 4 2 8 Pass 3: 3 4 2 5 8

1. Compare 3,5 3 5 4 2 8 No swap 1. Compare 3,4 3 4 2 5 8 No swap

2. Compare 5,4 3 4 5 2 8 Swap 2. Compare 4,2 3 2 4 5 8 Swap
3. Compare 5,2 3 4 2 5 8 Swap

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

13 14

BUBBLE SORT SELECTION SORT

Pass 4: 3 2 4 5 8
- is a simple comparison-based sorting
algorithms which works by repeatedly finding
1. Compare 3,2 2 3 4 5 8 No swap the minimum or maximum element from the
unsorted part of the list and swapping it with
the first unsorted element.
- The process is repeated until the entire list is
sorted.

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

15 16

4
 2/15/25

SELECTION SORT SELECTION SORT

ALGORITHMS STEPS FOR ASCENDING ORDER: TIME COMPLEXITY:
- Start at the beginning of the list (index 0) Best Case: O (n2)
- Find the minimum element in the unsorted part
of the list (from the current index to the last *even if the list is already sorted, selection sort
element) still performs n-1 comparisons for each element.
- Swap the minimum element with the element
at the current index.
- Move to the next index and repeat the process
until the entire list is sorted.
Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

17 18

SELECTION SORT SELECTION SORT

TIME COMPLEXITY: TIME COMPLEXITY:
Average Case: O (n2) Worst Case: O (n2)

*the algorithms performs the same number of *when the list is in reverse order, selections sort
comparisons, and each pass perform n-1 also performs quadratic comparisons. The
comparisons for each element. algorithm still needs to perform n-1 comparisons
for each element.

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

19 20

5
 2/15/25

SELECTION SORT SELECTION SORT

SPACE COMPLEXITY: Given 64 25 12 22 11
O(1)

*the algorithm is in-place, meaning it doesn’t Step 1 11 25 12 22 64 Swap 11 and 64

require additional space for another list or array.
Step 2 11 12 25 22 64 Swap 12 and 25

Step 3 11 12 22 25 64 Swap 22 and 25

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

21 22

SELECTION SORT INSERTION SORT

- Is a comparison-based sorting algorithm that

11 12 22 25 64 No Swap 25 and builds the final sorted array or list one element
Step 4 at a time.
64
- Is a simple sorting algorithm that works by
Step 5 11 12 22 25 64 iteratively inserting each element of an
No Swap since
unsorted list into its correct position in a sorted
63 alone portion of the list.

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

23 24

6
 2/15/25

INSERTION SORT INSERTION SORT

- Start from the second element TIME COMPLEXITY:
- Compare the current element with the Best Case: O(n)
elements before it.
- Shift elements greater than the current element *occurs when the list is already sorted, and in this
one position to the right to make space. case, only one comparison is needed for each
- Insert the current element into the correct element, and no shifting is necessary.
position.
- Repeat this process for all remaining elements.
Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

25 26

INSERTION SORT INSERTION SORT

TIME COMPLEXITY: TIME COMPLEXITY:
Average Case: O(n2) Worst Case: O(n2)

*the algorithm needs to shift each element in the *happens when the list is sorted in reverse order.
sorted section multiple times to make room for
the element being inserted.

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

27 28

7
 2/15/25

INSERTION SORT INSERTION SORT

SPACE COMPLEXITY: Given 29 10 14 37 13
O(1)
Step 1: 10 29 14 37 13
*is an in-place sorting algorithm, meaning it does
not require any additional space for a second Step 2: 10 14 29 37 13
array or list.
Step 3: 10 14 29 37 13
Step 4: 10 13 14 29 37
Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

29 30

MERGE SORT MERGE SORT

- Is a divide-and-conquer sorting algorithm, and it Steps:

divides the array into two halves, recursively sorts
each half, and then merges the sorted halves back 1. Divide – split the array into two halves.
together. 2. Conquer – recursively sort each half.
3. Combine (merge) – merge the two sorted
halves into a single sorted array.

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

31 32

8
 2/15/25

MERGE SORT MERGE SORT

TIME COMPLEXITY: TIME COMPLEXITY:

Best Case: O(n log n) Average Case: O(n log n)

*occurs when the list is already sorted, and it still *will divide the list into halves and recursively sort
divides the list and merges the sorted halves, but them, performing a merge step at each level.
the time complexity remains O(n log n) because,
even if the data is sorted, the algorithm still needs
to divide the list into halves and merge the
results. Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

33 34

MERGE SORT MERGE SORT

TIME COMPLEXITY: SPACE COMPLEXITY:

Worst Case: O(n log n) O(n)

*whether the list is sorted, reverse sorted, or *is not an in-place sorting algorithm, so it requires
randomly ordered, merge sort always divides the additional space for the merging process.
list and merges the sublists in the same manner.

Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

35 36

9
 2/15/25

MERGE SORT MERGE SORT

Given 39 28 44 11 39 28 44 11

Step 1 39 28 44 11 Step 3 28 39 11 41

Step 2 39 28 44 11
Step 4 11 28 39 41
Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing

37 38

THANK OFFERS
PRODUCT YOU

Prepared by: Maxil S. Urocay MSCS ongoing

45

10