Chapter 7DSA (Data Structures & Algorithms)~1 min read
Sorting Algorithms
Data Sort करायला शिका
Sorting म्हणजे elements विशिष्ट order मध्ये arrange करणे. वेगवेगळ्या sorting algorithms च्या time complexities वेगळ्या असतात. Merge Sort आणि Quick Sort च्या O(n log n) complexity ने production मध्ये वापरले जातात.
Bubble Sort — O(n²) — simple but slow
python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # Already sorted — early exit
break
return arr
print(bubble_sort([64, 34, 25, 12, 22])) # [12, 22, 25, 34, 64]Merge Sort — O(n log n) — divide and conquer
python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # Divide
right = merge_sort(arr[mid:]) # Divide
return merge(left, right) # Conquer
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([38, 27, 43, 3, 9])) # [3, 9, 27, 38, 43]- ▸Bubble Sort: O(n²) — simple, slow
- ▸Selection Sort: O(n²) — simple, slow
- ▸Insertion Sort: O(n²) avg, O(n) best — good for small/nearly sorted
- ▸Merge Sort: O(n log n) — stable, extra space
- ▸Quick Sort: O(n log n) avg, O(n²) worst — in-place, fast in practice
- ▸Python built-in sort: Timsort — O(n log n)
✅ Key Points — लक्षात ठेवा
- ▸Production: Quick Sort किंवा Merge Sort
- ▸Stable sort: equal elements चा order preserve
- ▸Python sorted() / .sort() — O(n log n) Timsort
- ▸Interview: Merge Sort implement करणे common
- ▸Divide and Conquer — recursion वापरतात
0/10 chapters पूर्ण