Advanced Level • Lesson 2

📊 Data Structures and Algorithms

⏱️ 40 minutes 📚 Advanced 🎯 Efficiency & Optimization

📊

Master Data Structures and Algorithms!

Learn how to organize data efficiently and solve problems like a pro!

What are Data Structures?

Data structures are ways to organize and store data so we can use it efficiently. Think of them like different containers - a shopping list (array), a contact book (object), or a queue at a mamak stall!

Choosing the right data structure is like choosing the right tool - you wouldn't use a spoon to cut nasi lemak!

💡 Real-World Example: Grab uses arrays to store nearby drivers, objects to store driver details, and algorithms to find the fastest route to you!

Key Concepts

📋

Arrays

Ordered list of items. Like a queue at McDonald's - everyone has a position!

🗂️

Objects/JSON

Key-value pairs. Like a dictionary - look up words to get definitions!

🔄

Sorting

Arranging data in order. Like organizing apps alphabetically on your phone!

🔍

Searching

Finding specific data. Like searching for a contact in your phone!

⚡

Big O Notation

Measures algorithm efficiency. How fast does it run with lots of data?

🎯

Optimization

Making code faster and more efficient. Work smarter, not harder!

Arrays and Array Methods

📋 Working with Arrays

Arrays store ordered lists of data. Here are essential array methods:

                // Create an array of Malaysian foods
                let foods = ["Nasi Lemak", "Roti Canai", "Char Kway Teow"];

                // Add to end
                foods.push("Satay"); // ["Nasi Lemak", "Roti Canai", "Char Kway Teow", "Satay"]

                // Remove from end
                let last = foods.pop(); // "Satay"

                // Add to start
                foods.unshift("Rendang"); // ["Rendang", "Nasi Lemak", "Roti Canai", "Char Kway Teow"]

                // Remove from start
                let first = foods.shift(); // "Rendang"

                // Find index
                let index = foods.indexOf("Roti Canai"); // 1

                // Slice (get portion)
                let portion = foods.slice(0, 2); // ["Nasi Lemak", "Roti Canai"]

                // Map (transform each item)
                let uppercase = foods.map(food => food.toUpperCase());

                // Filter (keep only some items)
                let hasNasi = foods.filter(food => food.includes("Nasi"));

                // Sort alphabetically
                foods.sort(); // Alphabetical order
              

Objects and JSON

🗂️ Working with Objects

Objects store key-value pairs - perfect for structured data:

                // Object for a Grab driver
                let driver = {
                name: "Ahmad",
                car: "Proton X70",
                rating: 4.8,
                trips: 1250,
                location: {
                lat: 3.1390,
                lng: 101.6869
                }
                };

                // Access properties
                console.log(driver.name); // "Ahmad"
                console.log(driver.location.lat); // 3.1390

                // Add new property
                driver.available = true;

                // Convert to JSON (for sending to server)
                let json = JSON.stringify(driver);
                console.log(json); // String: '{"name":"Ahmad","car":"Proton X70"...}'

                // Parse JSON back to object
                let parsed = JSON.parse(json);
                console.log(parsed.name); // "Ahmad"

                // Array of objects (common pattern!)
                let drivers = [
                { name: "Ahmad", rating: 4.8, distance: 2 },
                { name: "Siti", rating: 4.9, distance: 1 },
                { name: "Kumar", rating: 4.7, distance: 3 }
                ];

                // Find closest driver
                let closest = drivers.sort((a, b) => a.distance - b.distance)[0];
                console.log(closest.name); // "Siti"
              

Bubble Sort Algorithm

🔄 Bubble Sort - Simple but Slow

Bubble sort compares adjacent items and swaps them if they're in the wrong order. Like bubbles rising to the top!

                function bubbleSort(arr) {
                let n = arr.length;

                for (let i = 0; i < n - 1; i++) { for (let j=0; j < n - i - 1; j++) { // Compare adjacent elements if
                  (arr[j]> arr[j + 1]) {
                  // Swap them
                  let temp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = temp;
                  }
                  }
                  }
                  return arr;
                  }

                  // Sort Grab driver distances
                  let distances = [5, 2, 8, 1, 9, 3];
                  console.log(bubbleSort(distances)); // [1, 2, 3, 5, 8, 9]

                  // Time Complexity: O(n²) - slow for large datasets!
              

Visualization:
[5, 2, 8, 1] → Compare 5 & 2, swap → [2, 5, 8, 1]
[2, 5, 8, 1] → Compare 5 & 8, no swap
[2, 5, 8, 1] → Compare 8 & 1, swap → [2, 5, 1, 8]
...continues until fully sorted!

Selection Sort Algorithm

🎯 Selection Sort - Find the Smallest

Selection sort finds the smallest element and moves it to the front. Repeat for the rest!

                function selectionSort(arr) {
                let n = arr.length;

                for (let i = 0; i < n - 1; i++) { // Find minimum element in remaining array let minIndex=i; for (let
                  j=i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex=j; } } // Swap minimum with first
                  element if (minIndex !==i) { let temp=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } } return
                  arr; } // Sort food prices let prices=[12, 5, 18, 3, 9]; console.log(selectionSort(prices)); // [3, 5,
                  9, 12, 18] // Time Complexity: O(n²) - also slow! 

Linear Search Algorithm

🔍 Linear Search - Check Every Item

