সিলেকশন সর্ট একটি সর্টিং অ্যালগরিদম যা অ্যারেটি শুরু থেকে ডাকচে চলতে থাকে এবং প্রতিটি এলিমেন্টকে বাঁকি লিস্টের সবচেয়ে ছোট এলিমেন্ট দিয়ে রিপ্লেস করে। বামপাশের অংশ সর্টেড থাকে, ডানপাশের অনসর্টেড।
সিলেকশন সর্ট অ্যালগরিদম
int arr[5] = {5,4,2,1,3};for i=0 to size-2→for j=i+1 to size-1ছোটটি খুঁজুন, তারপরarr[i]দিয়ে স্ব্যাপ করুন।
রিকারসিভ সিলেকশন সর্ট
ন্যূনতম এলিমেন্টের ইনডেক্স খুঁজুন।
যদি ন্যূনতম ইনডেক্স == অ্যারে সাইজ হয়, ফেরত যান।
অন্যথায় বর্তমান এলিমেন্ট ও ন্যূনতম এলিমেন্ট স্ব্যাপ করুন।
বাঁকি অনসর্টেড অংশে রিকারসিভ কল দিন।
উদাহরণ
ইনপুট − Arr[] = {5,7,2,3,1,4}, length=6
আউটপুট − সর্টেড অ্যারে: 1 2 3 4 5 7
ইনপুট − Arr[] = {1,2,3,3,2}
আউটপুট − সর্টেড অ্যারে: 1 2 2 3 3
প্রোগ্রামে ব্যবহৃত পদ্ধতি
রিকারসিভ সিলেকশন সর্টের বেস কেস: minIndex == size-1। অন্যথায় ন্যূনতম খুঁজে স্ব্যাপ করে ডানপাশ রিকারসিভ সর্ট।
ইনপুট অ্যারে
Arr[]ও দৈর্ঘ্যlength।findMin(int arr[], int i, int j)ফাংশনi+1থেকেjপর্যন্ত ন্যূনতম ইনডেক্স ফেরত দেয়।যদি
i == jহয়,iফেরত দিন।অন্যথায়
minpos = findMin(arr, i+1, j); যদিarr[i] < arr[minpos]হয়,minpos = i।recurselectSort(int arr1[], int len1, int pos1)ফাংশন রিকারসিভভাবে সর্ট করে।যদি
pos1 == len1হয়, ফেরত যান।minpos1 = findMin(arr1, pos1, len1-1)।যদি
minpos1 != pos1হয়, স্ব্যাপ করুন।recurselectSort(arr1, len1, pos1+1)কল করুন।
উদাহরণ কোড
#include <iostream>
using namespace std;
int findMin(int arr[], int i, int j){
int minpos;
if (i == j){
return i;
}
minpos = findMin(arr, i + 1, j);
if(arr[i] < arr[minpos]){
minpos = i;
}
return minpos;
}
void recurselectSort(int arr1[], int len1, int pos1){
int temp, minpos1;
if (pos1 == len1){
return;
}
minpos1 = findMin(arr1, pos1, len1-1);
if (minpos1 != pos1){
temp = arr1[pos1];
arr1[pos1] = arr1[minpos1];
arr1[minpos1] = temp;
}
recurselectSort(arr1, len1, pos1 + 1);
}
int main(){
int Arr[] = {1,5,3,0,9,3,5};
int length = sizeof(Arr)/sizeof(Arr[0]);
recurselectSort(Arr, length, 0);
cout << "Sorted Array using recursive Selection sort: " << endl;
for (int i = 0; i < length; i++){
cout << Arr[i] << " ";
}
return 0;
}
আউটপুট
উপরের কোড রান করলে নিচের আউটপুট পাওয়া যাবে:
Sorted Array using recursive Selection sort: 0 1 3 3 5 5 9
