সিলেকশন সর্ট(Selection sort) অ্যালগরিদম

কোনো উপাদান বাঁ ডাটাসমূহকে একটি নির্দিষ্ট ক্রমে সাজানোর প্রক্রিয়াই হলো সর্টিং(Sorting) । সর্টিং(Sorting) আমরা দুই ভাবে করতে পারি -

১। Ascending Order এবং

২। Descending Order

১। Ascending Order :-

ছোট থেকে বড় ক্রমে সাজানোর প্রক্রিয়াকে বলা হয় Ascending Order । যেমন :-

শ্রেণিকক্ষের হাজিরা খাতায় শিক্ষার্থীদের নামগুলো রোল নম্বর অনুযায়ী সাজানো থাকে ।

এছাড়াও লক্ষ্য করলে দেখবেন বিভিন্ন স্কুল-কলেজে ফিজিক্যাল এক্সারসাইজ করার সময় শিক্ষার্থীদেরকে ছোট থেকে বড় ক্রমে লাইনে দাড় করে রাখা হয়

২। Descending Order :-

বড় থেকে ছোট ক্রমে সাজানোর প্রক্রিয়াকে বলা হয় Descending Order । যেমন :-

ফাইনাল পরীক্ষা শেষে রেজাল্ট শিটে শিক্ষার্থীদের নামগুলো মোট নম্বর অনুযায়ী বড় থেকে ছোট ক্রমে সাজানো থাকে ।

আসল কথায় আসা যাক, প্রোগ্রামিং করার সময় বিভিন্ন কাজে ডাটাসমূহকে এরকম সর্ট করার প্রয়োজন হয় । তখন আমরা খুব সহজেই বিভিন্ন সর্টিং অ্যালগরিদম ব্যাবহার করে ডাটাসমূকে সর্ট করে ফেলতে পারি । কম্পিউটার সায়েন্সে অনেক ধরণের সর্টিং অ্যালগরিদম আছে তারমধ্যে সহজ এবং জনপ্রিয় একটি সর্টিং অ্যালগরিদম হলো সিলেকশন সর্ট(Selection sort) ।

সিলেকশন সর্ট(Selection sort) :-

এই সর্টিং অ্যালগরিদমের মূল বিষয় হলো, প্রতি ইটারেশনে ডাটাসমূহ থেকে একটি সঠিক উপাদানকে সিলেক্ট করা এবং তাকে অন্য আরেকটি উপাদানের সাথে অদল-বদল করে(যদি প্রয়োজন হয়) সঠিক জায়গায় এসাইন করা ।

ধরি, আমাদের কাছে [100,400,300,600,500] এই অ্যারেটি আছে । এখন এই অ্যারেটিকে সিলেকশন সর্ট(Selection sort) অ্যালগরিদম ব্যাবহার করে Descending Order অর্থাৎ বড় থেকে ছোট ক্রমে সাজাতে হবে।

স্টেপ(১) :- প্রথমে উপরোক্ত অ্যারে থেকে সবচেয়ে বড় সংখ্যাটিকে সিলেক্ট করি এক্ষেত্রে 600 হচ্ছে সবচেয়ে বড় সংখ্যা । এখন 600 কে সবার প্রথমে নিয়ে আসতে হবে এজন্য অ্যারের প্রথম উপাদান 100 এর সঙ্গে 600 এর স্থান অদল-বদল করি । অদল-বদল শেষে আমাদের অ্যারেটি দাঁড়াবে এরকম -

[600,400,300,100,500]

স্টেপ(২) :- এখন অ্যারের দিকে লক্ষ করলে দেখতে পারবো যে, অ্যারের প্রথম উপাদানটি সবচেয়ে বড় । তাই প্রথম উপাদান বাদে অ্যারের বাকি উপাদানগুলোর মধ্যে সবচেয়ে বড় সংখ্যাটি সিলেক্ট করি এক্ষেত্রে সংখ্যাটি হচ্ছে 500 । এরপর 400 এর সাথে 500 এর স্থান অদল-বদল করি তাহলে অ্যারেটি দাঁড়াবে -

[600,500,300,100,400]

স্টেপ(৩) :- অ্যারের প্রথম দুটি উপাদান সর্ট করা শেষ এখন বাকি তিনটি(300,100,400) উপাদান সর্ট করতে হবে । তাহলে এই তিনটি উপাদানের মধ্যে সবচেয়ে বড় সংখ্যাটি সিলেক্ট করি সংখ্যাটি হলো 400 । এরপর 300 এর সাথে 400 এর স্থান অদল-বদল করি এখন অ্যারেটি হবে -

[600,500,400,100,300]

স্টেপ(৪) :- এখন আমরা নিশ্চিত যে, অ্যারের প্রথম ৩টি উপাদান সর্টেড রয়েছে তাহলে বাকি ২টি(100,300) উপাদান থেকে সবচেয়ে বড় সংখ্যাটি সিলেক্ট করি এক্ষেত্রে সংখ্যাটি হচ্ছে 300 । এখন 100 এর সাথে 300 এর স্থান অদল-বদল করি । অদল-বদল শেষে অ্যারেটি হবে -

[600,500,400,300,100]

যেহেতু, অ্যারের ৫টি উপাদানের মধ্যে প্রথম ৪টি উপাদান বড় থেকে ছোট ক্রমে সাজানো । সেক্ষেত্রে আমরা নিশ্চিত যে, অ্যারের শেষ উপাদান অর্থাৎ 100 তার সঠিক জায়গাতেই আছে এর কোনো অদল-বদল করতে হবে নাহ । তাহলে আমাদের ফাইনাল অর্থাৎ সর্টেড অ্যারেটি হলো -

[600,500,400,300,100]

