Searching and Sorting Algorithms: Python

Sort Algo:

Sorting Algorithm Comparison Table :

Algorithm	Best Case	Worst Case	Space	Stable?	In-Place?
Bubble Sort	$O(n)$	$O(n^2)$	$O(1)$	Yes	Yes
Quick Sort	$O(n \log n)$	$O(n^2)$	$O(\log n)$	No	Yes
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes	No
Timsort (Python Built-in)	$O(n)$	$O(n \log n)$	$O(n)$	Yes	No

Bubble Sort - Nested loop 

for i in range(n):
for j in range(n-i-1):

If the array is already sorted:

[1, 2, 3, 4, 5]

the algorithm can stop after one pass.

Selection Sort - Find the smallest element and put it at the beginning.

Insertion Sort - key is the element we're trying to insert into the already-sorted portion.

Insertion Sort is actually useful when:

• Data is almost sorted

• Dataset is small.You need an in-place algorithm

Searching Algo:

Binary Search (The Gold Standard for Search) - Binary Search works on a sorted array.

• Concept: Divide and conquer on a sorted list.

• Step-by-Step Dry Run:

1. Start with low = 0, high = len - 1.

2. Find mid.

3. If target == mid, return.

4. If target < mid, high = mid - 1.

5. Else, low = mid + 1.

   
   
   

Linear Search
Linear Search means checking every element one by one until we find the target.
arr = [10, 25, 30, 45, 50]
target = 45

Basic Algorithm

For every element:

1. Check whether it equals the target.

2. If yes → return its index.

3. Otherwise continue.

4. If we reach the end → target doesn't exist.

        Use it when:

• The array is unsorted
• The array is small
• You only need to search once
• Sorting the data isn't worth the cost