[Powered by Google Translate] [সাজান মার্জ] [Rob Bowden - হার্ভার্ড বিশ্ববিদ্যালয়] [এটি CS50. - CS50.TV] এর একত্রীকরণ সাজানোর সম্পর্কে কথা বলা যাক. এ পর্যন্ত আপনি বুদ্বুদ সাজানোর, সন্নিবেশ সাজানোর, এবং নির্বাচন সাজানোর দেখা করেছি. যদিও আমি ভাল দ্বারা মানে আমার হাত তরঙ্গ ধরনের করব, সাজানোর একত্রীকরণ সাধারণত সঞ্চালিত এই 3 প্রকারের কোনো চেয়ে ভাল. 

কিন্তু একত্রীকরণ সাজানোর বিষয়ে কথা আগে, আসুন 2 অনুসারে সাজানো তালিকা মার্জ সম্পর্কে কথা বলুন. আমরা এই মত অনুসারে সাজানো তালিকা 2 গ্রহণের প্রক্রিয়া কল, করব, এবং একটি একক তাদের অনুসারে সাজানো তালিকা তৈরীর আউট - সুচী মার্জ. কিভাবে এই আমরা কি করতে পারি? তবে, ধারণা শুধু অন্যান্য তালিকার শেষে সম্মুখের একটি তালিকা বিদ্ধ করা হয় এবং তারপর অনুসন্ধানের ফলাফলের তালিকায় সাজাতে. 

যদিও এই কাজ করে, এটা অপ্রয়োজনীয় কাজ অনেক. আমরা শুধু বাছাই চেয়ে এটা দ্রুত করতে পারেন. উল্লেখ্য, একটি ভুল ধারণা মাত্র প্রতিটি তালিকা থেকে পর্যায়ক্রমে কাপ নিতে হয়. যদিও যে যে কাজ মত প্রথমে মনে হতে পারে, করছেন যা আমরা 4, 8, 15, 23, 16 সঙ্গে শেষ - বিজ্ঞপ্তি অনুযায়ী 16 এবং 23 জায়গা হয়ে গেছে. কারণ 2 উপাদান আছে যা মার্জ তালিকা প্রদর্শিত পরপর করা উচিত একই প্রারম্ভিক তালিকা আছে. উভয় 15 এবং 16 বাম দিকের তালিকার মধ্যে. কৌতুক যাও যে ইতিমধ্যে উভয় তালিকা অনুসারে বাছাই করা হয় সদ্ব্যবহার করা হয়. এর মানে হল যে যদি আমরা শুধুমাত্র উভয় তালিকার প্রথম উপাদান তাকান - এখানে, 4 এবং 8 - এ তাদের একজন হতে মার্জ তালিকার প্রথম উপাদান আবশ্যক. ভাল, কেন হল? এই তালিকা দুটি ইতিমধ্যেই সাজানো, এবং তাই হয় 4 বা 8 ক্ষুদ্রতম উপাদান যখন আমরা 2 তালিকা একত্রিত হতে হবে. এই ক্ষেত্রে, ক্ষুদ্রতম 4 টি, তাই আমরা 4 সময় নিন এবং এটি আমাদের মার্জ তালিকার প্রথম উপাদান করতে পারেন. এখন আমরা অবশিষ্ট প্রথম তালিকার 3 উপাদান মার্জ অবিরত এবং দ্বিতীয় তালিকার 4 উপাদান. 

আবার, আমরা শুধুমাত্র উভয় তালিকার প্রথম উপাদান তাকান প্রয়োজন. 2 ছোট আমাদের মার্জ তালিকার দ্বিতীয় উপাদান হতে হবে. 8 এবং 15 এর মধ্যে এই সময়, 8 ক্ষুদ্রতম হয়, এবং তাই আমরা যে সন্নিবেশ হিসাবে আমাদের অনুসারে সাজানো তালিকা দ্বিতীয় উপাদান. আমরা উভয় তালিকার প্রথম উপাদান তুলনা অবিরত করতে পারেন এবং 2 ছোট সরিয়ে ফেলা হয়. 15 এবং 23, 15 তুলনা হয় ছোট এবং যাতে এর আমাদের তৃতীয় উপাদান. এখন 16 তুলনা করে এবং 23, 16 হয় ছোট. যাতে এর চতুর্থ উপাদান. 

উল্লেখ্য, 2 উপাদানের একটি সারিতে একই তালিকা থেকে এসেছিলেন. এটি কেন মার্জ তালিকা মাত্র 2 তালিকা থেকে বিকল্প উপাদানের করতে পারেন না. 50 এবং 23, 23 তুলনা হয় ছোট, তাই আমরা যে নির্বাচন করুন. 50 এবং 42 এর মধ্যে, 42 হয় ছোট. 50 এবং 108 এর মধ্যে, 50 হয় ছোট. এবং পরিশেষে, আমরা মাত্র 108 আছে, তাই এটা আমাদের তালিকার শেষে অবস্থিত নেভিগেশন এড়িয়ে যেতে হবে. উল্লেখ্য, আমরা একটি সুন্দর, সাজানো তালিকা আছে. প্রতিটি সময় আমরা প্রথম 2 তালিকার 2 উপাদান তুলনা আমরা মার্জ তালিকা পরবর্তী উপাদান নির্ধারণ করে. এর মানে হল যে যদি চূড়ান্ত তালিকা n সংখ্যা, যেখানে n হল এখানে রয়েছে 8, তারপর আমরা যথাস্থান মধ্যে যারা সংখ্যার সব পাওয়া সবচেয়ে n তুলনা এ প্রয়োজন. যেমন একটি অ্যালগরিদম রৈখিক সময় চালানোর জন্য বলা হয়, কিন্তু যে সম্পর্কে এখানে না চিন্তা. 

