[Powered by Google Translate] [সন্নিবেশন সাজান] [টমি MacWilliam] [হার্ভার্ড বিশ্ববিদ্যালয়] [এটি CS50.TV] যাক এর সন্নিবেশ সাজানোর কটাক্ষপাত, সংখ্যার একটি তালিকা গ্রহণ এবং তাদের বাছাই করার জন্য একটি অ্যালগরিদম নিতে. একটি অ্যালগরিদম,, মনে রাখবেন শুধু একটি টাস্ক accomplishing জন্য ধাপে ধাপে পদ্ধতি. সন্নিবেশ সাজানোর পিছনে মৌলিক দুটি অংশ মধ্যে আমাদের তালিকা বিভক্ত করা হয়, একটি সাজানো অংশ এবং একটি পাঁচমিশালী অংশ. 

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

একবার আমরা শুরু বাছাই, আমরা এই সংখ্যা অনুসারে সাজানো এই বাঁদিকে রেখে দেব. সুতরাং, আসুন 23, আমাদের তালিকায় প্রথম উপাদান দিয়ে শুরু. আমরা এখনও আমাদের অনুসারে বাছাই করা অংশ কোন উপাদান না, তাই আসুন সহজভাবে 23 আমাদের অনুসারে বাছাই করা অংশ শুরু এবং শেষের বিবেচনা. এখন, আমাদের অনুসারে বাছাই করা অংশ এক নম্বর, 23 আছে, এবং আমাদের পাঁচমিশালী অংশ এই পাঁচটি সংখ্যা আছে. চলুন এখন আমাদের পাঁচমিশালী অংশ, 42, মধ্যে সাজানো অংশ মধ্যে পরবর্তী সংখ্যা ঢোকান. 

আমাদের অনুসারে বাছাই করা অংশ একমাত্র উপাদান এতদূর - তাই না, আমরা 23 তে 42 তুলনা করতে হবে. চল্লিশ দুটি হয় 23 থেকে বড়, তাই আমরা শুধু শেষে 42 সংযুক্ত করতে পারেন তালিকায় অনুসারে বাছাই করা অংশ. গ্রেট! এখন আমাদের অনুসারে বাছাই করা অংশ দুটি উপাদান রয়েছে, এবং আমাদের পাঁচমিশালী অংশ চারটি উপাদান রয়েছে. সুতরাং, এখন এর 4 সরানো যাক, পাঁচমিশালী অংশ পরবর্তী উপাদান. সুতরাং, যেখানে সাজানো এই অংশে স্থাপন করা উচিত? 

মনে রাখবেন, আমরা ক্রম অনুসারে সাজানো এই সংখ্যাটি লিখুন চান তাই আমাদের অনুসারে বাছাই করা অংশ অবশেষ সব সময়ে সঠিকভাবে সাজানো. যদি আমরা 42 ডানদিকে 4 লিখুন তারপর, আমাদের তালিকা আদেশ করা হবে. সুতরাং, আসুন আমাদের সাজানোর অংশ যাচ্ছেন ডান বাম অবিরত. হিসাবে আমরা সরাতে, যাক এর একটি জায়গা নিচে প্রতিটি নম্বরে একটি নতুন নম্বর জন্য জায়গা নামান. ঠিক আছে, 4 এ কম 23, যাতে আমরা এখানে রাখুন না হয় পারেন. যাক 23 এর ডান এক জায়গায় সরাতে. 

তার মানে আমরা অনুসারে বাছাই করা অংশ প্রথম স্লটে মধ্যে 4 দিতে চাই. কিভাবে এই তালিকায় স্থান ইতিমধ্যে খালি বিজ্ঞপ্তি, কারণ আমরা করছি সাজানো উপাদান চলন্ত নিচে হিসাবে আমরা তাদের সম্মুখীন হয়েছি. ঠিক আছে. সুতরাং, আমরা halfway আছে. চলুন অনুসারে বাছাই করা অংশ মধ্যে 16 ড্রাইভে ঢোকাতে আমাদের এলগরিদম অবিরত. ষোল কম 42, তাই এর ডান 42 নামান যাক. ষোল এছাড়াও কম 23, তাই এর যে উপাদান নামান যাক. 

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

