সিপিপি তে সর্ট এবং স্টেবল সর্ট ফাংশনের পার্থক্য

সিপিপি তো সর্ট আর স্টেবল সর্ট নামের দুটি পৃথক ফাংশন আছে। এই পোস্টের উদ্দেশ্য এদুটির পার্থক্য দেখানো,কিভাবে ব্যবহার করতে হয় শিখানো না। আজকে codeforces কনটেস্টে জিনিসটা মাথায় না থাকার কারণে একদম সহজ প্রবলেমে বিশাল ধরা খেয়েছি।

প্রবলেমটির লিংক:
http://www.codeforces.com/problemset/problem/63/A

এখানে বলা হয়েছে নিচের মত নামের লিস্ট দেয়া হবে:

6
Jack captain
Alice woman
Charlie man
Teddy rat
Bob child
Julia woman

এটাকে সর্ট করতে হবে এমন ভাবে যেন rat রা সবার সামনে আসে,তারপর woman আর child (এদের precedence সমান),তারপর man ও সবশেষে ক্যাপ্টেন। দুজনের precedence সমান হলে যাকে আগে ইনপুট দেয়া হয়েছে তাকে আগে রাখতে হবে। তাহলে আউটপুট হবে:

Teddy
Alice
Bob
Julia
Charlie
Jack

খুব সহজ সমস্যা,বেশ দ্রুত ৫মিনিটের মধ্যে কোড লিখে ফেললাম:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

struct node
{
	string S;
	int w;
	bool operator < ( const node &b) const{
	return w<b.w;} 
}e[10000];
int main()
{
	READ("in");
	int N,i;
	cin>>N;
	for(i=0;i<N;i++)
	{
		string name,X;
		cin>>name>>X;
		e[i].S=name;
		if(X=="rat")e[i].w=1;
		if(X=="woman")e[i].w=2;
		if(X=="child")e[i].w=2;
		if(X=="man")e[i].w=3;
		if(X=="captain")e[i].w=4;
	}
   sort(e,e+N);
   for(i=0;i<N;i++)
   cout<<e[i].S<<endl;
	return 0;
}

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define READ(f) freopen(f, "r", stdin)

#define WRITE(f) freopen(f, "w", stdout)

struct node

{

string S;

int w;

bool operator < ( const node &b) const{

return w<b.w;}

}e[10000];

int main()

{

READ("in");

int N,i;

cin>>N;

for(i=0;i<N;i++)

{

string name,X;

cin>>name>>X;

e[i].S=name;

if(X=="rat")e[i].w=1;

if(X=="woman")e[i].w=2;

if(X=="child")e[i].w=2;

if(X=="man")e[i].w=3;

if(X=="captain")e[i].w=4;

}

sort(e,e+N);

for(i=0;i<N;i++)

cout<<e[i].S<<endl;

return 0;

}

ভূল হবার সম্ভাবনা নেই ভেবে লক করে দিয়ে অন্যদের কোড দেখতে থাকলাম। সিস্টেম টেস্টের পর দেখি wrong answer,এত সহজ প্রবলেমে যা ছিল পুরাই অপ্রত্যাশিত। ভলিউমে সাবমিট করার পর যে কেসের জন্য ভূল হচ্ছিল দেখেই বুঝতে পারলাম সমস্যা কোথায়। কেসটা হলো:

20
Wswwcvvm woman
Btmfats rat
I rat
Ocmtsnwx man
Urcqv rat
Yghnogt woman
Wtyfc man
Wqle child
Ujfrelpu rat
Dstixj man
Ahksnio woman
Khkvaap woman
Sjppvwm rat
Egdmsv rat
Dank rat
Nquicjnw rat
Lh captain
Tdyaqaqln rat
Qtj rat
Tfgwijvq rat

আমার আউটপুট এসেছিল:

Tfgwijvq
Btmfats
I
Qtj
Urcqv
Tdyaqaqln
Nquicjnw
Dank
Ujfrelpu
Egdmsv
Sjppvwm
Khkvaap
Ahksnio
Wqle
Yghnogt
Wswwcvvm
Dstixj
Wtyfc
Ocmtsnwx
Lh

