সিলেকশন সর্ট হল একটি সাজানোর অ্যালগরিদম যা ডাটা সাজানোর জন্য ব্যবহার করা হয় শুরু থেকে একটি অ্যারের পুনরাবৃত্তি করে এবং প্রতিটি উপাদানকে তালিকার ক্ষুদ্রতম উপাদান দিয়ে প্রতিস্থাপন করে। আমরা এগিয়ে যাওয়ার সাথে সাথে বাম অ্যারে সাজানো হয়, এবং ডান অ্যারেটি সাজানো হয় না। প্রতিটি পদক্ষেপ অদলবদল করে সূচকের বর্তমান অবস্থানে পরবর্তী ক্ষুদ্রতম স্থানকে রাখে।
নির্বাচন সাজানোর অ্যালগরিদম
-
int arr[5]={ 5,4,2,1,3 };
-
int i, j;
-
সূচী i=0 থেকে i<অ্যারে সাইজ -1
এ যাত্রা করুন-
সূচী j=i+1 থেকে অ্যারের আকার - 1
-এ যান -
সবচেয়ে ছোট খুঁজুন এবং এর index.pos
সংরক্ষণ করুন
-
-
arr[i]
এর সাথে পাওয়া সূচী পোজে উপাদান অদলবদল করুন -
সমাপ্তি
পুনরাবৃত্ত নির্বাচন বাছাই
-
ন্যূনতম উপাদানের সূচক খুঁজুন
-
যদি পাওয়া ক্ষুদ্রতম উপাদান সূচকটি অ্যারের আকারের সমান হয়, তাহলে ফিরে আসুন।
-
অন্যথায় ক্ষুদ্রতম উপাদানের সাথে বর্তমান উপাদান অদলবদল করুন
-
সাজানো উপাদানগুলি বাদ দিয়ে বাকি অ্যারের জন্য উপরের পদক্ষেপগুলি পুনরাবৃত্তিমূলকভাবে সম্পাদন করুন
উদাহরণ
ইনপুট − Arr[] ={ 5,7,2,3,1,4 }; দৈর্ঘ্য=6
আউটপুট − সাজানো অ্যারে:1 2 3 4 5 7
ব্যাখ্যা −
First Pass :- 5 7 2 3 1 4 → swap → 1 2 7 3 5 4 1 2 7 3 5 4 → no swap 1 2 7 3 5 4 → swap → 1 2 3 7 5 4 1 2 3 7 5 4 → swap → 1 2 3 4 5 7 1 2 3 4 5 7 → no swap
ইনপুট − Arr[] ={ 1, 2, 3, 3, 2 };
আউটপুট − সাজানো অ্যারে:1 2 2 3 3
ব্যাখ্যা −
1 2 3 3 2 → no swap 1 2 3 2 3 → no swap 1 2 3 2 3 → swap → 1 2 2 3 3 1 2 2 3 3 → no swap
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
নির্বাচন সাজানোর পুনরাবৃত্তিমূলক পদ্ধতিতে, বেস কেসটি সর্বনিম্ন সূচক =অ্যারের আকার -1। অন্যথায় বর্তমান সূচকের সাথে অ্যারে অদলবদল থেকে ন্যূনতম খুঁজুন এবং পুনরাবৃত্তভাবে ডান সাজানো অ্যারে সাজান।
-
ইনপুট অ্যারে Arr[] এবং দৈর্ঘ্য এটিতে উপাদানের সংখ্যা হিসাবে নিন।
-
ফাংশন FindMin(int arr[], int i, int j) অ্যারে এবং এর সূচী নেয় এবং arr[j] থেকে arr[i+1]-এর মধ্যে ন্যূনতম উপাদানের সূচী প্রদান করে।
-
একটি পরিবর্তনশীল মিনপোস নিন।
-
যদি i এবং j উভয়ই একই হয়, তাহলে ন্যূনতম উপাদানের সূচক হিসাবে i ফেরত দিন কারণ উভয়ই একই।
-
অন্যথায় মিনপোস =findMin(arr, i + 1, j) ব্যবহার করে i+1 থেকে j অবস্থানের জন্য পুনরাবৃত্তি করুন।
-
if(arr[i]
-
ফাংশন recurselectSort(int arr1[], int len1, int pos1) ইনপুট অ্যারে নেয় এবং সিলেকশন সাজানোর রিকারশন ব্যবহার করে ক্রমবর্ধমান ক্রমে সাজায়৷
-
যদি pos1 ==len1 তাহলে ন্যূনতম কোন পাওয়া না যায়, তাহলে ফেরত দিন।
-
অন্যথায় সেট করুন minpos1 =findMin(arr1, pos1, len1-1)
-
যদি বর্তমান pos1 সূচক এবং ন্যূনতম উপাদান সূচক minpos1 একই না হয়, তাহলে টেম্প ব্যবহার করে এই সূচকগুলিতে উপাদানগুলি অদলবদল করুন৷
-
recurselectSort(arr1, len1, pos1 + 1) ব্যবহার করে বাকি অ্যারের জন্য পুনরাবৃত্তি করুন।
-
সমস্ত কলের শেষে, যখন লেন 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;
int 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
