CITY COLLEGE OF SAN FERNANDO PAMPANGA

City of San Fernando, Pampanga

INSTITUTE OF INFORMATION TECHNOLOGY

DATA STRUCTURES AND ALGORITHMS

Module 3: Searching & Sorting

Learning Outcomes:
At the end of the module, the students are able to:
●​ Explain the principles and differences between searching and sorting algorithms.
●​ Implement linear and binary search in Java.
●​ Implement bubble sort, selection sort, and insertion sort in Java.
●​ Analyze algorithm efficiency using Big-O notation.
●​ Compare the strengths and limitations of different algorithms.

Module Description:
Searching and sorting are fundamental operations in computer science, forming the backbone of
data processing. Searching determines the presence or location of data within a collection, while
sorting arranges data in a logical order to improve accessibility and efficiency. Mastery of these
concepts equips students with the skills to optimize data handling and prepare for more advanced
algorithms.

III. Lesson Content

A. Searching Algorithms
Searching is the process of finding the position of a specific value (target) in a collection of
data.​
The choice of search algorithm depends on:
●​ Data size
●​ Data order (sorted or unsorted)
●​ Performance requirements

1. Linear Search
Definition:
●​ Also called sequential search.

Data Structures and Algorithms ​ ​ ​ Page 1 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

●​ Works by scanning each element from the start to the end until the target is found or all
elements have been checked.
Steps:
1.​ Start from the first element.
2.​ Compare each element to the target value.
3.​ If a match is found, return the position.
4.​ If no match is found, return “Not Found” after reaching the end.
Example Analogy:​
Looking for a specific book in a messy pile where the books are in no particular order—you check
each one until you find it.
Pros:
●​ Simple and easy to implement.
●​ Works for unsorted data.
Cons:
●​ Slow for large datasets.
●​ Time complexity: O(n).
Flowchart Idea:
Start → i = 0 → Is arr[i] == target? → Yes → Return index
↓ No
i++ → i < length? → Repeat or "Not Found"

2. Binary Search
Definition:
●​ Works only on sorted data.
●​ Repeatedly divides the search interval in half.
Steps:
1.​ Find the middle element of the array.
2.​ Compare it to the target:
o​ If equal, return the index.
o​ If the target is less, search the left half.
o​ If the target is greater, search the right half.

Data Structures and Algorithms ​ ​ ​ Page 2 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

3.​ Repeat until the subarray size becomes zero.

Example Analogy:​
Looking for a word in a dictionary: instead of checking page-by-page, you open near the middle,
decide whether to go left or right, and repeat.
Pros:
●​ Very fast for large datasets.
●​ Time complexity: O(log n).
Cons:
●​ Requires sorted data.
●​ More complex to implement.
Flowchart Idea:
Start → left=0, right=length-1 → mid=(left+right)/2
If arr[mid] == target → Found
If arr[mid] > target → right = mid - 1
Else → left = mid + 1
Repeat until left > right → Not Found

B. Sorting Algorithms
Sorting is the process of arranging data in a specific order (ascending or descending).​
Sorting is important because:
●​ It improves search efficiency (binary search needs sorted data).
●​ It makes data easier to read and process.

1. Bubble Sort
Definition:
●​ Repeatedly steps through the array, compares adjacent elements, and swaps them if they are
in the wrong order.
Steps:
1.​ Start from the first element.
2.​ Compare with the next element.
3.​ Swap if they are out of order.

Data Structures and Algorithms ​ ​ ​ Page 3 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

4.​ Continue until the largest element “bubbles up” to the end.
5.​ Repeat for the remaining unsorted part.
Analogy:​
Imagine air bubbles rising to the surface of water — the largest bubble reaches the top in each pass.
Pros:
●​ Very simple to code.
●​ Good for small datasets.
Cons:
●​ Very slow for large datasets.
●​ Time complexity: O(n²).

