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.
Binary Search is a much faster searching algorithm but requires the list to be sorted beforehand.
| 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) |
Bubble Sort is a comparison-based sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order.
In Selection Sort, the list is divided into two parts: sorted and unsorted.
Insertion Sort works similarly to how we sort playing cards in our hands.
Merge Sort is a Divide and Conquer algorithm.
Quick Sort is also a Divide and Conquer algorithm. It picks an element as a pivot and partitions the array around the pivot.
| 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) |
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.