If you're seeing this message, it means we're having trouble loading external resources on our website.

তোমার যদি কোন ওয়েব ফিল্টার দেওয়া থাকে, তাহলে দয়া করে নিশ্চিত কর যে *.kastatic.org এবং *.kasandbox.org ডোমেইনগুলো উন্মুক্ত।

মূল বিষয়বস্তু

কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 1

পাঠ 4: সিলেকশন সর্ট
কম্পিউটিং
কম্পিউটার বিজ্ঞান
অ্যালগোরিদম
সিলেকশন সর্ট
© 2024 Khan Academyব্যবহারের শর্তাদিগোপনীয়তার নীতিমালাকুকি নোটিশ

সিলেকশন সর্ট বিশ্লেষণ

গুগল শ্রেণিকক্ষ
সিলেকশন সর্ট অ্যারে এর সূচকগুলো লুপ করে; প্রতিটি ইনডেক্স এর জন্য; সিলেকশন সর্ট indexOfMinimum এবং swapকল করে। যদি অ্যারে এর দৈর্ঘ্য n হয়, তাহলে অ্যারের ইনডেক্স সংখ্যা n হবে।
যেহেতু লুপ এর বডি ( body ) প্রতিবার কোড এর দুই লাইন রান করে সেহেতু তুমি হয়ত মনে করতে পার যে কোডের 2n লাইন সিলেকশন সর্ট এর মাধ্যমে সম্পাদন হয়। কিন্তু এটা সত্য নয়! মনে রাখতে হবে যে indexOfMinimum এবং swap এই দুইটি হচ্ছে ফাংশন: এদের মধ্যে যদি যে কোন একটিও কল করা হয় তাহলে কোডের কিছু লাইন সম্পাদিত হবে।
একবার swap কমান্ডটি কল করলে কোডের কয়টি লাইন কাজ করবে? স্বাভাবিকভাবে তিনটি লাইন কাজ করবে, অর্থাৎ swap এর প্রতিটি কল ধ্রুবক সময় ব্যবহার করে কোডের তিনটি লাইনের কাজ সম্পাদন করে।
একটি সিঙ্গেল (single)indexOfMinimum কলে কোডের কয়টি লাইন সম্পাদন হয়? এক্ষেত্রে indexOfMinimum ভিতরে থাকা লুপটিও আমাদের গণনার ভিতরে রাখতে হবে। indexOfMinimum এর কলে লুপটি কতবার চলে? এটি সাব-অ্যারের আকারের উপরে নির্ভর করে, যার উপর ভিত্তি করেই এই পুনরাবৃত্তি ঘটতে থাকে। যদি সাব-অ্যারে একটি সম্পূর্ণ অ্যারে হয় (প্রথম ধাপের মত), তাহলে লুপটি n সংখ্যক বার কার্যকর হয়। যদি সাব-অ্যারের আকার 6 হয়, তাহলে লুপটি 6 বার কার্যকর হবে।
উদাহরণস্বরূপ, ধরা যাক সম্পূর্ণ অ্যারের আকার হল 8, তাহলে এখন চিন্তা করে দেখা যাক সিলেকশন সর্ট কীভাবে কাজ করে।
  1. In the first call of indexOfMinimum, it has to look at every value in the array, and so the loop body in indexOfMinimum runs 8 times.
  2. In the second call of indexOfMinimum, it has to look at every value in the subarray from indices 1 to 7, and so the loop body in indexOfMinimum runs 7 times.
  3. In the third call, it looks at the subarray from indices 2 to 7; the loop body runs 6 times.
  4. In the fourth call, it looks at the subarray from indices 3 to 7; the loop body runs 5 times.
  5. …
  6. In the eighth and final call of indexOfMinimum, the loop body runs just 1 time.
If we total up the number of times the loop body of indexOfMinimum runs, we get 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 times.

দ্রষ্টব্য: যোগফল নির্ণয় 1 থেকে n

তুমি কীভাবে 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 এর যোগফল দ্রুত হিসাব করবে? এখানে একটি কৌশল আছে। চল সংখ্যাগুলোকে একটু অন্যভাবে সাজাই। প্রথমে 8 + 1 যোগ করব, বৃহত্তম এবং ক্ষুদ্রতম মান। আমরা পাই 9। তারপর আমরা 7 + 2 যোগ করব, দ্বিতীয় বৃহত্তম এবং ক্ষুদ্রতম মান। ব্যাপারটি মজার, আমরা আবার 9 পাচ্ছি। এখন 6 + 3 যোগ করলে কেমন হয়? আবারও 9। সবশেষে, 5 + 4। এবং আবারও, 9! তাহলে আমরা কি পাচ্ছি?
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=4⋅9=36 .
এখানে চার জোড়া সংখ্যা ছিল যাদের প্রতি জোড়ার যোগফল 9। যে কোন ধারাবাহিক পূর্ণ সংখ্যার ক্রম যোগ করার সাধারণ কৌশলটি হল:
  1. Add the smallest and the largest number.
  2. Multiply by the number of pairs.