2. Selection Sort
Definition:
●​ Finds the smallest element from the unsorted portion and swaps it with the first unsorted
element.
Steps:
1.​ Set the first element as the smallest.
2.​ Compare it with the rest of the list.
3.​ If a smaller element is found, update the smallest.
4.​ Swap smallest with first unsorted element.
5.​ Move to the next position and repeat.
Analogy:​
Choosing the smallest apple from a pile, placing it in the basket, then repeating with the rest.
Pros:
●​ Easy to implement.
●​ Makes only n swaps (better for memory swaps than Bubble Sort).
Cons:
●​ Still slow for large datasets.
●​ Time complexity: O(n²).

3. Insertion Sort

Data Structures and Algorithms ​ ​ ​ Page 4 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

Definition:
●​ Builds the sorted portion of the list one element at a time by inserting the new element into
its correct position.
Steps:
1.​ Assume the first element is sorted.
2.​ Take the next element (key) and compare with elements in the sorted part.
3.​ Shift larger elements one position to the right.
4.​ Insert the key into the correct position.
5.​ Repeat until all elements are sorted.
Analogy:​
Sorting a hand of playing cards — pick one card at a time and insert it into the right position.
Pros:
●​ Efficient for small or nearly sorted datasets.
●​ Time complexity: O(n²) in worst case, O(n) in best case.

C. Comparing Algorithms
Algorithm Best Case Worst Case Works on Unsorted? Complexity
Linear Search O(1) O(n) ✅ O(n)
Binary Search O(1) O(log n) ❌ (needs sorted) O(log n)
Bubble Sort O(n) O(n²) ✅ O(n²)
Selection Sort O(n²) O(n²) ✅ O(n²)
Insertion Sort O(n) O(n²) ✅ O(n²)

What is Time complexity?

Data Structures and Algorithms ​ ​ ​ Page 5 | 13
 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

Time complexity is basically a way to measure how fast an algorithm runs as the size of the
input grows.

📌 Why it matters in Searching & Sorting

●​ Linear Search → checks each element one by one → time grows linearly with data size →
O(n).
●​ Binary Search → cuts the search space in half each step → time grows logarithmically →
O(log n).
●​ Sorting algorithms → their efficiency changes depending on the method used:
o​ Bubble Sort: O(n²) (slow for large lists)
o​ Merge Sort: O(n log n) (fast for large lists)

📊 How to read it:

If n = number of elements:
●​ O(1) → constant time (instant regardless of n)
●​ O(log n) → very fast growth
●​ O(n) → time grows proportionally with n
●​ O(n²) → time grows much faster — bad for big n

A. Searching Algorithms

1. Linear Search (Java with Explanation)

public class LinearSearch {

// Method to perform Linear Search

public static int linearSearch(int[] arr, int target) {
// Loop through each element in the array
for (int i = 0; i < [Link]; i++) {
// Check if the current element matches the target value
if (arr[i] == target) {
return i; // Return the index where the target is found

Data Structures and Algorithms ​ ​ ​ Page 6 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

}
}
return -1; // If target not found, return -1
}

public static void main(String[] args) {

// Example array
int[] numbers = {5, 2, 9, 1, 7};

// Call the search method for number 9

int result = linearSearch(numbers, 9);

// Display result
if (result != -1) {
[Link]("Found at index " + result);
} else {
[Link]("Not Found");
}
}
}
Explanation:
●​ for (int i = 0; i < [Link]; i++) → checks every element one-by-one.
●​ if (arr[i] == target) → if current element matches, return index immediately.
●​ return -1 → means “not found” if loop ends without a match.
●​ Best case: found at first position → O(1)
●​ Worst case: found at last position or not at all → O(n)

2. Binary Search (Java with Explanation)

Data Structures and Algorithms ​ ​ ​ Page 7 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

