सिलेक्शन सॉर्ट क्या है?
सिलेक्शन सॉर्ट एक सरल सॉर्टिंग एल्गोरिदम है जो ऐरे में सबसे छोटा एलिमेंट ढूंढकर उसे पहली पोजीशन पर रखता है, फिर शेष ऐरे के लिए प्रक्रिया दोहराता है।
प्रक्रिया
- पूरी सूची में से सबसे छोटा एलिमेंट चुनें और उसे पहली पोजीशन पर रखें।
- शेष एलिमेंट्स के लिए यही प्रक्रिया दोहराएं जब तक सभी सॉर्ट न हो जाएं।
उदाहरण: 30, 50, 40, 10, 20
पहला पास
सबसे छोटा = 10 (इंडेक्स 3)। इसे इंडेक्स 0 (30) के साथ स्वैप करें।
10 50 40 30 20
दूसरा पास
शेष (50,40,30,20) में सबसे छोटा = 20। इंडेक्स 1 (50) के साथ स्वैप करें।
10 20 40 30 50
तीसरा पास
शेष (40,30,50) में सबसे छोटा = 30। इंडेक्स 2 (40) के साथ स्वैप करें।
10 20 30 40 50
चौथा पास
शेष (40,50) में सबसे छोटा = 40। पहले से सही स्थान पर है।
10 20 30 40 50
एल्गोरिदम
for (i = 0; i < n-1; i++) {
sm = i;
for (j = i+1; j < n; j++) {
if (a[j] < a[sm])
sm = j;
}
// स्वैप a[i] और a[sm]
t = a[i];
a[i] = a[sm];
a[sm] = t;
}C प्रोग्राम
#include <stdio.h>
int main() {
int a[50], i, j, n, t, sm;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements: ");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 0; i < n-1; i++) {
sm = i;
for (j = i+1; j < n; j++) {
if (a[j] < a[sm])
sm = j;
}
t = a[i];
a[i] = a[sm];
a[sm] = t;
}
printf("Sorted array: ");
for (i = 0; i < n; i++)
printf("%d\t", a[i]);
return 0;
}आउटपुट
Enter number of elements: 4 Enter elements: 45 12 37 68 Sorted array: 12 37 45 68
विशेषताएं
- समय जटिलता: O(n²) - सभी केस में।
- स्पेस जटिलता: O(1) - इन-प्लेस सॉर्टिंग।
- स्वैप की संख्या न्यूनतम (अधिकतम n-1)।