Linear search checks each item one by one until it finds the target. Simple but can be slow!

                  function linearSearch(arr, target) {
                  for (let i = 0; i < arr.length; i++) { if (arr[i]===target) { return i; // Found it! Return the index
                    } } return -1; // Not found } // Search for a driver by name let driverNames=["Ahmad", "Siti"
                    , "Kumar" , "Fatimah" ]; let index=linearSearch(driverNames, "Kumar" ); console.log(index); // 2 //
                    Time Complexity: O(n) - checks every item in worst case 

Binary Search Algorithm

⚡ Binary Search - Divide and Conquer

Binary search is much faster but requires a SORTED array. It eliminates half the data each step!

                    function binarySearch(arr, target) {
                    let left = 0;
                    let right = arr.length - 1;

                    while (left <= right) { let mid=Math.floor((left + right) / 2); if (arr[mid]===target) { return mid;
                      // Found it! } else if (arr[mid] < target) { left=mid + 1; // Search right half } else { right=mid
                      - 1; // Search left half } } return -1; // Not found } // Search sorted prices let
                      sortedPrices=[3, 5, 9, 12, 18, 25, 30]; let result=binarySearch(sortedPrices, 12);
                      console.log(result); // 3 // Time Complexity: O(log n) - MUCH faster for large datasets! 

Search for 12 in [3, 5, 9, 12, 18, 25, 30]:
Step 1: Check middle (12) → Found it!

Search for 25:
Step 1: Check middle (12), 25 > 12 → Search right half [18, 25, 30]
Step 2: Check middle (25) → Found it!

Big O Notation - Algorithm Efficiency

⚡ Understanding Big O

Big O notation describes how an algorithm's performance scales with input size:

O(1) - Constant: Always takes same time (accessing array by index)
O(log n) - Logarithmic: Very fast (binary search)
O(n) - Linear: Grows with input (linear search, forEach)
O(n log n) - Fast sorting (JavaScript's built-in sort)
O(n²) - Quadratic: Slow for large data (bubble sort, nested loops)

                      // O(1) - Constant
                      let first = arr[0]; // Always takes same time

                      // O(n) - Linear
                      arr.forEach(item => console.log(item)); // Grows with array size

                      // O(log n) - Logarithmic
                      binarySearch(sortedArr, target); // Divides problem in half each step

                      // O(n²) - Quadratic (AVOID for large datasets!)
                      for (let i = 0; i < arr.length; i++) { for (let j=0; j < arr.length; j++) { // Nested loops=n²
                        operations! } } 

Common Mistakes to Avoid

⚠️ Watch Out For:

Binary search on unsorted data: Must sort first!
Modifying array while looping: Can cause bugs
Using slow algorithms for large data: O(n²) is bad for 10,000+ items
Forgetting to return -1: Search functions should return -1 when not found
Not considering edge cases: Empty arrays, single items, duplicates

Summary

You've learned:

✅ Arrays store ordered lists with useful methods (push, pop, map, filter)
✅ Objects store key-value pairs, JSON converts between string and object
✅ Bubble sort and selection sort are O(n²) - simple but slow
✅ Linear search is O(n), binary search is O(log n) - much faster!
✅ Big O notation measures algorithm efficiency
✅ Choose the right data structure and algorithm for the job!

🎮 Interactive Challenge: Practice Algorithms!

🔄 Challenge 1: Implement Bubble Sort

Write bubble sort to sort Malaysian state names alphabetically:

🔍 Challenge 2: Search Algorithm

Implement binary search to find a price in a sorted array:

📊 Challenge 3: Array Methods

Use array methods to manipulate data:

💡 Tip: Test your algorithms with different inputs - empty arrays, single items, already sorted, reverse sorted!

🎯 Activity: Algorithm Performance Comparison

What You'll Do:

Compare the performance of different sorting and searching algorithms!

Instructions:

Create an array of 100 random numbers
Time how long bubble sort takes (use console.time())
Time how long selection sort takes
Time how long JavaScript's built-in sort() takes
Compare the results - which is fastest?
Try with 1000 numbers - what happens?

Bonus Challenges:

Compare linear vs binary search speed
Create visualizations showing how each algorithm works
Test with different data types (strings, objects)

🏆 Challenge: Can you implement a more efficient sorting algorithm? Research "merge sort" or "quick sort"!

💪 Practice Challenges

Challenge 1: Grab Route Optimization

Create a system to find the shortest route for a Grab driver:

Array of destinations with distances: [{ name: "KLCC", distance: 5 }, ...]
Sort destinations by distance (closest first)
Filter out destinations more than 10km away
Calculate total travel distance
Use binary search to find a specific destination

Bonus: Add traffic factor - multiply distance by 1.5 during peak hours!

Challenge 2: E-Commerce Product Search

Build a product search and filter system:

Array of products (name, price, category, rating)
Implement search by name (linear search)
Sort products by price (low to high, high to low)
Filter by category and minimum rating
Find products in price range using binary search

Challenge 3: Student Grade Analytics

Analyze student performance data:

Array of students with grades: [{ name: "Ahmad", grades: [85, 90, 78] }, ...]
Calculate average grade for each student (use map)
Find students with average > 80 (use filter)
Sort students by average grade
Find top 3 students
Implement search to find student by name

Challenge 4: Food Delivery Optimization

Create a food delivery management system:

Array of orders: [{ id: 1, restaurant: "Mamak", customer: "Ahmad", distance: 3, time: 20 }, ...]
Sort orders by delivery time (urgent first)
Filter orders within 5km radius
Group orders by restaurant (use objects)
Calculate total delivery fees based on distance
Implement binary search to find order by ID

Think about Big O: Which operations are O(1), O(n), or O(n²)?