Sorting & Searching

Sorting and searching are fundamental operations in computer science, critical for efficiently organizing and retrieving data.

Sorting Algorithms

Comparison-Based Sorting

1. Bubble Sort

   • Time Complexity: O(n²)
   • Space Complexity: O(1)
   • Stable: Yes

2. Selection Sort

   • Time Complexity: O(n²)
   • Space Complexity: O(1)
   • Stable: No

3. Insertion Sort

   • Time Complexity: O(n²)
   • Space Complexity: O(1)
   • Stable: Yes

4. Merge Sort

   • Time Complexity: O(n log n)
   • Space Complexity: O(n)
   • Stable: Yes

5. Quick Sort

   • Time Complexity: O(n log n) average, O(n²) worst
   • Space Complexity: O(log n)
   • Stable: No

6. Heap Sort

   • Time Complexity: O(n log n)
   • Space Complexity: O(1)
   • Stable: No

Non-Comparison Sorting

1. Counting Sort

   • Time Complexity: O(n + k)
   • Space Complexity: O(n + k)
   • Stable: Yes

2. Radix Sort

   • Time Complexity: O(d * (n + k))
   • Space Complexity: O(n + k)
   • Stable: Yes

Searching Algorithms

1. Linear Search

   • Time Complexity: O(n)

2. Binary Search

   • Time Complexity: O(log n)
   • Requires sorted data

3. Depth-First Search (DFS)

   • Used for traversing or searching tree or graph structures

4. Breadth-First Search (BFS)

   • Used for traversing or searching tree or graph structures

Common Problems

1. Search in Rotated Sorted Array
2. Find First and Last Position of Element in Sorted Array
3. Merge Intervals
4. Kth Largest Element in an Array
5. Top K Frequent Elements