stable_sort() কি? সাধারণ sort() আর stable_sort() এর মধ্যে পার্থক্য কি? কখন এটা ব্যাবহার করবো?

asked 13 Feb '16, 20:56

Undefined%20Mehedi's gravatar image

Undefined Mehedi
4510


sort():

sort হচ্ছে যা আপনাকে কোন আরে সর্ট করে দিবে ঠিকই, কিন্তু যেটার/যেগুলোর উপর মেইনলি সর্ট করছেন সেগুলোর ভ্যালু সমান হলে এলিমেন্টগুলোর মধ্যে রিলেটিভ অর্ডার আগের মত নাও থাকতে পারে। যেমন ধরুন, আমার কাছে (x, y) আকারে ৩ পেয়ার ভ্যালু আছেঃ

১। (৫, ৭)

২। (১, ১৭)

৩। (১, ১৯)

এখন ধরুণ, সর্ট ফাংশন কল দিলাম, শুধু মাত্র x এর উপর ভিত্তি করে ছোট থেকে বড় সর্ট করার জন্য এবং এটি নিচের মত করে সর্ট করে দিলো।

১। (১, ১৯)

২। (১, ১৭)

৩। (৫, ৭)

এটা নিঃসন্দেহে একটি সঠিক সর্ট। কারণ আমরা বলেছি শুধু মাত্র x এর উপর সর্ট করতে। কিন্তু লক্ষ্য করুন (১, ১৭) এবং (১, ১৯) এই ২ পেয়ারের রিলেটিভ অর্ডার বদলে গেছে। আগে (১, ১৯) প্রথমে ছিলো, এখন (১, ১৭) প্রথমে।

stable_sort():

stable sort হচ্ছে যা আপনাকে কোন আরে সর্ট করে দিবে এবং সাথে সাথে যেটার/যেগুলোর উপর মেইনলি সর্ট করছেন সেগুলোর ভ্যালু সমান হলে এলিমেন্টগুলোর মধ্যে রিলেটিভ অর্ডার পূর্বের মত রাখাটা নিশ্চিত করবে। যেমন আগের উদাহরণটার ক্ষেত্রে stable_sort এর আউটপুট হবেঃ

১। (১, ১৭)

২। (১, ১৯)

৩। (৫, ৭)

অর্থাৎ x এর উপর ভিত্তি করে সর্ট হয়েছে, সাথে সাথে (১, ১৭) এবং (১, ১৯) এই ২ পেয়ারের রিলেটিভ অর্ডার ঠিক রেখেছে।

কিছু ব্যাপারঃ

১। অ্যারের প্রতিটি এলিমেন্টে যদি একটি মাত্র ভ্যালু করে থাকে সে ক্ষেত্রে ২টি সর্টের আউটপুট একই আসার কথা।

২। ছোট অ্যারের ক্ষেত্রে সাধারণত ভিন্ন আউটপুট পাওয়া যায় না, বড় অ্যারের ক্ষেত্রে সমস্যা হয়।

উদাহরনঃ

নিচে ২০ এলিমেন্টের একটি ভেক্টর নিয়ে উদাহরণ দেখিয়েছি, যার প্রতিটা এলিমেন্ট ২টি ভ্যালুর পেয়ার।

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

bool comp(pair<int,int> const &a,pair<int,int>  const &b)
{
    return a.first > b.first ;
}

int main()
{
    _
    int n = 3,k=20;
    vector< pair<int,int> >v(k),v2,vv;

    for(auto &x:v)
    {
        x.first = n%2?150-n/3:n/3;
        x.second = n%2?n:300-n;
        n++;
    }
    v2 = v;
    cout<<"Before:\n";
    for (auto &x:v)
        cout<<x.first<<" "<<x.second<<"\n";

    stable_sort(v.begin(), v.end(), comp);
    n = 0;
    cout<<"After Stable Sort:\n";
    for (auto &x:v)
        cout<<n++<<" :"<<x.first<<" "<<x.second<<"\n";
    vv = v;
    v = v2;

    sort(v.begin(), v.end(), comp);
    n = 0;
    cout<<"After Sort:\n";
    for (auto &x:v)
        cout<<n++<<" :"<<x.first<<" "<<x.second<<"\n";

    cout<<"Difference between two:\n";
    for (int i = 0; i<k; i++)
        if(vv[i]!=v[i])
        {
            cout<<i<<" (   v ) :"<<v[i].first<<" "<<v[i].second<<"\n";
            cout<<i<<" (  vv ) :"<<vv[i].first<<" "<<vv[i].second<<"\n";
        }


    return 0;
}

প্রোগ্রামটি রান করলে আমার পিসিতে নিচের মত আউটপুট দেয়ঃ

Before:
149 3
1 296
149 5
2 294
148 7
2 292
147 9
3 290
147 11
4 288
146 13
4 286
145 15
5 284
145 17
6 282
144 19
6 280
143 21
7 278
After Stable Sort:
0 :149 3
1 :149 5
2 :148 7
3 :147 9
4 :147 11
5 :146 13
6 :145 15
7 :145 17
8 :144 19
9 :143 21
10 :7 278
11 :6 282
12 :6 280
13 :5 284
14 :4 288
15 :4 286
16 :3 290
17 :2 294
18 :2 292
19 :1 296
After Sort:
0 :149 3
1 :149 5
2 :148 7
3 :147 11
4 :147 9
5 :146 13
6 :145 15
7 :145 17
8 :144 19
9 :143 21
10 :7 278
11 :6 282
12 :6 280
13 :5 284
14 :4 288
15 :4 286
16 :3 290
17 :2 292
18 :2 294
19 :1 296
Difference between two:
3 (   v ) :147 11
3 (  vv ) :147 9
4 (   v ) :147 9
4 (  vv ) :147 11
17 (   v ) :2 292
17 (  vv ) :2 294
18 (   v ) :2 294
18 (  vv ) :2 292

এখানে পর্যবেক্ষণ করলে দেখবেন vv তে সবসময় রিলেটিভ অর্ডার মেইন্টেইন করতেছে, কারণ এটি stable sort করার পর পাওয়া।

কোন কিছু না বুঝলে জিজ্ঞেস করতে পারেন।

ধন্যবাদ।

permanent link

answered 14 Feb '16, 01:46

manetsus's gravatar image

manetsus
2.2k211

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×131
×14

question asked: 13 Feb '16, 20:56

question was seen: 892 times

last updated: 14 Feb '16, 01:46