কন্টেন্ট

• তুলনা রেখাচিত্র
• দ্রুত বাছাইয়ের সংজ্ঞা
• মার্জ সাজানোর সংজ্ঞা
• উপসংহার

দ্রুত সাজানোর এবং মার্জ করা সাজানোর অ্যালগরিদমগুলি বিভাজন এবং বিজয়ী অ্যালগরিদমের উপর ভিত্তি করে তৈরি হয় যা বেশ একইভাবে কাজ করে। দ্রুত এবং মার্জ সাজানোর মধ্যে পূর্বের পার্থক্যটি হ'ল দ্রুত সারণিতে পিভট উপাদানটি বাছাইয়ের জন্য ব্যবহৃত হয়। অন্যদিকে, মার্জ বাছাই বাছাই করার জন্য পিভট উপাদান ব্যবহার করে না।

উভয় বাছাই কৌশল, দ্রুত সাজানো এবং মার্জ সাজানোর বিভাজন এবং বিজয় পদ্ধতিতে নির্মিত হয় যেখানে উপাদানগুলির সেটটি ভাগ করা হয় এবং তারপরে পুনর্বিন্যাসের পরে সংযুক্ত করা হয়। দ্রুত সাজানোর ক্ষেত্রে উপাদানের একটি বড় সেট বাছাইয়ের জন্য মার্জ সাজানোর চেয়ে আরও তুলনা প্রয়োজন।

1. 1. তুলনা রেখাচিত্র
   2. সংজ্ঞা
   3. মূল পার্থক্য
   4. উপসংহার

তুলনা রেখাচিত্র

তুলনার জন্য ভিত্তি	দ্রুত বাছাই	বাছাই মার্জ
অ্যারেতে উপাদানগুলির বিভাজন	উপাদানগুলির তালিকার বিভাজন অগত্যা অর্ধে বিভক্ত নয়।	অ্যারে সর্বদা অর্ধে ভাগ করা হয় (এন / 2)।
সবচেয়ে খারাপ ক্ষেত্রে জটিলতা	উপর2)	ও (এন লগ এন)
ভাল কাজ করে	ছোট অ্যারে	যে কোনও ধরণের অ্যারেতে সূক্ষ্মভাবে কাজ করে।
গতি	ছোট ডেটা সেটের জন্য অন্য বাছাই করা অ্যালগরিদমের চেয়ে দ্রুত।	সব ধরণের ডেটা সেটে ধারাবাহিক গতি।
অতিরিক্ত সঞ্চয় স্থান প্রয়োজন	কম	অধিক
দক্ষতা	বৃহত্তর অ্যারেগুলির জন্য অপ্রতুল।	আরো দক্ষ.
বাছাই পদ্ধতি	অভ্যন্তরীণ	বহিরাগত

দ্রুত বাছাইয়ের সংজ্ঞা

দ্রুত বাছাই সংক্ষিপ্ত অ্যারেগুলির জন্য দ্রুত হওয়ায় অ্যালগরিদমকে বাছাই করার জন্য এটি ব্যাপকভাবে ব্যবহৃত হয়। উপাদানগুলির সেটটি বারে বারে ভাগ করা হয় যতক্ষণ না এটি আরও বিভাজন করা সম্ভব হয় না। দ্রুত সাজানোর হিসাবে পরিচিত পার্টিশন এক্সচেঞ্জ সাজান। এটি উপাদানগুলির বিভাজনের জন্য একটি মূল উপাদান (পিভট হিসাবে পরিচিত) ব্যবহার করে। একটি পার্টিশনে মূল উপাদানগুলির চেয়ে ছোট ছোট উপাদান রয়েছে। অন্য একটি পার্টিশনে মূল উপাদানগুলির চেয়ে বড় সেগুলি রয়েছে। উপাদানগুলি পুনরাবৃত্তভাবে বাছাই করা হয়।

ধরুন A হ'ল একটি অ্যারে, এ, এ, …… .., এ, এন সংখ্যার যেটি বাছাই করতে হবে। দ্রুত সাজানোর অ্যালগরিদম নিম্নলিখিত পদক্ষেপ নিয়ে গঠিত।