আশা করি, আপনারা সিলেকশন সর্ট(Selection sort) অ্যালগরিদমটি বুঝতে পেরেছেন যদি একবারে বুঝে না থাকেন তাহলে আরেকবার পড়তে হবে । চলুন এখন ইমপ্লিমেন্টেশন বাঁ কোড লিখা যাক -

পাইথনে ইমপ্লিমেন্টেশন :-

def selectionSort(arr):
    # i এর মান  0 থেকে len(arr) - 1 এর আগ পর্যন্ত ১ করে বাড়াই
    for i in range(len(arr) - 1):
        # largest নামে variable নিই এবং i এসাইন করি
        largest = i

        # j এর মান i+1 থেকে len(arr) এর পর্যন্ত ১ করে বাড়াই
        for j in range(i+1, len(arr)):

          # arr[largest] < arr[j] যদি সত্য হয় তাহলে largest এসাইন করি
            if arr[largest] < arr[j]:
                largest = j

        # যদি largest এবং i সমান না হয় তাহলে সংখ্যা দুইটি অদল-বদল করি
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
    return arr

জাভাস্ক্রিপ্টে ইমপ্লিমেন্টেশন :-

const selectionSort = (arr) => {
  // i এর মান  0 থেকে arr.length - 1 এর আগ পর্যন্ত ১ করে বাড়াই
  for (let i = 0; i < arr.length - 1; i++) {
    // largest নামে variable নিই এবং i এসাইন করি
    let largest = i;
    // j এর মান i+1 থেকে arr.length এর পর্যন্ত ১ করে বাড়াই
    for (let j = i + 1; j < arr.length; j++) {

      // arr[largest] < arr[j] যদি true হয় তাহলে largest এ j এসাইন করি

      if (arr[largest] < arr[j]) {
        largest = j;
      }
    }

    // যদি largest এবং i সমান না হয় তাহলে সংখ্যা দুইটি অদল-বদল করি
    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
    }
  }
  return arr;
};

যেকোনো অ্যালগরিদম বাঁ ডাটা-স্ট্রাকচারের মূল কনসেপ্ট যদি আপনি ভালোভাবে বুঝতে পারেন তাহলে যেকোনো প্রোগ্রামিং ল্যাঙ্গুয়েজ ব্যাবহার করেই ইমপ্লিমেন্ট করতে পারবেন ।

চলুন সিলেকশন সর্ট(Selection sort) অ্যালগরিদমের টাইম ও স্পেস কমপ্লেক্সিটি নিয়ে একটু অ্যানালাইসিস করা যাক -

টাইম কমপ্লেক্সিটি(Time Complexity) :

উপরোক্ত কোড লক্ষ করলে দেখবো প্রথম লুপটি চলে i = 0 থেকে n-1 পর্যন্ত । এবং ভেতরের অর্থাৎ ২য় লুপটি চলে j = i+1 থেকে n-1 পর্যন্ত ।

যখন i = 0, তখন ভেতরের লুপটি চলে j = 0 থেকে j = n - 1 অর্থাৎ 4 বার ।

আবার i = 1 হলে, ভেতরের লুপটি চলে j = 1 থেকে j = n - 1 অর্থাৎ 3 বার ।

i = 2 হলে, ভেতরের লুপটি চলে j = 2 থেকে j = n - 1 অর্থাৎ 2 বার । এভাবেই যতক্ষণ না লুপটি শেষ হয় চলতেই থাকবে ।

একটু লক্ষ করলে দেখতে পারবো যে, প্রথম লুপটি n সংখ্যক বার চললে তার ভেতরের লুপটি চলতেছে m সংখ্যক বার । তাহলে টাইম কমপ্লেক্সিটি(Time Complexity) দাঁড়াবে O(n * m) । এখানে যেহেতু m এর মান n এর সমান তাহলে টাইম কমপ্লেক্সিটি(Time Complexity) বলতে পারি O(n * n) বা O(n²) ।

স্পেস কমপ্লেক্সিটি(Space Complexity) :

উপরের প্রোগ্রামে একটু খেয়াল করলে দেখতে পারবো যে, প্রোগ্রামে একটি লিস্ট বা অ্যারে প্যারামিটার হিসেবে নেওয়া হয়েছে । এবং যা কাজ-কারবার করা হয়েছে তা এই অ্যারে বা লিস্টের মধ্যেই । এই অ্যারে বা লিস্টে কিন্তু কোনো নতুন উপাদান সংযোজন, বিয়োজন ইত্যাদি কিছুই করা হয় নাই । তাহলে বলতে পারি অ্যারে বা লিস্টটি Constant । এখন আপনার কাছে আমার প্রশ্ন এই প্রোগ্রামের স্পেস কমপ্লেক্সিটি(Space Complexity) কত ?

আশা করি পেরেছেন হ্যাঁ স্পেস কমপ্লেক্সিটি(Space Complexity) হচ্ছে - O(1) ।

ব্রাভো, যদি এতদূর পর্যন্ত আপনি ঠিকঠাক ভাবে পড়ে থাকেন তাহলে আমি ধরে নিতেই পারি সিলেকশন সর্ট(Selection sort) সম্পর্কে ভালো একটা দখল চলে আসছে ।

যদি সত্যি বুঝে থাকেন তাহলে একটি কাজ করতে পারেন, উপরোক্ত অ্যারেটিকে আমি কিন্তু Descending Order অর্থাৎ বড় থেকে ছোট ক্রমে সাজিয়েছি এখন আপনি সিলেকশন সর্ট(Selection sort) অ্যালগরিদম ব্যাবহার করে অ্যারেটিকে Ascending Order অর্থাৎ ছোট থেকে বড় ক্রমে সাজানোর চেষ্টা করবেন ।

খুবই সহজ একটি কাজ আশা করি পারবেন শুভকামনা রইলো 🥰।