Collin:COCS-2436

# Week 4: Sorting, Searching, and Algorithm Analysis

#### Objectives

- Understand why algorithm efficiency matters.
- Learn how to analyze algorithm performance.
- Introduce Big-O notation and common complexity classes: time and space.
- Implement and analyze simple searching and sorting algorithms.
- Understand how to compare objects in Java using `equals()`, `compareTo()`, `Comparable`, and `Comparator`.

---

## Why Study Algorithms?

#### Importance of Algorithm Analysis

- *Real-world problems:*
    - Traveling Through the City: Walking vs. Riding a Bus or Subway
    - Building a contact list app* 10 vs 10K
    - Google or Amazon Search: It processes billions of queries every day
- *Why Efficiency Matters:* How do we ensure our programs run as fast as possible, even with large data sets?
    - As data size grows, inefficiencies become costly.
    - Optimized algorithms scale better with large inputs.
- *Beyond Efficiency: Other Key Factors*
    - Resource Management: How much memory and computation does an algorithm use?
    - Scalability: Can the algorithm handle increasing amounts of data efficiently?
    - Predictability & Stability: Does the algorithm perform consistently across different datasets and conditions?

So, when we analyze an algorithm, we’re not just looking at speed—we’re considering memory use, scalability,
predictability, and practicality. That’s why understanding algorithm analysis is so important!

---

### Linear Search as Brute-Force Searching Example

- Introduce a naive approach to searching.
- Walk through how it checks each element one by one.  [{}]
- How to analyze this algorithm?

---

### Empirical vs Theoretical Analysis

#### Theoretical Analysis

- Theoretical analysis is the study of an algorithm's performance based on mathematical models.
- It focuses on how the algorithm behaves as the size of the input increases.
- We count the number of operations independent of actual execution.
- It uses Big O Notation to estimate the upper bound of the running time or memory usage.
- Steps in Theoretical Analysis:
    - Identify the basic operations in the algorithm (e.g., comparisons, swaps).
    - Count how many times these operations are performed based on the input size 𝑛.
    - Express this in Big O notation to generalize the performance.
- This is *more critical* because it allows us to predict performance across all scenarios, independent of specific
  machines.

---

#### Empirical Analysis

- Empirical analysis involves actually running the algorithm on different inputs and measuring its performance,
  typically in terms of time or memory usage.
- This type of analysis gives you a concrete understanding of how the algorithm performs in the real world, which can
  sometimes differ from theoretical expectations due to factors like hardware, caching, or system load.
- Steps in Empirical Analysis:
    - Implement the algorithm.
    - Choose different input sizes (e.g., arrays of 100, 500, 1000 elements).[{}]
    - Run the algorithm multiple times and record the time taken.
    - Compare the empirical results with the theoretical predictions.
- Empirical results fluctuate, while theoretical complexity stays consistent for all cases.

---

### Introduction to Big-O Notation

- A mathematical way to describe an algorithm's efficiency.
- Measures how execution time or space requirements grow with input size.
- Focuses on **worst-case scenarios** to provide upper-bound performance.
- Big-O: "O of n" or "Order of n".
- Examples:
    - **O(1):** Constant time → Looking up a book’s page number in an index.
    - **O(log n):** Logarithmic time → Binary search in a dictionary.
    - **O(n):** Linear time → Searching an unsorted contact list.
    - **O(n log n):** Linearithmic time → Merge sort, quicksort.
    - **O(n²):** Quadratic time → Comparing each student with every other student.
    - **O(2ⁿ):** Exponential time → Recursive Fibonacci sequence.
    - **O(n!):** Factorial time → Permutations of a set.

---
### ![img.png](assets/bigO.png)
---

### Analyzing Linear search:

- **Best case:** O(1) (element found at first position)
- **Worst case:** O(n) (element at last position or not present)

```java
public static int search(int[] arr, int target) {
 for (int i = 0; i < arr.length; i++) {
 if (arr[i] == target) {
 return i; // Found target at index i
 }
 }
 return -1; // Target not found
}
```

- Focuses on **worst-case scenarios** to provide upper-bound performance.
- **Time Complexity:** O(n) (Worst-case: checking every element)
- **Space Complexity:** O(1) (No additional memory used beyond input array)

---

### Why Focus on Time Complexity?

#### Why Not Just Run the Code?

- Running time can vary based on hardware and input size.
- We need a standard way to compare algorithms.

---

#### Time Complexity vs. Space Complexity