public class BinarySearch {

// Method to perform Binary Search (array must be sorted)

public static int binarySearch(int[] arr, int target) {
int left = 0; // Starting index
int right = [Link] - 1; // Ending index

while (left <= right) {

// Calculate middle index
int mid = (left + right) / 2;

// If middle element is the target

if (arr[mid] == target) {
return mid;
}

// If target is greater, ignore left half

if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, ignore right half
else {
right = mid - 1;
}
}
return -1; // Not found
}

public static void main(String[] args) {

// Sorted array for binary search
int[] numbers = {1, 2, 5, 7, 9};

Data Structures and Algorithms ​ ​ ​ Page 8 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

// Search for number 7

int result = binarySearch(numbers, 7);

// Display result
if (result != -1) {
[Link]("Found at index " + result);
} else {
[Link]("Not Found");
}
}
}
Explanation:
●​ Requires sorted array for correct results.
●​ mid = (left + right) / 2 → finds midpoint index.
●​ If target > middle element → search right half.
●​ If target < middle element → search left half.
●​ Time complexity: O(log n).

B. Sorting Algorithms

1. Bubble Sort (Java with Explanation)

public class BubbleSort {

// Method to perform Bubble Sort

public static void bubbleSort(int[] arr) {
// Outer loop runs (n-1) times
for (int i = 0; i < [Link] - 1; i++) {
// Inner loop compares adjacent elements
for (int j = 0; j < [Link] - 1 - i; j++) {
// Swap if elements are in wrong order

Data Structures and Algorithms ​ ​ ​ Page 9 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

if (arr[j] > arr[j + 1]) {

int temp = arr[j]; // Store first value
arr[j] = arr[j + 1]; // Move second to first position
arr[j + 1] = temp; // Move stored value to second position
}
}
}
}

public static void main(String[] args) {

int[] numbers = {5, 2, 9, 1, 7};

bubbleSort(numbers);

// Print sorted array

for (int num : numbers) {
[Link](num + " ");
}
}
}
Explanation:
●​ Outer loop controls number of passes.
●​ Inner loop compares adjacent elements.
●​ Largest element moves to the end each pass (“bubbles up”).
●​ Time complexity: O(n²).

2. Selection Sort (Java with Explanation)

public class SelectionSort {

// Method to perform Selection Sort

public static void selectionSort(int[] arr) {

Data Structures and Algorithms ​ ​ ​ Page 10 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

for (int i = 0; i < [Link] - 1; i++) {

int minIndex = i; // Assume current position is smallest

// Find the smallest element in remaining array

for (int j = i + 1; j < [Link]; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // Update smallest index
}
}

// Swap smallest element with current position

int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

public static void main(String[] args) {

int[] numbers = {5, 2, 9, 1, 7};

selectionSort(numbers);

// Print sorted array

for (int num : numbers) {
[Link](num + " ");
}
}
}
Explanation:
●​ Finds the smallest element in unsorted part of array.
●​ Swaps smallest with first unsorted position.

Data Structures and Algorithms ​ ​ ​ Page 11 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

●​ Makes only n swaps, unlike Bubble Sort.

●​ Time complexity: O(n²).

3. Insertion Sort (Java with Explanation)

public class InsertionSort {

// Method to perform Insertion Sort

public static void insertionSort(int[] arr) {
// Start from the second element
for (int i = 1; i < [Link]; i++) {
int key = arr[i]; // Element to insert
int j = i - 1;

// Move elements greater than key to one position ahead

while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert key into correct position
arr[j + 1] = key;
}
}

public static void main(String[] args) {

int[] numbers = {5, 2, 9, 1, 7};

insertionSort(numbers);

// Print sorted array

for (int num : numbers) {
[Link](num + " ");

Data Structures and Algorithms ​ ​ ​ Page 12 | 13

 CITY COLLEGE OF SAN FERNANDO PAMPANGA
City of San Fernando, Pampanga
INSTITUTE OF INFORMATION TECHNOLOGY

}
}
}
Explanation:
●​ Treats the first element as already sorted.
●​ Takes next element and inserts into the correct place in sorted section.
●​ Efficient for nearly sorted data.
●​ Best case complexity: O(n), Worst: O(n²).

References (APA 7th ed.)

●​ Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th
ed.). MIT Press.
●​ Liang, Y. D. (2020). Introduction to Java programming and data structures (12th ed.).
Pearson.
●​ Oracle. (2024). The Java™ tutorials. [Link]
●​ Wirth, N. (2020). Algorithms and data structures. Springer.

Data Structures and Algorithms ​ ​ ​ Page 13 | 13