একটি পূর্ণসংখ্যার অ্যারে (ধনাত্মক ও ঋণাত্মক) দেওয়া থাকলে, কনস্ট্যান্ট এক্সট্রা স্পেস ব্যবহার করে সেটিকে সর্ট করতে হবে যাতে সব ঋণাত্মক সংখ্যা আগে, তারপর ধনাত্মক।
উদাহরণ
ইনপুট − arr[] = {4, 2, -1, -1, 6, -3, 0}
আউটপুট − -3 -1 -1 0 6 2 4
ইনপুট − arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}
আউটপুট − -9 -10 2 3 10 5 8 4
প্রোগ্রামে ব্যবহৃত পদ্ধতি
দুটি পয়েন্টার
i=0(শুরু),j=size-1(শেষ)।while(true)লুপে:iবাড়াতে থাকুন যতক্ষণarr[i] < 0।jকমানো থাকুন যতক্ষণarr[j] > 0।যদি
i < jহয়,swap(arr[i], arr[j])।অন্যথায় ব্রেক।
উদাহরণ কোড
#include <iostream>
using namespace std;
void Rearrangement(int arr[], int size){
int i = 0, j = size - 1;
while(true){
while(arr[i] < 0 && i < size) i++;
while(arr[j] > 0 && j >= 0) j--;
if (i < j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else break;
}
}
int main(){
int arr[] = {4, 2, -1, -1, 6, -3, 0};
int size = sizeof(arr)/sizeof(arr[0]);
Rearrangement(arr, size);
cout << "Rearrangement of positive and negative numbers with constant extra space is: ";
for(int i = 0; i < size; i++) cout << arr[i] << " ";
return 0;
}
আউটপুট
উপরের কোড রান করলে নিচের আউটপুট পাওয়া যাবে:
Rearrangement of positive and negative numbers with constant extra space is: -3 -1 -1 0 6 2 4