- *Time Complexity*: How fast does an algorithm run?
- *Space Complexity*: How much memory does it use?
- *Focus:* Optimizing time is usually more crucial in large-scale applications.
- Space complexity is also important, especially in memory-constrained environments. Mobile devices and Embedded
  systems.

---

## Smarter Searching: Binary Search

- Requires a sorted array.
- *Best case:* O(1) (middle element is target).
- *Worst case:* O(log n) (halving search space each step).

```java
public static int search(int[] arr, int target) {
 int left = 0, right = arr.length - 1;
 while (left <= right) {
 int mid = left + (right - left) / 2;
 if (arr[mid] == target) {
 return mid;
 }
 if (arr[mid] < target) {
 left = mid + 1;
 } else {
 right = mid - 1;
 }
 }
 return -1;
}
```

---

### Sorting Algorithms

- Sorting is one of the most fundamental tasks in computer science. They provide a solid foundation for understanding
 how to organize and manipulate data efficiently.
- Sorting involves arranging data in a particular order (usually ascending or descending).
- Sorting is a ubiquitous operation to Core of Many Applications.
- It's essential for tasks like searching, database indexing, and data visualization.
- They are used in various applications, from simple database queries to complex machine learning models.
- Sorting algorithms provide a strong foundation for problem-solving and advanced topics in computer science.

---

## Bubble Sort

- Bubble sort is one of the simplest sorting algorithms.
- It works by *repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping
 them if they are in the wrong order*.
- <iframe width="460" height="215" src="https://www.youtube.com/embed/yIQuKSwPlro?si=z8HloLyvAzNeEUA0" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>

```java
private static void bubbleSort(int[] arr) {
 // Loop through each element in the array
 for (int i = 0; i < arr.length; i++) {
 // Loop through the array up to the last unsorted element
 for (int j = 0; j < arr.length - i - 1; j++) {
 // If the current element is greater than the next element
 if (arr[j] > arr[j + 1]) {
 // Swap the elements
 int temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 }
 }
 }
}
```

- Time Complexity: ??
- Space Complexity: ??

---

## Selection Sort: Find the Smallest and Swap

- Selection sort is another simple sorting algorithm.
- It works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the first
  unsorted element. [{}]
- Time Complexity: ??
- Space Complexity: ??

---

## Insertion Sort: Sort as You Go

- Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time.
- It works by taking one element from the input data and inserting it into the correct position in the sorted part of
  the array. [{}]
- Efficient because it shifts elements instead of swapping frequently.
- Faster than Bubble Sort and Selection Sort in many cases.
    - Swapping involves three operations (read, write, read again), while shifting only moves memory values around.
    - Less swapping means better performance in practice
    - In modern processors, shifting is often faster than swapping because data movement in memory is optimized.
- Works well for small datasets and nearly sorted arrays.
- Time Complexity: ??
- Space Complexity: ??

---

## Complexity Comparisons

| Algorithm      | Best Case | Worst Case |
|----------------|-----------|------------|
| Linear Search  | O(1)      | O(n)       |
| Binary Search  | O(1)      | O(log n)   |
| Bubble Sort    | O(n)      | O(n²)      |
| Selection Sort | O(n²)     | O(n²)      |
| Insertion Sort | O(n)      | O(n²)      |

---

## Comparing Objects in Java

- So far, we have sorted and searched **primitive types (int, double, etc.)**.
- In real-world applications, we usually deal with **objects**, such as `Patient`, `Organ`, or `Student`.
- Sorting and searching objects requires defining how to compare them!

---

#### Ways to Compare Objects in Java

1. Using *`==`* Operator (Compares memory addresses)
2. Using *`.equals()`* Method (Checks if two objects are logically equal)

---

3. Using *`Comparable`* (Natural Ordering)**
    - Defines default sorting order for a class.
    - Used in `Arrays.sort()` and `Collections.sort()`. [{}]

4. Using *`Comparator`* (Custom Sorting)
    - Allows multiple sorting strategies without modifying the class.
    - Useful when we need different sorting orders (e.g., sort by name instead of id).

---

### When to Use What?
| Feature  | `==` | `.equals()` | `Comparable` | `Comparator` |
|----------------|------|-------------|--------------|--------------|
| Checks memory address           | YES  | .           | .            | .            |
| Checks value equality           | .    | YES         | .            | .            |
| Defines natural sorting         | .    | .           | YES          | .            |
| Allows multiple sorting options | .    | .           | .            | YES          |

---
### Knowledge 🧠 Check 
### http://quiz.codewithme.com
### ![img.png](assets/img.png)
---

### LABS
-----