যদি ক্রমের পূর্ণসংখ্যাগুলো বিজোড় হয় , যাতে তুমি এদেরকে জোড়ায় জোড়ায় সাজাতে না পার? এটা কোন ব্যাপার না! শুধু ধরা যাক বিজোড় সংখ্যাটি, অর্ধেক জোড়া হিসাবে ক্রমের মাঝখানে আছে। উদাহরণস্বরূপ, 1 + 2 + 3 + 4 + 5 \ যোগ করি। আমাদের দুইটি পূর্ণ জোড়া আছে (1 + 5 এবং 2 + 4, প্রতিটির যোগফল 6 ) এবং একটি "অর্ধেক জোড়া" (3, যা 6 এর অর্ধেক), মোট 2.5 টি জোড়া প্রদান করে। আমরা 2.5⋅6=15 গুণ করি এবং আমরা সঠিক উত্তরটি পাই।
যদি সংখ্যার ক্রমের যোগফল 1 থেকে n পর্যন্ত যায়? আমরা তখন এটিকে একটি গাণিতিক সিরিজ বলি। সর্বনিম্ন এবং বৃহত্তম সংখ্যার যোগফল হল n+1। কারণ এখনে সবমিলিয়ে n সংখ্যক সংখ্যা রয়েছে, সর্বমোট n/2 সংখ্যক জোড়া আছে (যেখানে n জোড় অথবা বিজোড়)। অতএব, 1 থেকে n সংখ্যার সমষ্টি (n+1)(n/2), যা n2/2+n/2 এর সমান। n=5 এবং n=8 এর জন্য এই সূত্রটি চেষ্টা কর।

সিলেকশন সর্টের ক্ষেত্রে অ্যাসিম্পটোটিক চলার সময়ের বিশ্লেষণ

সিলেকশন সর্টের চলার সময়কে তিন ভাগে ভাগ করা যায়ঃ
  1. The running time for all the calls to indexOfMinimum.
  2. The running time for all the calls to swap.
  3. The running time for the rest of the loop in the selectionSort function.
2 এবং 3 নং ধাপ সহজ। আমরা জানি যে n সংখ্যকবার swap কে কল করা হয় এবং প্রত্যেকটি কলের ধ্রুবক সময় লাগে। অ্যাসিম্পটোটিক চিহ্ন ব্যবহার করে, swap কে কল করার সময় হল Θ(n)। সিলেকশন সর্টের লুপের বাকি অংশ হল indexOfMinimum যাচাই করে লুপের চলকের মান বৃদ্ধি করা এবং swap করা, এজন্য আরও Θ(n) সময়ের জন্য ধ্রুবক সময়ে n বার লুপ চলে।
For part 1, the running time for all the calls to indexOfMinimum, we've already done the hard part. Each individual iteration of the loop in indexOfMinimum takes constant time. The number of iterations of this loop is n in the first call, then n−1, then n−2, and so on. We've seen that this sum, 1+2+⋯+(n−1)+n is an arithmetic series, and it evaluates to (n+1)(n/2), or n2/2+n/2. Therefore, the total time for all calls to indexOfMinimum is some constant times n2/2+n/2. In terms of big-Θ notation, we don't care about that constant factor, nor do we care about the factor of 1/2 or the low-order term. The result is that the running time for all the calls to indexOfMinimum is Θ(n2).
Adding up the running times for the three parts, we have Θ(n2) for the calls to indexOfMinimum, Θ(n) for the calls to swap, and Θ(n) for the rest of the loop in selectionSort. The Θ(n2) term is the most significant, and so we say that the running time of selection sort is Θ(n2).
Notice also that no case is particularly good or particularly bad for selection sort. The loop in indexOfMinimum will always make n2/2+n/2 iterations, regardless of the input. Therefore, we can say that selection sort runs in Θ(n2) time in all cases.
দেখা যাক, Θ(n2) এর রান করার সময় কীভাবে কাজ করার সময়কে প্রভাবিত করে। ধরি, সিলেকশন সর্টের আনুমানিক n মানকে বিন্যস্ত করতে n2/106 সেকেন্ড সময় লাগে। n এর ছোট একটি মান নিয়ে শুরু করা যাক, ধরি, n=100। তাহলে সিলেকশন সর্টের রান করার সময় হল 1002/106=1/100 সেকেন্ড। এটি বেশ দ্রুত। কিন্তু যদি n=1000 হয়? তাহলে সিলেকশন সর্টের 10002/106=1 সেকেন্ড সময় লাগে। 10 গুণ হারে অ্যারেটি বৃদ্ধি পাচ্ছে, কিন্তু এটির রান করার সময় সেই অনুপাতে 100 গুণ বৃদ্ধি পাচ্ছে। যদি n=1,000,000 হয়? তাহলে সিলেকশন সর্টের 1,000,0002/106=1,000,000 সেকেন্ড সময় লাগে, যা হল 11.5 দিন। অ্যারের আকার 1000 গুণ বৃদ্ধি করলে এটির রান করার সময় তখন লক্ষ গুণ বৃদ্ধি পায়!
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।

আলোচনায় অংশ নিতে চাও?

প্রবেশ কর
কোন আলাপচারিতা নেই।
ইংরেজি জানো? খান একাডেমির ইংরেজি সাইটে আরো আলোচনা দেখতে এখানে ক্লিক কর।