Array

1. Sorting Algorithms

Sorting arranges elements in a specific order (ascending or descending).

• Bubble Sort – Repeatedly swaps adjacent elements if they are in the wrong order.
• Selection Sort – Selects the smallest/largest element and places it in order.
• Insertion Sort – Builds the sorted array one element at a time.
• Merge Sort – Uses the divide-and-conquer technique to sort.
• Quick Sort – Selects a pivot and partitions elements around it.
• Heap Sort – Uses a binary heap to sort efficiently.
• Radix Sort – Sorts numbers digit by digit.
• Counting Sort – Counts occurrences of elements (used for small range values).
• Sorting

---

2. Searching Algorithms

Used to find an element in an array.

1. Linear Search

• Approach: Sequentially checks each element in the array.
• Time Complexity:
  • Best: O(1)
  • Worst: O(n)
  • Average: O(n)
• Space Complexity: O(1)

2. Binary Search (For Sorted Arrays Only)

• Approach: Repeatedly divides the array in half and searches in the relevant half.
• Time Complexity:
  • Best: O(1)
  • Worst: O(log n)
  • Average: O(log n)
• Space Complexity:
  • O(1) (Iterative)
  • O(log n) (Recursive, due to function call stack)

3. Jump Search (For Sorted Arrays)

• Approach: Jumps ahead by a block size (√n) and does a linear search within that block.
• Time Complexity:
  • Best: O(1)
  • Worst: O(√n)
  • Average: O(√n)
• Space Complexity: O(1)

4. Interpolation Search (For Uniformly Distributed Sorted Data)

Approach: Uses the formula to estimate the probable position of the target. $$ pos=left+ \frac {(target−arr[left])×(right−left)}{(arr[right]−arr[left])}​ $$

Sort

1. Comparison-Based Sorting

These algorithms compare elements to determine their order.

a. Bubble Sort

• Repeatedly swaps adjacent elements if they are in the wrong order.
• Time Complexity: O(n²)
• Space Complexity: O(1)

b. Selection Sort

• Finds the smallest element and places it in the correct position.
• Time Complexity: O(n²)
• Space Complexity: O(1)

c. Insertion Sort

• Picks one element at a time and places it in its correct position.
• Time Complexity: O(n²)
• Space Complexity: O(1)
• Efficient for small or nearly sorted data.

d. Merge Sort (Divide and Conquer)

• Divides the array into halves, sorts them, and merges them.
• Time Complexity: O(n log n)
• Space Complexity: O(n)

e. Quick Sort (Divide and Conquer)

• Picks a pivot, partitions the array, and sorts recursively.
• Time Complexity: O(n log n) (Best & Avg), O(n²) (Worst)
• Space Complexity: O(log n) (due to recursion)

f. Heap Sort

• Converts the array into a heap and extracts elements in order.
• Time Complexity: O(n log n)
• Space Complexity: O(1)

g. Shell Sort

• Variation of insertion sort that sorts elements at a gap.
• Time Complexity: O(n log n) (Best), O(n²) (Worst)
• Space Complexity: O(1)

2. Non-Comparison-Based Sorting

These algorithms do not compare elements directly.