1. কী হিসাবে নির্বাচিত প্রথম উপাদান বা যেকোন এলোমেলো উপাদান, ধরে নিন কী = এ (1)।
2. "নিম্ন" পয়েন্টারটি দ্বিতীয় স্থানে এবং "আপ" পয়েন্টার অ্যারের শেষ উপাদানটিতে অবস্থিত, অর্থাত্ কম = 2 এবং উপরে = এন;
3. ধারাবাহিকভাবে, "নিম্ন" পয়েন্টারটিকে (এ> কী) অবধি এক অবস্থান দ্বারা বৃদ্ধি করুন।
4. ধারাবাহিকভাবে, "আপ" পয়েন্টারটিকে একটি অবস্থান দ্বারা (A <= কী) অবধি হ্রাস করুন।
5. আপ যদি এ এর ​​সাথে কম ইন্টারচেঞ্জ এ এর ​​চেয়ে বেশি হয়
6. পদক্ষেপ ৩,৪ এবং 5 এর পুনরাবৃত্তি করুন যতক্ষণ না পদক্ষেপ 5-এর শর্তটি ব্যর্থ হয় (অর্থাত্ <= কম) তারপরে এটিকে কী দ্বারা পরিবর্তন করুন।
7. যদি কীটির বাম উপাদানগুলি কীটির চেয়ে ছোট হয় এবং কীগুলির ডান উপাদানগুলি কীটির চেয়ে বড় হয় তবে অ্যারেটি দুটি সাব-অ্যারেতে বিভক্ত হয়।
8. উপরের পদ্ধতিটি বারবার সাবারিগুলিতে প্রয়োগ করা হয় যতক্ষণ না পুরো অ্যারেটি বাছাই করা হয়।

   

   
   

সুবিধাগুলি এবং অসুবিধাগুলি

এটির একটি ভাল গড় কেস আচরণ রয়েছে। দ্রুত সাজানোর চলমান সময়ের জটিলতাটি এটি ভাল যে এটি বুদ্বুদ সাজানো, সন্নিবেশ সারণি এবং নির্বাচন সাজানোর মতো অ্যালগরিদমের চেয়ে দ্রুত। তবে এটি জটিল এবং খুব পুনরাবৃত্তিমূলক কারণ এটি বড় অ্যারেগুলির জন্য উপযুক্ত নয়।

মার্জ সাজানোর সংজ্ঞা

বাছাই মার্জ এটি একটি বাহ্যিক অ্যালগরিদম যা বিভাজন এবং বিজয়ী কৌশলের উপর ভিত্তি করে। কেবলমাত্র একটি উপাদান বাকি না হওয়া পর্যন্ত উপাদানগুলি বারবার সাব-অ্যারে (এন / 2) এ বিভক্ত হয়, যা বাছাইয়ের সময়টিতে উল্লেখযোগ্য পরিমাণ হ্রাস পায়। এটি সহায়ক অ্যারে সঞ্চয় করার জন্য অতিরিক্ত সঞ্চয়স্থান ব্যবহার করে। মার্জ সাজ্টে তিনটি অ্যারে ব্যবহার করা হয় যেখানে প্রতি অর্ধে দুটি সংরক্ষণের জন্য দুটি ব্যবহৃত হয় এবং তৃতীয়টি চূড়ান্ত বাছাই করা তালিকা সঞ্চয় করতে ব্যবহৃত হয়। প্রতিটি অ্যারে তখন পুনরাবৃত্তভাবে বাছাই করা হয়। অবশেষে, এটিকে অ্যারের উপাদান উপাদান আকারে তৈরি করতে সাববারিগুলি একত্রিত করা হয়েছে। তালিকাটি সর্বদা মাত্র অর্ধেক (n / 2) এ ভাগ করা যায় দ্রুত সাজানোর থেকে পৃথক diss

A কে A, A, ………, A. বাছাই করার জন্য n সংখ্যক উপাদানের অ্যারে হতে দিন মার্জ সাজানোর প্রদত্ত পদক্ষেপগুলি অনুসরণ করে।

