Algorithms: Sorting and Searching
Algorithms are step-by-step procedures for calculations, data processing, and automated reasoning. Two of the most fundamental categories of algorithms in computer science are Searching and Sorting.
1. Searching Algorithms
Searching is the process of finding a specific element within a collection of data.
Linear Search
The simplest method. It checks every element in the list sequentially until the desired element is found or the list ends.
- Time Complexity: O(n) (Linear time)
- Best for: Unsorted or small lists.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1Binary Search
A much faster algorithm that works by repeatedly dividing the search interval in half. The array must be sorted first.
- Time Complexity: O(log n) (Logarithmic time)
- Best for: Large, sorted lists.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -12. Sorting Algorithms
Sorting is the process of arranging data in a particular order (usually ascending or descending).
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.
- Time Complexity: O(nĀ²) (Quadratic time)
- Usage: Educational purposes; rarely used in production due to slowness.
function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}Merge Sort
A "Divide and Conquer" algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
- Time Complexity: O(n log n)
- Usage: General purpose, stable sort.
Quick Sort
Another "Divide and Conquer" algorithm. It picks an element as a "pivot" and partitions the given array around the picked pivot.
- Time Complexity: O(n log n) on average.
- Usage: Very fast in practice, standard in many libraries.