समस्या
C भाषा में विभिन्न छँटाई तकनीकें क्या हैं? किसी एक छँटाई तकनीक को उदाहरण सहित समझाइए।
समाधान
C भाषा पांच छँटाई तकनीक प्रदान करती है, जो इस प्रकार हैं -
- बबल सॉर्ट (या) एक्सचेंज सॉर्ट।
- चयन क्रम।
- सम्मिलन क्रम (या) रैखिक छँटाई।
- त्वरित छँटाई (या) विभाजन विनिमय छँटाई।
- मर्ज सॉर्ट (या) बाहरी सॉर्ट।
बबल सॉर्ट
यह सबसे सरल छँटाई तकनीक है जिसे एक्सचेंज सॉर्ट भी कहा जाता है।
प्रक्रिया
-
सूची में शेष तत्वों के साथ पहले तत्व की तुलना करें और यदि वे क्रम में नहीं हैं तो उन्हें एक्सचेंज (स्वैप) करें।
-
सूची में अन्य तत्वों के लिए इसे तब तक दोहराएं जब तक कि सभी तत्व क्रमबद्ध न हो जाएं।
30 50 40 10 20
नीचे दिए गए तत्वों पर विचार करें -
पहला पास
शेष तत्वों के साथ पहले तत्व की तुलना करें।
a[0]> a[1] $\square$ $\square$30>50 (F) $\square$ $\square$कोई एक्सचेंज नहीं
a[0]> a[2] $\square$ $\square$ 30>40 (F) $\square$ $\square$ कोई एक्सचेंज नहीं
a[0]> a[3] $\square$ $\square$ 30>10 (T) $\square$ $\square$ एक्सचेंज
a[0]> a[4] $\square$ $\square$ 10>20 (F) $\square$ $\square$ कोई एक्सचेंज नहीं
10 50 40 30 20
दूसरा पास
शेष तत्वों के साथ दूसरे तत्व की तुलना करें।
a[1]> a[2] $\square$ $\square$ 50>40 (T) $\square$ $\square$ एक्सचेंज
a[1]> a[3] $\square$ $\square$ 40>30 (T) $\square$ $\square$ एक्सचेंज
a[1]> a[4] $\square$ $\square$ 30>20 (T) $\square$ $\square$ एक्सचेंज
10 20 50 40 30
तीसरा पास
तीसरे तत्व की तुलना शेष तत्वों से करें।
a[2]> a[3] $\square$ $\square$ 50>40 (T) $\square$ $\square$ एक्सचेंज
a[2]> a[4] $\square$ $\square$ 40>30 (T) $\square$ $\square$ एक्सचेंज
10 20 30 50 40
चौथा पास
चौथे तत्व की तुलना शेष तत्वों से करें।
a[3]> a[4] $\square$ $\square$ 50>40 (T) $\square$ $\square$ एक्सचेंज
10 20 30 40 50
प्रक्रिया
बबल सॉर्ट के लिए नीचे दी गई प्रक्रिया देखें -
for (i=0; i<n-1; i++){
for (j=i+1; j<n; j++){
if (a[i] > a[j]){
t=a[i];
a[i] = a[j];
a[j] = t;
}
}
} उदाहरण
बबल छँटाई तकनीक के लिए C प्रोग्राम निम्नलिखित है -
#include<stdio.h>
int main(){
int a[50], i,j,n,t;
printf("enter the No: of elements in the list:\n");
scanf("%d", &n);
printf("enter the elements:\n");
for(i=0; i<n; i++){
scanf ("%d", &a[i]);
}
printf("Before bubble sorting the elements are:\n");
for(i=0; i<n; i++)
printf("%d \t\n", a[i]);
for (i=0; i<n-1; i++){
for (j=i+1; j<n; j++){
if (a[i] > a[j]){
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
printf ("after bubble sorting the elements are:\n");
for (i=0; i<n; i++)
printf("%d\t", a[i]);
return 0;
} आउटपुट
जब उपरोक्त प्रोग्राम को निष्पादित किया जाता है, तो यह निम्नलिखित परिणाम उत्पन्न करता है -
enter the No: of elements in the list: 5 enter the elements: 12 11 45 26 67 Before bubble sorting the elements are: 12 11 45 26 67 after bubble sorting the elements are: 11 12 26 45 67