Unit IV: Searching and Sorting
1. Linear Search
Linear Search is the simplest searching algorithm. It works by sequentially checking each element of the list until a match is found or the whole list has been searched.
- Procedure: Start from the first element and compare it with the target value. Move to the next element until found.
- Applicability: Can be used on both sorted and unsorted lists.
- Best Case: Target is at the first position O(1).
- Worst Case: Target is at the last position or not present O(n).
2. Binary Search
Binary Search is a much faster searching algorithm but requires the list to be sorted beforehand.
- Procedure: It repeatedly divides the search interval in half. If the target value is less than the middle element, it narrows the interval to the lower half; otherwise, it narrows it to the upper half.
- Complexity: O(log n).
Comparison: Linear vs. Binary Search
| Feature | Linear Search | Binary Search |
|---|---|---|
| Data Requirement | Unsorted or Sorted | Strictly Sorted |
| Complexity | O(n) | O(log n) |
| Efficiency | Low (for large data) | High (for large data) |
3. Bubble Sort
Bubble Sort is a comparison-based sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order.
- Mechanism: Large values "bubble up" to the end of the list in each pass.
- Complexity: Worst and Average case O(n²).
4. Selection Sort
In Selection Sort, the list is divided into two parts: sorted and unsorted.
- Mechanism: It repeatedly finds the minimum element from the unsorted part and puts it at the beginning.
- Complexity: Always O(n²) regardless of initial order.
5. Insertion Sort
Insertion Sort works similarly to how we sort playing cards in our hands.
- Mechanism: It takes one element from the unsorted part and "inserts" it into its correct position in the sorted part.
- Complexity: Best case O(n) (already sorted); Worst case O(n²).
6. Merge Sort
Merge Sort is a Divide and Conquer algorithm.
- Procedure: It divides the array into two halves, calls itself for the two halves, and then merges the two sorted halves.
- Complexity: O(n log n) in all cases.
- Stability: It is a stable sort (preserves order of equal elements).
7. Quick Sort
Quick Sort is also a Divide and Conquer algorithm. It picks an element as a pivot and partitions the array around the pivot.
- Procedure: Elements smaller than the pivot go to the left, and larger elements go to the right.
- Complexity: Average case O(n log n); Worst case O(n²) (if pivot selection is poor).
8. Comparisons of Sorting Techniques
| Algorithm | Best Complexity | Worst Complexity | Space Complexity |
|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n²) | O(log n) |
Exam Tips & Warnings
- Merge Sort is preferred for linked lists but requires extra space for arrays.
- Quick Sort is generally the fastest in practice but has a bad worst-case performance.
- Selection Sort minimizes the number of swaps, making it useful when memory writing is costly.
Frequently Asked Questions
Q: Why is Binary Search better than Linear Search?
Binary search drastically reduces the number of comparisons. For 1 million elements, Linear Search might take 1,000,000 steps, while Binary Search takes only about 20 steps.
Q: What is a "Pivot" in Quick Sort?
The pivot is a reference element used to partition the data into two subsets: those smaller than the pivot and those larger.