# 2.2 Common Computing Algorithms This section outlines fundamental algorithms used in computer science for sorting and searching data, explaining their mechanics and evaluating them through the lens of computational thinking. ## Sorting Algorithms *Sorting algorithms* are used to arrange data into a specific order, such as ascending or descending. This makes the data more useful for subsequent operations like searching. ### a) Insertion Sort An algorithm that builds the final sorted array one item at a time. It iterates through an input array and removes one element per iteration, finds the place the element belongs in the sorted part of the array, and inserts it there. **i. Working of Insertion Sort** The algorithm divides the array into a sorted and an unsorted part. It picks an element from the unsorted part and places it at its correct position in the sorted part. **Example:** Sort the array `[12, 31, 25, 8, 32, 17]` in ascending order. 1. **Start:** `[12, 31, 25, 8, 32, 17]` - Assume the first element `12` is the initial sorted part. 2. **Pick `31`:** Compare `31` with `12`. Since `31 > 12`, it's in the correct relative order. - Sorted: `[12, 31]` - Array: `[12, 31, 25, 8, 32, 17]` 3. **Pick `25`:** Compare `25` with `31`. Since `25 < 31`, swap them. - Array: `[12, 25, 31, 8, 32, 17]` - Compare `25` with `12`. Since `25 > 12`, it's in the correct position. - Sorted: `[12, 25, 31]` 4. **Pick `8`:** Compare `8` with `31` (swap), then `25` (swap), then `12` (swap). - `[12, 25, 8, 31, 32, 17]` - `[12, 8, 25, 31, 32, 17]` - `[8, 12, 25, 31, 32, 17]` - Sorted: `[8, 12, 25, 31]` 5. **Pick `32`:** Compare `32` with `31`. Since `32 > 31`, no swap is needed. - Sorted: `[8, 12, 25, 31, 32]` 6. **Pick `17`:** Compare `17` with `32` (swap), `31` (swap), `25` (swap). Compare with `12`, no swap needed. - `[8, 12, 25, 31, 17, 32]` - `[8, 12, 25, 17, 31, 32]` - `[8, 12, 17, 25, 31, 32]` 7. **Final Sorted Array:** `[8, 12, 17, 25, 31, 32]` **ii. Insertion Sort in Computational Thinking** - **Abstraction:** Gradually build a sorted collection by picking one item at a time and inserting it into its correct position among the already-sorted items. - **Decomposition:** - **Pick and Insert:** Take the next unsorted item. - **Find Correct Position:** Compare it with elements in the sorted portion and shift elements to make space. - **Insert:** Place the item in the created space. - **Pattern Recognition:** The process of picking, comparing, shifting, and inserting is repeated for every element in the unsorted portion. - **Algorithmic Design:** 1. Start with the second element. 2. Store this current element. 3. Compare it with elements in the sorted part (to its left). 4. Shift larger elements one position to the right. 5. Insert the current element into its correct position. 6. Repeat for all remaining elements. ### b) Bubble Sort A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The passes through the list are repeated until the list is sorted. **i. Working of Bubble Sort** In each pass, the largest unsorted element "bubbles" up to its correct position at the end of the unsorted section. **Example:** Sort the array `[13, 32, 26, 35, 10]` - **First Iteration:** - `(13, 32)` -> No swap. Array: `[13, 32, 26, 35, 10]` - `(32, 26)` -> Swap. Array: `[13, 26, 32, 35, 10]` - `(32, 35)` -> No swap. Array: `[13, 26, 32, 35, 10]` - `(35, 10)` -> Swap. Array: `[13, 26, 32, 10, 35]` - *Result:* The largest element `35` is now at the end. - **Second Iteration:** - `(13, 26)` -> No swap. - `(26, 32)` -> No swap. - `(32, 10)` -> Swap. Array: `[13, 26, 10, 32, 35]` - *Result:* The second largest element `32` is in position. - **Third Iteration:** - `(13, 26)` -> No swap. - `(26, 10)` -> Swap. Array: `[13, 10, 26, 32, 35]` - **Fourth Iteration:** - `(13, 10)` -> Swap. Array: `[10, 13, 26, 32, 35]` - **Final Sorted Array:** `[10, 13, 26, 32, 35]` **ii. Bubble Sort in Computational Thinking** - **Abstraction:** Achieve order by repeatedly comparing and swapping adjacent items. - **Decomposition:** - **Adjacent Comparison:** Compare a pair of adjacent items. - **Swap Logic:** If the pair is out of order, swap them. - **Iteration:** Repeat the process in passes until no more swaps are needed. - **Pattern Recognition:** The core pattern is the pairwise comparison and swapping, which is repeated across the array in multiple passes. - **Algorithmic Design:** 1. Start from the first element. 2. Compare the current element with the next element. Swap if the current is larger. 3. Move to the next pair and repeat until the end of the array. This completes one pass. 4. After each pass, the next largest element is in its correct place. 5. Repeat the passes for the remaining unsorted portion of the array. 6. Continue until the entire array is sorted. | Table 2.2 - Insertion Vs. Bubble Sort | Insertion Sort | Bubble Sort | | :--- | :--- | :--- | | **When to use** | Small number of items, nearly sorted data. | Small number of items, often used for educational purposes. | | **Typical Application**| Practical for small datasets. | Primarily for teaching basic sorting concepts. | ## Searching Algorithms *Searching algorithms* are used to find a specific element (*target*) within a collection of elements. ### a) Binary Search A highly efficient search algorithm that works on ***sorted lists***. It follows a "divide and conquer" approach. **i. Working of Binary Search** The algorithm compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half. **Example:** Find the number `56` in the sorted array `[10, 12, 24, 29, 39, 40, 51, 56, 69]` 1. **Start:** Array: `[10, 12, 24, 29, 39, 40, 51, 56, 69]`. Middle element is `39`. - Compare `56` with `39`. Since `56 > 39`, the target must be in the right half. 2. **New Search Space:** `[40, 51, 56, 69]`. Middle element is `51`. - Compare `56` with `51`. Since `56 > 51`, take the right half again. 3. **New Search Space:** `[56, 69]`. Middle element is `56`. - Compare `56` with `56`. A match is found at index `7`. 4. **Result:** The algorithm returns the location `7`. **ii. Binary Search in Computational Thinking** - **Abstraction:** Find an item by repeatedly dividing the search space in half. - **Decomposition:** - **Middle Item Check:** Compare the target with the middle item. - **Search Space Division:** Discard the half where the target cannot be. - **Recursion:** Repeat the process on the remaining half. - **Pattern Recognition:** The core pattern is halving the search space in each step. - **Algorithmic Design:** 1. Start with the entire sorted array. 2. Find and check the middle element. 3. If it matches the target, the search is complete. 4. If the target is smaller, repeat the search on the left half. 5. If the target is larger, repeat the search on the right half. 6. Continue until the target is found or the search space is empty. ### b) Linear Search (Sequential Search) A simple algorithm that checks every element in a list one by one until the desired element is found or the list ends. This method can be used on ***unsorted lists***. **i. Working of Linear Search** Start from the first element and compare it with the target. If they match, return the index. If not, move to the next element and repeat. **Example:** Find the number `41` in the array `[70, 40, 30, 11, 57, 41, 25, 14, 56]` 1. Compare `41` with `70` (index 0). No match. 2. Compare `41` with `40` (index 1). No match. 3. Compare `41` with `30` (index 2). No match. 4. Compare `41` with `11` (index 3). No match. 5. Compare `41` with `57` (index 4). No match. 6. Compare `41` with `41` (index 5). Match found! 7. **Result:** The algorithm returns the location `5`. **ii. Linear Search in Computational Thinking** - **Abstraction:** Find an item by checking each item sequentially from the beginning. - **Decomposition:** - **Start Point:** Begin at the first item. - **Item Checking:** Compare the current item with the target. - **Stopping Condition:** Stop when the item is found or the end of the list is reached. - **Pattern Recognition:** The pattern is a linear, sequential progression through the collection. - **Algorithmic Design:** 1. Start at the first element. 2. Check if the current element equals the target. 3. If it is, the search is complete. 4. If not, move to the next element. 5. Repeat until the target is found or the end of the array is reached. | Table 2.3 - Linear Vs. Binary Search | Linear Search | Binary Search | | :--- | :--- | :--- | | **Prerequisite** | None (works on sorted or unsorted lists) | **List must be sorted** | | **When to use** | Small number of elements or unsorted lists. | Large number of elements. | | **Efficiency** | Less efficient for large datasets (O(n)). | Very efficient for large datasets (O(log n)). | ## Possible Questions/Answers - **Q:** What is the primary purpose of a sorting algorithm? **A:** To arrange data in a specific order (e.g., ascending or descending) to make it easier to read and search. - **Q:** What is the main difference between how Insertion Sort and Bubble Sort work? **A:** Insertion Sort builds a sorted section by inserting elements into their correct place, one by one. Bubble Sort repeatedly compares and swaps adjacent elements, causing the largest unsorted items to "bubble" to the end with each pass. - **Q:** What is the most important prerequisite for using Binary Search? **A:** The list or array of elements must be sorted beforehand. - **Q:** Why is Binary Search generally faster than Linear Search for large lists? **A:** Binary Search eliminates half of the remaining search space with each comparison, drastically reducing the number of checks needed. Linear Search must check every element in the worst-case scenario.