সিলেকশন সর্ট কী?
সিলেকশন সর্ট একটি সাধারণ সর্টিং অ্যালগরিদম যা অ্যারেতে থেকে সর্বনিম্ন মান খুঁজে বের করে সেটিকে প্রথম পজিশনে রাখে। এরপর বাকি অংশে পুনরাবৃত্তি করে পুরো অ্যারেটি সর্ট করা হয়।
প্রক্রিয়া
- লিস্ট থেকে সবচেয়ে ছোট এলিমেন্ট খুঁজে প্রথম পজিশনে রাখুন।
- বাকি এলিমেন্টগুলোর মধ্যেও একই কাজ করে পুরো লিস্ট সর্ট হওয়া পর্যন্ত চলুন।
উদাহরণ দিয়ে ব্যাখ্যা (পাস দিয়ে পাস)
প্রাথমিক অ্যারে: 30, 50, 40, 10, 20
প্রথম পাস
সর্বনিম্ন: 10 (ইন্ডেক্স ৩)। এক্সচেঞ্জ a[0] এবং a[3]।
ফলাফল: 10, 50, 40, 30, 20
দ্বিতীয় পাস
সর্বনিম্ন (ইন্ডেক্স ১ থেকে): 20। এক্সচেঞ্জ a[1] এবং a[4]।
ফলাফল: 10, 20, 40, 30, 50
তৃতীয় পাস
সর্বনিম্ন (ইন্ডেক্স ২ থেকে): 30। এক্সচেঞ্জ a[2] এবং a[3]।
ফলাফল: 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;
}
t = a[i];
a[i] = a[sm];
a[sm] = t;
}সি প্রোগ্রাম
#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]);
// Selection Sort
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("After selection sorting: ");
for (i = 0; i < n; i++)
printf("%d\t", a[i]);
return 0;
}আউটপুট
Enter number of elements: 4 Enter elements: 45 12 37 68 After selection sorting: 12 37 45 68
টাইম কমপ্লেক্সিটি
সিলেকশন সর্টের টাইম কমপ্লেক্সিটি সব ক্ষেত্রে O(n²)। ছোট ডেটাসেটের জন্য উপযুক্ত, বড় ডেটার জন্য দক্ষ নয়।