মার্জ জন্য আমাদের এলগরিদম ব্যবহার করে, আমরা একটি দ্রুত একত্রীকরণ সাজানোর আলগোরিদিম করতে পারেন. সুতরাং, আসুন আমাদের তালিকা রিসেট করুন. 2 একত্রীকরণ সাজানোর প্রক্রিয়ায় বড় ধাপ আছে. প্রথম অবিরত, অর্ধেক কাপ মধ্যে তালিকা বিভক্ত করুন যতক্ষণ না আমরা শুধু তাদের মধ্যে 1 কাপ সঙ্গে তালিকার একটি গুচ্ছ আছে. যদি একটি তালিকা একটি বিজোড় সংখ্যা উপস্থিত রয়েছে চিন্তা এবং আপনি তাদের মধ্যে পুরোপুরি কেটে পরিষ্কার করতে পারবেন না. শুধু ইচ্ছামত বাছাই তালিকা যা অতিরিক্ত কাপ ইন অন্তর্ভুক্ত সুতরাং, আসুন এই তালিকা বিভক্ত. এখন আমরা 2 তালিকা আছে. এখন আমরা 4 তালিকা আছে. 

এবং এখন আমরা একটি তালিকা প্রতিটি একক কাপ সঙ্গে 8 তালিকা আছে. যাতে এর ধাপ 1 জন্য এটি. ধাপ 2 জন্য, বার বার আমরা একত্রীকরণ এলগরিদম ব্যবহার করে আমরা আগে শিখেছি তালিকা জোড়া একত্রীকরণ. 108 এবং 15 মার্জ, আমরা তালিকায় 15, 108 দিয়ে শেষ পর্যন্ত. 50 এবং 4 মার্জ, আমরা 4, 50 দিয়ে শেষ পর্যন্ত. 8 এবং 42 মার্জ, আমরা 8 সঙ্গে শেষ 42,. এবং 23 এবং 16 মার্জ, আমরা 16 সঙ্গে শেষ 23,. এখন সব আমাদের তালিকা আকার 2 হয়. উল্লেখ্য, 4 তালিকার প্রতিটি সাজানো হয়. 

সুতরাং আমরা তালিকা জোড়া মার্জ আবার শুরু করতে পারেন. 15 এবং 108 এবং 4 এবং 50 মার্জ - প্রথম 4 টি, তাহলে 15, তারপর 50, তারপর 108. 8, 42 এবং 16, 23 মার্জ, আমরা প্রথম তারপর 8, 16, তারপর 23, তারপর 42 নিতে. তাই এখন আমরা 4 আকার মাত্র 2 তালিকা আছে, প্রতিটি যা সাজানো হয়. তাই এখন আমরা এইসব 2 তালিকা একত্রীকরণ. প্রথম আমরা 4 নিতে. তারপর আমরা 8 নিতে. তারপর আমরা 15 এবং তারপর 16, 23, তারপর 42, তারপর 50, 108 তারপর নিতে. এবং আমরা কাজ সম্পন্ন হয়. আমরা এখন একটি অনুসারে সাজানো তালিকা আছে. সুতরাং কিভাবে দ্রুত ছিল এই ঠিক,? পরিভাষা ইন, একত্রীকরণ সাজানোর হয় O (n log n), যেহেতু বুদ্বুদ সাজানোর, সন্নিবেশ সাজানোর, এবং নির্বাচন ধরণের সব হয় হে (ঢ ²). আসলে, যত তাড়াতাড়ি আপনি জানতে পারবেন, আপনি কেমন চিন্তা করতে পারবে না যে সাধারণ ক্ষেত্রে সঞ্চালিত O (n log n) চেয়ে ভাল. আবার, এই বড় হে স্বরলিপি সম্পর্কে এখনো যদি আপনি এটি দেখা না না দিয়ে চিন্তা করবেন. 

শুধু যে এই অর্থ জানা যদি আমরা একটি বড় তালিকা সাজাতে চেয়েছিলেন বুদ্বুদ সাজানোর, সন্নিবেশ সাজানোর, এবং নির্বাচন সাজানোর সম্ভাব্য ব্যয় হতে পারে সময়ের চেয়ে উল্লেখযোগ্যভাবে সাজানোর একত্রীকরণ. এটা যে একত্রীকরণ সাজানোর জন্য দ্রুত সব তালিকায় করা মানে এই নয় অথবা এমনকি জন্য কোনো একটি নির্দিষ্ট মাপ অধীন একক তালিকা. উদাহরণস্বরূপ, সন্নিবেশ সাজানোর সব তালিকায় 5 উপাদানের চেয়ে ছোট দ্রুততম সাজানোর জন্য হতে পারে. বাস্তবে, একত্রীকরণ 50 সাজানোর উপাদান হিসাবে ছোট হিসাবে তালিকার জন্য সাধারণত দ্রুত. 

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

আমার নাম Rob Bowden, এবং এই CS50. [CS50.TV] - এবং সাজানোর নির্বাচন. [Laughs] ওহ, যে খুব আউট নিতে কারণ আমি সুইচ কিভাবে আমি এটি উপস্থাপনা ছিল না. বাম তালিকা. এটা ছিল একটা টাইপো. [Misspoke] আমি মাতাল আপ - [Laughs] আমি কি জানি না -