সিলেকশন সর্ট টেকনিকে (Selection Sort), লিস্ট দুটি অংশে ভাগ হয়। এক অংশে সব এলিমেন্ট সর্টেড থাকে এবং অন্য অংশে আইটেমগুলো আনসর্টেড। প্রথমে আমরা অ্যারে থেকে সর্বোচ্চ বা ন্যূনতম ডেটা নিই। ডেটা পাওয়ার পর (মান লেন ন্যূনতম) সেটিকে লিস্টের শুরুতে প্রথম পজিশনের ডেটার সাথে রিপ্লেস করে রাখি। এতে অ্যারে ছোট হয়ে যায়। এভাবে এই সোর্টিং টেকনিক সম্পন্ন হয়।
সিলেকশন সর্ট টেকনিকের জটিলতা
সময় জটিলতা: O(n²)
স্পেস জটিলতা: O(1)
ইনপুট − আনসর্টেড লিস্ট: 5 9 7 23 78 20 আউটপুট − সর্টিংয়ের পর অ্যারে: 5 7 9 20 23 78
অ্যালগরিদম
selectionSort(array, size)
ইনপুট: একটি ডেটা অ্যারে, এবং অ্যারেতে মোট সংখ্যা
আউটপুট: সর্টেড অ্যারে
শুরু
i := 0 থেকে size-2 পর্যন্ত // i-থ লোকেশন থেকে size পর্যন্ত ন্যূনতম বের করুন
iMin := i
j := i+1 থেকে size-1 পর্যন্ত
যদি array[j] < array[iMin] হয় তবে
iMin := j
শেষ
array[i] এবং array[iMin] সোয়্যাপ করুন
শেষ
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
void swapping(int &a, int &b) {
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
void selectionSort(int *array, int size) {
int i, j, imin;
for(i = 0; i < size-1; i++) {
imin = i;
for(j = i+1; j < size; j++)
if(array[j] < array[imin])
imin = j;
swap(array[i], array[imin]);
}
}
int main() {
int n;
cout << "এলিমেন্টের সংখ্যা দিন: ";
cin >> n;
int arr[n];
cout << "এলিমেন্টগুলো দিন:" << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "সর্টিংয়ের আগে অ্যারে: ";
display(arr, n);
selectionSort(arr, n);
cout << "সর্টিংয়ের পর অ্যারে: ";
display(arr, n);
}
আউটপুট
এলিমেন্টের সংখ্যা দিন: 6 এলিমেন্টগুলো দিন: 5 9 7 23 78 20 সর্টিংয়ের আগে অ্যারে: 5 9 7 23 78 20 সর্টিংয়ের পর অ্যারে: 5 7 9 20 23 78
