Modified Sorting Using Compare Function

struct node
{
   int x, y, z;
} A[5];

ধরেন, আপনি A অ্যারেটা z ভ্যারিয়েবল অনুযায়ী বড় থেকে ছোট আকারে সাজাবেন। এক্ষেত্রে sort() কীভাবে ইউজ করা যায় দেখা যাক।

প্রথমেই sort() ফাংশনের প্যারামিটারগুলো দেখি।

sort(starting element pointer, ending ending pointer + 1, compare function name);

অর্থাৎ, যদি ফাংশন নেম comp হয় আর আপনি পুরা A অ্যারেটা সর্ট করতে চান comp ফাংশন অনুযায়ী, তাহলে লাইনটা হবে নিম্নরূপঃ

sort(A + 0, A + 4 + 1, comp);

বা

sort(A, A + 5, comp);

এখানে A + 0 অর্থাৎ A[0] হল অ্যারের প্রথম এলিমেন্ট।
A + 4 অর্থাৎ A[4] হল অ্যারের শেষ এলিমেন্ট।

তাহলে আপনি যদি অ্যারেটার ১ নং ইন্ডেক্স থেকে ৩নং ইন্ডেক্স সর্ট করতে চাইতেন শুধু, তাহলে লাইনটা কেমন হত?

sort(A + 1, A + 3 + 1, comp);

অর্থাৎ

sort(A + 1, A + 4, comp);

এবার আসি comp ফাংশনে। দেখা যাক এটি কীভাবে কাজ করে।

comp ফাংশনটা জাস্ট একটা ডিজাইন যেটার কাজ হল বলে দেওয়া sort() ফাংশনটা কীভাবে কাজ করবে।

comp-এ সব সময় দুটা প্যারামিটার রাখতে হয়, এবং এটা রিটার্ন করবে ট্রু অর ফলস, অর্থাৎ bool টাইপ।

comp-এর কাজ হল বলে দেওয়া, অ্যারের যে কোন দুটা এলিমেন্টের মধ্যে কোনটা আগে থাকবে এবং কোনটা পরে থাকবে, অর্থাৎ এক্ষেত্রে comp বলে দিবে যে A অ্যারের ১ আর ৩ নং এলিমেন্টের মধ্যে ১-এর z বড় হয়, তাহলে তারা ঠিকই আছে, তাদের সর্টের প্রয়োজন নাই। যদি এলিমেন্টটার z ছোট হয়, তাহলে সর্ট করতে হবে।

comp ফাংশনটা অনেকটা দাঁড়াচ্ছে তাহলেঃ

bool comp (node p, node q)
{ };

এখানে, p, q প্যারামিটার দুটা হল A অ্যারের দুটা এলিমেন্ট, এবং অবশ্যই p অ্যারেতে আগে অবস্থিত আর q পরে অবস্থিত।

p, q এর টাইপ node কারণ অ্যারেটার টাইপও নোড।

যেহেতু p হচ্ছে অ্যারেতে যে এলিমেন্ট আগে আছে আর q হচ্ছে যেটা পরে আছে, তার মানে, p.z > q.z হলে p আর q সর্টেডই আছে? আর যদি না হয়, তাহলে তাদের সর্ট করতে হবে।

comp ফাংশনটা বলে দেয় যে সর্টেড আছে কিনা। অর্থাৎ, সর্টেড থাকলে (মানে আপনি যেভাবে সর্টেড রাখতে চান, এক্ষেত্রে আমরা চাচ্ছি z অনুযায়ী descending) ফাংশনটা true return করবে, নতুবা ফলস।

আর একটা ইম্পর্ট্যান্ট কথা। আপনার ফাংশন যেন অবশ্যই বলে দেয় p.z = q.z হলে কী হবে!

p.z = q.z হলে আপনি x বা y অনু্যায়ীও চেক করতে পারেন। ধরেন, p.z = q.z হলে আমি চাই x অনু্যায়ী ascendingly sort হবে। তখন আমার ফাংশনে তা-ই লিখে দিতে হবে। কিন্তু p.x = q.x হলে? সেক্ষেত্রে আবার y অনুযায়ীও দেখতে পারেন। কিন্তু তাও সমান হলে?

সেক্ষেত্রে false রিটার্ন করা মাস্ট। এটা একটা ইম্পর্ট্যান্ট পার্ট। এটা না করলে আপনি কিন্তু এটার্নাল লুপে পরে যেতে পারেন।

এবার ফাংশনটা লিখে দেখা যাক।

bool cmp (node p, node q)
{
      if (p.z > q.z)
         return true;
      else if (p.z == q.z)
     {
         if (p.x < q.x)
         return true;
      else return false; //অর্থাৎ, p.x == q.x হলে false রিটার্ন্ট হচ্ছে
    }
    else return false;
};

এ ফাংশনটা বুঝাচ্ছে যে, আপনি এমনভাবে সর্ট করতে চান যেন সর্টেড অ্যারের যে এলিমেন্ট আগে থাকবে, তার z ভ্যারিয়েবলের মান পরের এলিমেন্টের z থেকে বড় হবে। যদি তাদের z সমান হয়, তবে যেটা আগে আছে তার x পরেরটার থেকে ছোট হবে।

এবার নিজের কোড করে প্র্যাক্টিস করে জিনিসটা হাতে আনতে হবে।

PS: অপারেটর ওভারলোড করেও করা যায়। কিন্তু ফাংশন লিখে করা আমার কাছে ইজিয়ার লাগে, অপারেটর ওভারলোডিং-এর দরকার কখনও হয়নি ফাংশন ইউজের জন্য~

 

Hope this helps~

by - Tahsin Masrur