এটা অবশ্যই ভূল। শুরুতে Tfgwijvq এর জায়গায় btmfats থাকার কথা কারণ সেটা ইনপুটে আগে আছে।

এখানেই sort() আর stable_sort() এর পার্থক্য। পরেরটা input sequence টা ঠিক রাখে আগেরটা রাখেনা। stable_sort(e,e+N) লিখে কোডটি সাবমিট করার পরেই accepted হয়ে গেল যদিও যা ধরা খাওয়ার খেয়ে ফেলেছি। তবে বড় কোনো কনটেস্টে ধরা খাওয়ার থেকে এগুলোতে ধরা খেয়ে শেখা ভালো 🙂 ।

ফেসবুকে মন্তব্য

comments

7 thoughts on “সিপিপি তে সর্ট এবং স্টেবল সর্ট ফাংশনের পার্থক্য”

হুমম… সেই কবে সি প্লাস প্লাস গুতাইসিলাম।। 🙂

Anonymous says:

মার্চ ১, ২০১১ at ৬:৩৭ am

চিন্তা করছি মুক্তমনায় এরকম পোস্ট দিলে সবাই মারবে নাকি……….

Reply

brute force(5n) was enough to solve that problem, nlogn was not necessary 😀

no sort is required actually!!
i had solved it with normal procedure..

#include <iostream>
#include <algorithm>
#include <list>
#include <fstream>
#include <vector>
using namespace std;
int main(){
   // freopen("in.txt","r",stdin);
//ifstream in("in.txt");
vector <string> rat;
vector <string> w_c;
vector <string> man;
vector <string>::iterator pos;
string captain;
string name, tag;
int n;
cin>>n;
while(n--){
cin>>name>>tag;
if(tag=="man")
man.push_back(name);
if(tag=="rat")
rat.push_back(name);
if(tag=="captain")
captain=name;
if(tag=="woman" || tag=="child")
w_c.push_back(name);
}
for(int i=0;i<rat.size();i++)
cout<<rat[i]<<endl;
for(int i=0;i<w_c.size();i++)
cout<<w_c[i]<<endl;
for(int i=0;i<man.size();i++)
cout<<man[i]<<endl;
cout<<captain<<endl;
}

#include <iostream>

#include <algorithm>

#include <list>

#include <fstream>

#include <vector>

using namespace std;

int main(){

// freopen("in.txt","r",stdin);

//ifstream in("in.txt");

vector <string> rat;

vector <string> w_c;

vector <string> man;

vector <string>::iterator pos;

string captain;

string name, tag;

int n;

cin>>n;

while(n--){

cin>>name>>tag;

if(tag=="man")

man.push_back(name);

if(tag=="rat")

rat.push_back(name);

if(tag=="captain")

captain=name;

if(tag=="woman" || tag=="child")

w_c.push_back(name);

}

for(int i=0;i<rat.size();i++)

cout<<rat[i]<<endl;

for(int i=0;i<w_c.size();i++)

cout<<w_c[i]<<endl;

for(int i=0;i<man.size();i++)

cout<<man[i]<<endl;

cout<<captain<<endl;

}

এক প্রবলেম অনেক ভাবেই সলভ করা যেতে পারে :)। সর্ট করতে গিয়ে ধরা খেয়ে স্টেবল সর্টের ব্যাপারটা জেনেছি তাই ব্লগটি লেখা।

difference ta jane onek valo laglo..thanks.

ডিফারেন্সটা জেনে ভালো লাগলো । স্টেবল সর্ট এর কথা জানতাম তবে ইউজ করি নি কখোনো ? একটা প্রশ্ন ছিলো । সর্ট এর জায়গায় স্টেবল সর্ট ব্যবহার করলে কি নরমাল সর্টিং এর প্রব্লেম গুলোর এনসার গুলোর কোনো সমস্যা হবে ?? নাকি একই এন্সার আসবে ??

শাফায়েতের ব্লগ

সিপিপি তে সর্ট এবং স্টেবল সর্ট ফাংশনের পার্থক্য

ফেসবুকে মন্তব্য

7 thoughts on “সিপিপি তে সর্ট এবং স্টেবল সর্ট ফাংশনের পার্থক্য”

Leave a Reply Cancel reply