মান লেযিয়ে একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে, আমাদের এটিকে আরোহী ক্রমে সোর্ট করতে হবে। অ্যারে [5,2,3,1] হলে ফলাফল [1,2,3,5]।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
partition নামে একটি মেথড তৈরি করুন, যা অ্যারে, low এবং high নেবে
pivot := low সেট করুন
i = low থেকে high-1 পর্যন্ত লুপ চালান
যদি nums[i] < nums[high] হয়, swap(nums[i], nums[pivot]) এবং pivot++ করুন
swap(nums[pivot], nums[high])
sortArr() নামে একটি মেথড তৈরি করুন, যা অ্যারে, low এবং high নেবে
যদি low >= high হয়, রিটার্ন করুন
partitionIndex := partition(nums, low, high)
sortArr(nums, low, partitionIndex-1)
sortArr(nums, partitionIndex+1, high)
মেইন মেথড থেকে sortArr() কল করুন low=0, high=arr.size()-1 দিয়ে
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<string> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: int partition(vector <int>& nums, int low, int high){ int pivot = low; for(int i = low; i < high; i++){ if(nums[i] < nums[high]){ swap(nums[i], nums[pivot]); pivot++; } } swap(nums[pivot], nums[high]); return pivot; } void sortArr(vector <int>& nums, int low, int high){ if(low >= high) return; int partitionIndex = partition(nums, low, high); sortArr(nums, low, partitionIndex - 1); sortArr(nums, partitionIndex + 1, high); } vector<int> sortArray(vector<int>& nums) { sortArr(nums, 0, nums.size() - 1); return nums; } }; main(){ vector<int> v1 = {5,2,3,1}; Solution ob; print_vector(ob.sortArray(v1)); }ইনপুট
[5,2,3,1]
আউটপুট
[1,2,3,5]