ঠিক আছে. এখন, আমরা চার সাজানো উপাদান এবং দুই পাঁচমিশালী উপাদান আছে. সুতরাং, আসুন অনুসারে বাছাই করা অংশ মধ্যে 8 সরাতে. আট কম 42. আট কম 23. এবং 8 কম 16. কিন্তু 8 4 হয় তার চেয়ে অনেক বেশী. সুতরাং, আমরা 4 এবং 16 এর মধ্যে 8 সন্নিবেশ চাই. 15 - এবং এখন আমরা আরও একটি উপাদান বাছাই যাও বাকি আছে. পঞ্চদশ কম 42, পঞ্চদশ কম 23. এবং 15 কম 16. কিন্তু 15 8 হয় তার চেয়ে অনেক বেশী. 

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

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

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

আমরা জানি যে এর অবস্থান ঞ মধ্যে সন্নিবেশ ঠিক আছে যাও, কারণ ইতিমধ্যে আমরা উপাদান যে অধিকার আছে এক স্থান ব্যবহার করেছি সরানো. মনে রাখবেন, আমরা ডান থেকে বাম অংশের মাধ্যমে সাজানো যাও চলন্ত করছি, কিন্তু আমরা বাম থেকে ডান পাঁচমিশালী অংশের মাধ্যমে চলন্ত করছি. ঠিক আছে. চলুন এখন কতদিন চলমান যে অ্যালগরিদম গ্রহণ কটাক্ষপাত করা. আমরা প্রথম প্রশ্ন কতদিন এটা জন্য এই অ্যালগরিদম লক চালানোর নিতে বলব. পুনরাহ্বান যে আমরা বিগ হে স্বরলিপি সঙ্গে এই চলমান সময় প্রতিনিধিত্বকারী. আমাদের তালিকা বাছাই, আমরা পাঁচমিশালী অংশ উপাদান পুনরুক্তি করা ছিল, এবং এর জন্য প্রতিটি সম্ভাব্য সাজানো অংশে সব উপাদানের উপরে যারা উপাদানের,. Intuitively, একটি হে (ঢ ^ 2) অপারেশন মত এই শব্দ. 

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

আমরা summations ঢোকা এখানে হবে না, কিন্তু এটি সক্রিয় আউট যে এই সঙ্কলন সমান যাও n (n - 1) 2 উপর, যা সম n ^ 2/2 - n / 2. Asymptotic রানটাইম সম্পর্কে যখন কথা বলা, এই n ^ 2 শব্দ থেকে এই শব্দটি n আয়ত্তে আনা যাচ্ছে না. সুতরাং, সন্নিবেশ সাজানোর হয় বিগ O (n ^ 2). . যদি আমরা একটি ইতিমধ্যে অনুসারে সাজানো তালিকা সন্নিবেশ সাজানোর দৌড়ে সেই ক্ষেত্রে, কেবলমাত্র আমরা নির্মাণ বাঁ দিক থেকে ডানদিকে অনুসারে বাছাই করা অংশ আপ চাই. সুতরাং, আমরা কেবল n ধাপ অনুক্রম করতে হবে. 

তার মানে যে সন্নিবেশ সাজানোর একটি n শ্রেষ্ঠ ক্ষেত্রে কর্মক্ষমতা রয়েছে, যা আমরা Ω (ঢ) সঙ্গে চিত্রিত করা. এবং যে সন্নিবেশ সাজানোর জন্য এটি, শুধু অনেক আলগোরিদিম একটি তালিকা বাছাই আমরা ব্যবহার করতে পারেন. আমার নাম টমি, এবং এই CS50. [CS50.TV] ওহ, আপনি যে একবার এটি আরম্ভ করা থামাতে পারে না. ওহ, আমরা যে কি - >> পরিস্ফুটন!