sorting

🔹 1. Bubble Sort

💡 Concept:

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

⚙️ How it Works:

• Compare first and second elements
• Swap if needed
• Continue for the entire array
• Repeat until no swaps are needed

⏱️ Complexity:

• Time: O(n²)
• Space: O(1)

✅ Best For:

• Small datasets
• Learning purposes

---

🔹 2. Selection Sort

💡 Concept:

Find the minimum element and place it at the beginning.

⚙️ Steps:

• Find the smallest element in the array
• Swap it with the first element
• Repeat for the remaining array

⏱️ Complexity:

• Time: O(n²)
• Space: O(1)

✅ Best For:

• Simple implementations

---

🔹 3. Insertion Sort

💡 Concept:

Build the sorted array one element at a time.

⚙️ Steps:

• Take one element
• Insert it into its correct position in the sorted part

⏱️ Complexity:

• Time: O(n²), Best case: O(n)
• Space: O(1)

✅ Best For:

• Nearly sorted arrays

---

🔹 4. Merge Sort

💡 Concept:

Divide and conquer algorithm.

⚙️ Steps:

• Divide array into halves
• Recursively sort each half
• Merge sorted halves

⏱️ Complexity:

• Time: O(n log n)
• Space: O(n)

✅ Best For:

• Large datasets
• Stable sorting

---

🔹 5. Quick Sort

💡 Concept:

Pick a pivot and partition the array around it.

⚙️ Steps:

• Choose a pivot
• Place smaller elements to left, larger to right
• Recursively apply to subarrays

⏱️ Complexity:

• Average: O(n log n)
• Worst: O(n²)

✅ Best For:

• Fast practical sorting

---

🔹 6. Heap Sort

💡 Concept:

Uses a binary heap structure.

⚙️ Steps:

• Build a max heap
• Extract maximum repeatedly

⏱️ Complexity:

• Time: O(n log n)
• Space: O(1)

✅ Best For:

• Memory-efficient sorting

---

🔹 7. Counting Sort

💡 Concept:

Counts frequency of elements.

⚙️ Steps:

• Count occurrences
• Place elements accordingly

⏱️ Complexity:

• Time: O(n + k)
• Space: O(k)

✅ Best For:

• Small range integers

---

🔹 8. Radix Sort

💡 Concept:

Sort numbers digit by digit.

⚙️ Steps:

• Sort based on least significant digit
• Move to most significant digit

⏱️ Complexity:

• Time: O(nk)
• Space: O(n + k)

✅ Best For:

• Large numbers

---

Comparison Table

Algorithm	Time Complexity	Space	Stable
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	No
Insertion Sort	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(log n)	No
Heap Sort	O(n log n)	O(1)	No
Counting Sort	O(n + k)	O(k)	Yes
Radix Sort	O(nk)	O(n+k)	Yes

---