Selection Sort
Selection Sort एक comparison-based sorting algorithm है, जिसमें हम array / list के elements को ascending या descending order में arrange करने के लिए हर step पर minimum (या maximum) element चुनते हैं और उसे उसकी correct position पर swap कर देते हैं।
Key Points :
- यह comparison-based और in-place sorting algorithm है।
- हर pass में minimum (या maximum) element को खोजकर उसकी correct position पर swap किया जाता है।
- Time Complexity : Best = Average = Worst = O(n²)
- Space Complexity : O(1)
- Logic बहुत simple है, Find minimum → Swap
- Beginners के लिए ideal sorting method है।
- Small datasets और hardware-level implementation में useful है।
Working Principle (कैसे काम करता है?)
1. Finding the minimum element (Minimum element खोजना) :
- हर pass में algorithm unsorted part में जाकर smallest element को खोजता है।
2. Placing at the Correct Position (Correct position पर रखना) :
- मिले हुए सबसे छोटे element को उसकी सही position (array के starting side) पर ले जाकर swap कर दिया जाता है।
3. Sorting + Unsorted (Sorted + Unsorted बनाना) :
- जिस position पर element सही जगह पर आ जाता है, वह हिस्सा अब sorted बन जाता है, और बाकी का हिस्सा अभी भी unsorted रहता है।
4. Repeat process :
- अगली pass में algorithm दोबारा unsorted हिस्से से minimum element खोजकर उसे उसकी correct position पर रख देता है।
5. Entire array sorted :
- जब हर position पर सही element आ जाता है, तब पूरा array पूरी तरह से sorted हो जाता है।
Example (उदाहरण)
array :[29, 10, 14, 37, 13]
Step 1
- Minimum = 10
- Swap with 29
→[10, 29, 14, 37, 13]
Step 2
- Remaining :
[29, 14, 37, 13] - Minimum = 13
- Swap with 29
→[10, 13, 14, 37, 29]
Step 3
- Remaining :
[14, 37, 29] - Minimum = 14
- Already in correct place
→[10, 13, 14, 37, 29]
Step 4
- Remaining :
[37, 29] - Minimum = 29
- Swap with 37
→[10, 13, 14, 29, 37]
Final Sorted Array : [10, 13, 14, 29, 37]
Pseudo Code
for i → 0 to n-1
minIndex = i
for j → i+1 to n-1
if A[j] < A[minIndex]
minIndex = j
swap(A[i], A[minIndex])
Applications of Selection Sort (अनुप्रयोग)
1. Small Data Sets Sorting
Selection Sort छोटे size वाले arrays या lists के लिए perfect है, क्योंकि इसका implementation simple और predictable होता है।
- Small student lists
- Temporary data sorting
2. When Memory Space is Limited (Low-Memory Conditions)
Selection Sort in-place algorithm है (extra memory नहीं लेता), इसलिए low-memory devices में इसका use होता है।
- Embedded systems
- Old mobile devices
3. Easy-to-Understand Teaching Purposes
Schools और colleges में sorting का basic logic समझाने के लिए सबसे ज्यादा Selection Sort use किया जाता है।
- Algorithm teaching
- Comparing sorting strategies
- Step-by-step demonstration
4. Situations Requiring Minimum Number of Swaps
Selection Sort में comparisons ज्यादा होते हैं, लेकिन swaps बहुत कम। जहाँ swapping cost बहुत high हो वहाँ यह useful है।
- Flash memory devices
- SSDs (जहाँ write operations costly होते हैं)
5. Finding the Minimum or Maximum Value
पूरा array sort न भी करना हो, Selection Sort का logic single minimum या maximum element निकालने में बहुत handy है।
- Small data filters
- Minimum marks, minimum price listing
- Quick scan operations
6. Simple Hardware Implementations
इसका logic clear और predictable होता है, इसलिए hardware level sorting circuits में इसका use किया जाता है।
- Digital circuit sorters
- FPGA sorting units
7. Partial Sorting Tasks
अगर आपको list को पूरी तरह sort नहीं करना, बस कुछ smallest elements चाहिए—Selection Sort एक अच्छा option है।
- Top 5 minimum values
- Lowest price filters
- Minimum ranking lists
8. Manual Comparison Scenarios
जहाँ manual selection/ comparison करना आसान हो, वहाँ इसका logic naturally fit होता है।
- Sorting playing cards manually
- Choosing lowest discount
- Selecting smallest item in shops
Advantages (लाभ)
1. Simple and Easy to Understand
- इसका concept बहुत आसान है — minimum element ढूंढो और उसे सही position पर रख दो।
2. Less Number of Swaps
- हर pass में सिर्फ 1 swap होता है, जिससे swap cost कम रहती है।
3. In-Place Algorithm
- Selection Sort extra memory use नहीं करता → Space Complexity O(1) रहती है।
4. Useful for Small Data Sets
- छोटी lists या educational purpose में यह काफी अच्छा काम करता है।
5. Predictable Performance
- Best, Average और Worst—तीनों cases में same time complexity (O(n²)) रहती है, इसलिए इसका performance predictable होता है।
Disadvantages (हानियाँ)
1. Slow for Large Data
- Time Complexity हमेशा O(n²) होने की वजह से यह बड़े data sets पर बहुत slow होता है।
2. Not a Stable Sort
- Equal elements का original order बदल सकता है, इसलिए यह stable sorting algorithm नहीं है।
3. Too Many Comparisons
- हर element को compare करना पड़ता है, जिससे total comparisons बहुत बढ़ जाते हैं।
4. Not Adaptive
- Array पहले से sorted हो तब भी time complexity कम नहीं होती — same time लगता है।
5. Less Use in Real-World Applications
- Faster algorithms जैसे Quick Sort, Merge Sort, Heap Sort available होने की वजह से Selection Sort practical applications में rarely use किया जाता है।
Insertion Sort
Insertion Sort एक simple, comparison-based और in-place sorting algorithm है। यह algorithm array या list के elements को ascending या descending order में arrange करता है।
Key Points
- Simple & Easy to Understand : Algorithm beginners के लिए perfect और आसानी से समझ में आने वाला।
- Comparison-Based : Elements को compare करके उनकी correct position तय होती है।
- In-Place Sorting : Extra memory की जरूरत नहीं होती।
- Space Complexity = O(1)
- Stable Algorithm : Equal elements का original order maintain रहता है।
- Best for Small Data Sets : छोटे arrays या lists के लिए efficient है।
Working Principle (कैसे काम करता है?)
Step-by-Step Process
1. Assume the first element is sorted
- Array का पहला element automatically sorted रहता है।
2. Compare and Shift Next Element
- Current element को left-side sorted elements के साथ compare करो।
- अगर left-side element बड़ा है → उसे एक position right shift करो।
3. Insert the Current Element
- Correct position मिलने पर current element को insert करो।
4. Repeat
- यह process array के हर element के लिए repeat करो।
- अंत में पूरा array sorted हो जाएगा।
Example (उदाहरण)
array = [8, 3, 5, 4]
Step 1
- First element
8already sorted →[8 | 3, 5, 4]
Step 2
- Take
3, compare with8→ shift8right → insert3→[3, 8 | 5, 4]
Step 3
- Take
5, compare with8→ shift8right → compare with3→ correct place is after3→[3, 5, 8 | 4]
Step 4
- Take
4, compare with8→ shift8right → compare with5→ shift5right → insert4→[3, 4, 5, 8]
Result : Sorted array → [3, 4, 5, 8]
Pseudo Code
InsertionSort(array A)
for i = 1 to length(A)-1
key = A[i]
j = i-1
while j >= 0 and A[j] > key
A[j+1] = A[j]
j = j-1
end while
A[j+1] = key
end for
end
Advantages (लाभ)
- Simple & Easy to Understand – Beginners-friendly, आसानी से समझा जा सकता है।
- Adaptive – अगर array पहले से partially sorted है, तो fast चलता है।
- In-Place Sorting – Extra memory की जरूरत नहीं।
- Stable – Equal elements का original order maintain रहता है।
- Efficient for Small Data Sets – छोटे datasets, embedded systems और handheld devices के लिए suitable है।
Disadvantages (हानियाँ)
- Slow for Large Data : Time Complexity O(n²) बड़े datasets के लिए inefficient है।
- Many Comparisons & Shifts : Randomly ordered arrays में हर element को compare और shift करना पड़ता है।
- Not Suitable for Performance-Critical Applications : Big Data या server-side sorting में ideal नहीं है ।
- Not Adaptive for Fully Unsorted Data : पूरी तरह unsorted array में slow performance देता है।
- Less Efficient than Merge or Quick Sort : Large datasets में Merge या Quick Sort की तुलना में slower होता है।