1. অ্যারে A প্রায় 2/2 অনুসারে বাছাই করা সাব-অ্যারে বিভক্ত করুন যার অর্থ (A, A), (A, A), (A, A), (A, A) সাব-অ্যারেগুলিকে অবশ্যই আবশ্যক সাজানো ক্রম হতে।
2. আকারের 4 অনুসারে বাছাই করা সাববারির তালিকাটি পেতে প্রতিটি জোড়া জোড়া করুন; সাবারিগুলির উপাদানগুলিও সাজানো ক্রমে, (ক, এ, এ, ক), ……, (এ, এ, ক, ক), ……।, (এ, এ, এ, এ) রয়েছে।
3. মাপের এন এর মধ্যে একটি মাত্র সাজানো অ্যারে না হওয়া পর্যন্ত ধাপ 2 বার বার করা হয়।

   

সুবিধাগুলি এবং অসুবিধাগুলি

মার্জ সাজানোর অ্যালগরিদম বাছাইয়ের সাথে জড়িত উপাদানগুলির নির্বিশেষে নির্ভুলভাবে একই এবং সুনির্দিষ্টভাবে সম্পাদন করে। এটি বড় ডেটা সেট দিয়েও দুর্দান্ত কাজ করে। তবে এটি মেমরির বৃহত্তর অংশ গ্রাস করে mes

1. মার্জ সাজানোর ক্ষেত্রে অ্যারেটি কেবলমাত্র দুটি অংশে বিভক্ত হওয়া উচিত (অর্থাত্ এন / ২) বিপরীতে, দ্রুত সাজানোর ক্ষেত্রে, তালিকাটি সমান উপাদানগুলিতে ভাগ করার কোনও বাধ্যবাধকতা নেই।
2. দ্রুত সাজানোর সবচেয়ে খারাপ ক্ষেত্রে জটিলতা হ'ল ও (এন)²) এটি সবচেয়ে খারাপ অবস্থার তুলনায় অনেক বেশি তুলনা করে। বিপরীতে, সংযুক্তি বাছাইয়ের ক্ষেত্রে একই খারাপ পরিস্থিতি এবং গড় কেস জটিলতা রয়েছে that এটি হ'ল (এন লগ এন)।
3. মার্জ বাছাই কোনও ধরণের ডেটা সেটগুলিতে ভাল বা ছোট কিনা তা ভালভাবে পরিচালনা করতে পারে। বিপরীতে, দ্রুত সাজানো বড় ডেটাসেটের সাথে ভালভাবে কাজ করতে পারে না।
4. কিছু ক্ষেত্রে যেমন ছোট ডেটা সেটগুলির ক্ষেত্রে মার্জ্ট সাজ্টের চেয়ে দ্রুত বাছাই করা দ্রুত হয়।
5. মার্জ সাজানোর জন্য সহায়ক অ্যারেগুলি সঞ্চয় করতে অতিরিক্ত মেমরি স্থান প্রয়োজন। অন্যদিকে, দ্রুত সাজানোর জন্য অতিরিক্ত স্টোরেজ করার জন্য খুব বেশি জায়গার প্রয়োজন হয় না।
6. মার্জ বাছাই দ্রুত বাছাইয়ের চেয়ে কার্যকর is
7. দ্রুত বাছাই হ'ল অভ্যন্তরীণ বাছাইয়ের পদ্ধতি যেখানে মুছে ফেলা হবে এমন ডেটা মূল স্মৃতিতে একসাথে সামঞ্জস্য করা হয়। বিপরীতভাবে, মার্জ সাজ্টটি বাহ্যিক বাছাইয়ের পদ্ধতি যা বাছাই করতে হবে এমন ডেটা একই সময়ে মেমরিতে সামঞ্জস্য করা যায় না এবং কিছুটিকে সহায়ক মেমরিতে রাখতে হয়।

উপসংহার

দ্রুত বাছাই দ্রুত ক্ষেত্রে হয় তবে কিছু পরিস্থিতিতে এটি অকার্যকর এবং সংযোজনীয় সাজানোর তুলনায় অনেক তুলনাও করে। যদিও মার্জ সাজানোর জন্য কম তুলনা প্রয়োজন, অতিরিক্ত অ্যারে সংরক্ষণের জন্য এটি 0 (n) এর অতিরিক্ত মেমরি স্পেস প্রয়োজন যখন দ্রুত সাজানোর জন্য ও (লগ এন) এর স্থান প্রয়োজন।