7. Searching and Sorting Algorithms

Linear search is the simplest way to find an item in a list. You start at the first element and move one by one until you either find the value or reach the end. It does not need the list to be sorted.

This method is easy to understand and implement but can be slow for large lists because it may have to check every element. Still, for small collections or occasional lookups, the simplicity often outweighs performance concerns.

Linear search is useful when:

• The list is unsorted
• The list is small
• You care more about readability than speed

Binary search is a faster search method but works only on sorted lists. The idea is to repeatedly cut the search space in half. You compare the target value to the middle element; if it’s smaller, you search the left half; if larger, the right half.

This approach greatly reduces the number of comparisons. Instead of checking every element, you narrow down quickly. However, you must maintain the list in sorted order, which may add overhead when inserting new elements.

Binary search is helpful when:

• The data is sorted (or can be kept sorted)
• You perform many searches
• Performance matters for large datasets

Bubble sort is a simple sorting algorithm where adjacent elements are repeatedly compared and swapped if they are out of order. Larger elements “bubble” to the end of the list with each pass.

It is easy to understand and a good teaching tool, but not efficient for large datasets. It makes many passes through the list and can be quite slow compared to more advanced algorithms.

Bubble sort is mainly used:

• For learning how sorting works
• For very small lists where performance doesn’t matter

Selection Sort
Selection sort works by repeatedly finding the smallest (or largest) element from the unsorted part and moving it to the correct position. It divides the list into a sorted and unsorted portion and expands the sorted part step by step.

It makes fewer swaps than bubble sort but still requires many comparisons. It is simple to code and good for educational purposes or very small inputs.

Insertion Sort
Insertion sort builds the sorted list one element at a time. It takes each new element and inserts it into the correct position within the part that is already sorted, similar to arranging playing cards in order.

Insertion sort performs well on small lists or lists that are already nearly sorted. It is often used inside other algorithms when working on small subarrays.