Bubble Sort
Bubble Sort एक simple comparison-based sorting algorithm है, जिसमें list के adjacent (पास-पास वाले) elements को compare किया जाता है, और अगर उनका order गलत हो तो swap कर दिया जाता है।
यह process बार-बार दोहराया जाता है, जब तक पूरा list sorted न हो जाए।
इसमें छोटे या बड़े elements “bubble” की तरह ऊपर (या सही position) तक पहुँच जाते हैं — इसलिए इसका नाम Bubble Sort रखा गया है।
Key Points :
- यह comparison-based sorting technique है।
- हर pass में adjacent elements compare और swap किए जाते हैं।
- Sorting process तब तक चलता है जब तक कोई swap न हो (list sorted हो जाए)।
- इसकी time complexity O(n²) होती है — इसलिए यह slow होता है।
- सीखने और implement करने में बहुत आसान है।
Time complexity : O(n²) (Slow)
Space complexity : O(1) (In-place)
Working Process (कार्य प्रक्रिया)
1. सबसे पहले array के पहले दो elements को compare किया जाता है।
- arr[ j ] और arr[ j + 1 ]
- यह check करता है कि क्या वे सही order में हैं या नहीं।
2. यदि पहला element > दूसरा element होता है, तो दोनों का swap किया जाता है।
- arr[ j ] > arr[ j + 1 ] → swap
3. इसके बाद अगले pair (index 1 और index 2) को compare किया जाता है।
4. यही compare–swap वाला process पूरे array में repeat होता है।
5. पहला pass पूरा होने पर सबसे बड़ा element अपनी सही जगह, यानी last position, पर पहुँच जाता है।
6. दूसरे pass से last element को ignore किया जाता है क्योंकि वह already sorted है।
7. यही प्रक्रिया बार-बार चलती रहती है, जब तक array के सभी elements पूरी तरह sorted न हो जाएँ।
Example (उदाहरण)
Array : [ 5, 1, 4, 2 ]
Initial State : [ 5, 1, 4, 2 ]
Pass 1 — Largest element end पर जाएगा
- Step 1 : Compare 5 & 1 → Swap
Before : 5 1
| |
After : 1 5
| |
Array → [1, 5, 4, 2]
- Step 2 : Compare 5 & 4 → Swap
Before : 5 4
| |
After : 4 5
| |
Array → [1, 4, 5, 2]
- Step 3 : Compare 5 & 2 → Swap
Before : 5 2
| |
After : 2 5
| |
Array → [1, 4, 2, 5]
Pass 2 — Next largest bubble up होगा
- Step 1 : Compare 1 & 4 → No Swap
Before : 1 4
| |
Array → [1, 4, 2, 5]
- Step 2 : Compare 4 & 2 → Swap
Before : 4 2
| |
After : 2 4
| |
Array → [1, 2, 4, 5]
Pass 3 — Sorted
1 2 4 5
| | | |
(sorted)
Final Output : [1, 2, 4, 5]
Pseudo Code
BubbleSort(array)
n = length(array)
for i = 0 to n-1
for j = 0 to n-i-2
if array[j] > array[j+1]
swap(array[j], array[j+1])
Advantages of Bubble Sort (लाभ)
- Simple and Easy to Understand
- सीखने और implement करने में बहुत आसान।
- In-place Sorting
- Extra memory की आवश्यकता नहीं होती।
- Stable Algorithm
- समान value वाले elements का relative order preserved रहता है।
- Good for Small Datasets
- छोटे datasets में जल्दी काम करता है।
- Detects Already Sorted Array (Optimized Version)
- अगर array पहले से sorted है, तो algorithm जल्दी stop कर सकता है।
Disadvantages of Bubble Sort (हानियाँ)
- Inefficient for Large Datasets
- Time Complexity O(n²) होने के कारण बड़े datasets में slow होता है।
- Many Comparisons and Swaps
- बार-बार adjacent elements की तुलना और swap करनी पड़ती है।
- Not Practical for Real Applications
- Large scale sorting के लिए rarely use किया जाता है।
- Slow Performance
- Worst और Average case में बहुत समय लग सकता है।
Quick Sort
Quick Sort एक efficient, comparison-based, divide and conquer sorting algorithm है। Array को smaller sub-arrays में divide करता है, और recursively sort करता है।
- सबसे पहले pivot element चुना जाता है, और array को pivot के आधार पर partition किया जाता है।
- Recursive process तब तक चलता है, जब तक sub-array में 1 या 0 element न बच जाए।
Type : Comparison-based
Method : Divide and Conquer
Time Complexity :
- Best Case : O(n log n)
- Average Case : O(n log n)
- Worst Case : O(n²) (अगर pivot हमेशा smallest या largest चुना जाए)
Space Complexity : O(log n) (Recursive stack)
Stability : Not stable
Working Process (कार्य प्रक्रिया)
Step 1 – Pivot Selection (Pivot चुनना)
- Array में से एक element को pivot चुनो।
- Pivot selection के common तरीके –
- First element
- Last element
- Middle element
- Random element
Step 2 – Partitioning (विभाजन करना)
- Array को दो हिस्सों में divide करो –
- Left : Pivot से छोटे elements
- Right : Pivot से बड़े elements
- Pivot को उसकी correct sorted position में place करो।
Step 3 – Recursive Sorting (पुनरावृत्ति)
- Left और Right sub-arrays पर same process apply करो।
- Process तब तक दोहराओ जब तक sub-array में केवल 1 या 0 element न बच जाए।
Step 4 – Combining (जोड़ना)
जब सभी sub-arrays sort हो जाएँ, तो final array automatically sorted हो जाएगा।
Example (उदाहरण)
Array : [8, 4, 7, 9, 3, 10, 5]
Pivot : Last element → 5
Step 1 – Partition
- Left :
[4, 3](less than 5) - Pivot :
[5] - Right :
[8, 7, 9, 10](greater than 5)
Step 2 – Recursive Sorting Left [4, 3]
Pivot = 3 → Left :
[], Pivot : 3, Right :[4]→ Sorted Left =[3, 4]
Step 3 – Recursive Sorting Right [8, 7, 9, 10]
- Pivot = 10 → Left :
[8, 7, 9], Pivot : 10, Right :[] [8, 7, 9]→ Pivot = 9 → Left :[8, 7], Pivot : 9, Right :[][8, 7]→ Pivot = 7 → Left :[], Pivot : 7, Right :[8]→ Sorted =[7, 8]- Combine →
[7, 8, 9, 10]
Final Sorted Array : [3, 4, 5, 7, 8, 9, 10]
Pseudo Code
QuickSort(arr, low, high):
if low < high:
pivot_index = Partition(arr, low, high)
QuickSort(arr, low, pivot_index – 1)
QuickSort(arr, pivot_index + 1, high)
Partition(arr, low, high):
pivot = arr[high]
i = low – 1
for j = low to high-1:
if arr[j] < pivot:
i = i + 1
swap arr[i] and arr[j]
swap arr[i+1] and arr[high]
return i+1
Advantages of Quick Sort (लाभ)
- Fast and Efficient – Large datasets में Quick Sort बहुत जल्दी काम करता है।
- In-Place Sorting – Array को extra memory के बिना sort करता है (O(1) extra space)।
- Divide and Conquer – Recursive method से array को छोटे हिस्सों में बाँटकर जल्दी sort करता है।
- Average Case Performance – Average case में time complexity O(n log n) है।
- Widely Used in Practice – Real-world applications और programming libraries में बहुत common।
Disadvantages of Quick Sort (हानियाँ)
- Worst Case O(n²) – अगर pivot हमेशा smallest या largest चुना जाए।
- Not Stable – Equal elements का relative order बदल सकता है।
- Recursive Calls– Recursive होने के कारण stack space O(log n) लेता है।
- Pivot Selection Sensitive – गलत pivot selection से performance बहुत प्रभावित हो सकती है।
