একটি ইন্টিজার অ্যারের উপাদানগুলাকে এমনভাবে সাজানো হবে যেন প্রথম উপাদানটি অ্যারের সর্বোচ্চ, দ্বিতীয় উপাদানটি ন্যূনতম, তৃতীয় উপাদানটি দ্বিতীয় সর্বোচ্চ, চতুর্থ উপাদানটি দ্বিতীয় ন্যূনতম - এভাবে চলতে থাকবে।
উদাহরণ দিয়ে বুঝি:
Input: 4 1 8 2 9 3 7 Output: 9 1 8 2 7 3 4 Explanation: সর্টেড আকারে: 1 2 3 4 7 8 9। এখন আমাদের চাহিদা অনুযায়ী অল্টারনেট সাজানো: সবচেয়ে বড় ৯, তারপর সবচেয়ে ছোট ১, তারপর ৮, ২, ৭, ৩, ৪।
এখন কনসেপ্ট বুঝলেই সমাধান বানাতে পারি। একটি সম্ভাব্য সমাধান: অ্যারেটি সর্ট করুন এবং সর্টেড অ্যারের শেষ ও প্রথম উপাদান প্রিন্ট করুন। এর ভিত্তিতে অ্যালগরিদম বানানো যাক।
আলগরিদম
Step 1: অ্যারেটি সর্ট করুন। Step 2: দুটি পয়েন্টার বানান - একটি শুরু থেকে ট্রাভার্সের জন্য, অন্যটি শেষ থেকে। Step 3: দুটি পয়েন্টারের মান অল্টারনেটভাবে প্রিন্ট করুন এবং ইটেরেটর বাড়ান।
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
using namespace std;
void alternateSort(int arr[], int n) ;
void swap(int *xp, int *yp) ;
void selectionSort(int arr[], int n) ;
int main(){
int arr[] = { 4,1,8,2,9,3,7};
int n = sizeof(arr)/sizeof(arr[0]);
alternateSort(arr, n);
return 0;
}
void alternateSort(int arr[], int n){
selectionSort(arr, n);
int i = 0, j = n-1;
while (i < j) {
cout << arr[j--] << " ";
cout << arr[i++] << " ";
}
if (n % 2 != 0)
cout << arr[i];
}
void swap(int *xp, int *yp){
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n){
int i, j, min_idx;
for (i = 0; i < n-1; i++){
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}
আউটপুট
9 1 8 2 7 3 4
