পাইথন সিলেকশন সোর্ট: একটি পূর্ণাঙ্গ গাইড

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

সিলেকশন সোর্ট কী এবং কেন এটি গুরুত্বপূর্ণ?

তালিকা সাজানো প্রোগ্রামিং-এ একটি অত্যন্ত সাধারণ অপারেশন। চিন্তা করুন একটি শিক্ষক যিনি তার শিক্ষার্থীদের اخیرের পরীক্ষার ফলাফল বিশ্লেষণ করতে চান। শিক্ষকটি নম্বরগুলোকে আরোহী বা অবরোহী ক্রমে সাজাতে পারেন, যাতে সর্বোচ্চ এবং সর্বনিম্ন নম্বর সহজে খুঁজে পাওয়া যায়। সিলেকশন সোর্ট হল এমন একটি অ্যালগরিদম যা একটি তালিকাকে আরোহী বা অবরোহী ক্রমে সাজাতে সাহায্য করে।

পাইথন সিলেকশন সোর্ট কী?

পাইথন সিলেকশন সোর্ট বারবার একটি তালিকায় ন্যূনতম উপাদান খুঁজে বের করে এবং সেটিকে তালিকার একটি নির্দিষ্ট শেষে সরিয়ে দেয়। এই প্রক্রিয়া তালিকাটি পূর্ণভাবে সাজানো পর্যন্ত চলতে থাকে। আপনি সর্বাধিক উপাদান খুঁজে বের করার নির্দেশও দিতে পারেন। উভয় পদ্ধতিই তালিকা সাজায়।

সিলেকশন সোর্ট ধরে নেয় যে তালিকার প্রথম উপাদানটি সবচেয়ে ছোট মান। এরপর সেটি দ্বিতীয় উপাদানের সাথে তুলনা করে। যদি দ্বিতীয় উপাদানটি ন্যূনতম মানের চেয়ে ছোট হয়, তবে সেটিই নতুন ন্যূনতম মান হয়ে যায়। এই প্রক্রিয়া তালিকার শেষ উপাদান পর্যন্ত পুনরাবৃত্তি হয়। একবার শেষ উপাদান পর্যন্ত পৌঁছালে, ন্যূনতম মানটি অসাজানো তালিকার শুরুতে রাখা হয়।

পাইথন সিলেকশন সোর্টের ধাপে ধাপে উদাহরণ

সিলেকশন সোর্ট বোঝার সবচেয়ে ভালো উপায় হল একটি উদাহরণের মাধ্যমে চলে যাওয়া। আসুন শিক্ষার্থীদের নম্বরের একটি তালিকাকে আরোহী ক্রমে সাজাই। ধরে নিই আমাদের অসাজানো তালিকা হলো:

আমরা তালিকার প্রথম মানকে ন্যূনতম বলে ধরব। সিলেকশন সোর্টের প্রতিটি পুনরাবৃত্তি সবচেয়ে ছোট উপাদানটি খুঁজে বের করবে এবং সেটিকে সাজানো সাব-অ্যারেতে সরিয়ে দেবে।

ন্যূনতম উপাদান সাজানো একটি বিকল্প। আপনি সর্বাধিক উপাদান দিয়েও সিলেকশন সোর্ট করতে পারেন। কিন্তু এই উদাহরণে আমরা ন্যূনতম উপাদান ব্যবহার করছি।

এখন আমরা ন্যূনতম মানটি দ্বিতীয় উপাদানের সাথে তুলনা করব। যদি এই উপাদানটি ন্যূনতমের চেয়ে ছোট হয়, তবে দ্বিতীয় উপাদানটি নতুন ন্যূনতম মান হয়ে যাবে।

আমরা ৭৩ এবং ৬২ কে তুলনা করছি। ৭৩, ৬২ এর চেয়ে বড়, তাই নতুন ন্যূনতম মান হলো ৬২। এখন আমরা তালিকার বাকি সব সংখ্যার সাথে তুলনা করব:

৬১ কি ৬২ (আমাদের ন্যূনতম মান) এর চেয়ে বড়? না, তাই সেটিকে সোয়াপ করুন। ন্যূনতম হয়ে যায় ৬১।
৬৯ কি ৬১ (আমাদের ন্যূনতম মান) এর চেয়ে বড়? হ্যাঁ, তাই কিছুই করবেন না। ন্যূনতম ৬১-এই থাকে।

তালিকাটি এখনও একই দেখাচ্ছে:

তালিকার শেষে পৌঁছালে, আপনি ন্যূনতম মানটি তালিকার শুরুতে সরিয়ে আনতে পারেন:

৬১ (আমাদের ন্যূনতম মান) তালিকার শুরুতে স্থানান্তরিত হয়েছে, এবং বাকি সব মান এক ধাপ উপরে চলে এসেছে। আমরা এই প্রক্রিয়াটি সব উপাদান সাজানো পর্যন্ত পুনরাবৃত্তি করব।

আমাদের তালিকার প্রতিটি পুনরাবৃত্তি নিচের ফলাফলগুলো দেবে:

73, 62, 61, 69
61, 73, 62, 69
61, 62, 73, 69
61, 62, 69, 73

যখন সিলেকশন সোর্ট তালিকার সব উপাদান যাচাই করে নেয়, সেটি বন্ধ হয়ে যায়। সাজানো সাব-অ্যারে এবং অসাজানো সাব-অ্যারে উভয়ই আমাদের কাছে অদৃশ্য থাকে। আমাদের অ্যালগরিদম আমাদের জন্য অ্যারেটি সাজিয়ে দেয় এবং অসাজানো অংশটিকে ট্র্যাক করে রাখে।

পাইথনে সিলেকশন সোর্ট কীভাবে বাস্তবায়ন করবেন

এখন আপনি থিওরি জানেন: অভিনন্দন! এখন বাস্তব চ্যালেঞ্জ। আমরা পাইথনে সিলেকশন সোর্ট অ্যালগরিদমটি বাস্তবায়ন করব। একটি প্রোগ্রাম লিখব যা একটি পাইথন অ্যারে নেবে এবং সেটিকে আরোহী ক্রমে সাজাবে।

সোর্ট ফাংশন সংজ্ঞায়িত করুন

আমরা একটি পাইথন ফাংশন সংজ্ঞায়িত করব যা আমাদের সিলেকশন সোর্ট সম্পাদন করবে:

def sortList(array):
    length = len(array)
    for item in range(length):
        minimum = item
        for i in range(item + 1, length):
            if array[i] < array[minimum]:
                minimum = i
        (array[item], array[minimum]) = (array[minimum], array[item])

আমরা পাইথনের len() মেথড ব্যবহার করে তালিকার দৈর্ঘ্য বের করেছি। এরপর এই দৈর্ঘ্য ব্যবহার করে একটি for লুপ চালিয়েছি যা তালিকার প্রতিটি আইটেমের ওপর পুনরাবৃত্তি করে।

লুপের প্রতিটি পুনরাবৃত্তিতে, আমরা minimum এর মানকে তালিকার প্রথম আইটেম হিসেবে সেট করি। একবার ন্যূনতম মান সেট হলে, আরেকটি for লুপ শুরু হয় যা তালিকার প্রতিটি আইটেমের মধ্য দিয়ে যায়।

তালিকার প্রতিটি আইটেমের জন্য, আমাদের অ্যালগরিদম চেক করে যে ন্যূনতম মানটি কি ঐ আইটেমের চেয়ে বড়। যদি হয়, তবে কিছুই হয় না; অন্যথায়, ন্যূনতম মানটি প্রোগ্রাম যা পড়ছে সেটি হয়ে যায়।

তালিকার সব আইটেমের মধ্য দিয়ে লুপ করার পরে, আমাদের অ্যালগরিদম ন্যূনতম মানকে তালিকার শুরুতে সরিয়ে দেয়। এরপর প্রোগ্রামটি তালিকার দৈর্ঘ্যের সমান সংখ্যকবার চলে যাবে।

সোর্টিং ফাংশন কল করুন

আপনি লক্ষ্য করতে পারেন যে প্রোগ্রামটি চালালে কিছুই হয় না। কারণ আমরা এখনো কী মানগুলো ব্যবহার করব তা বলিনি। আপনার প্রোগ্রামের নিচে, sortList ফাংশনের বাইরে নিচের কোডটি যোগ করুন:

numbers = [73, 62, 61, 69]
sortList(numbers)
print("Sorted list:", numbers)

প্রোগ্রামটি চালালে নিচের আউটপুটটি ফেরত দেবে:

[61, 62, 69, 73]

আমাদের তালিকা সাজানোর হয়ে গেছে। নিজের পিঠে একটু ধাপ দিন; আপনি করলেন!

সিলেকশন সোর্ট ব্যবহার করে একটি তালিকাকে অবরোহী ক্রমেও সাজানো যায়। যদি আপনি এইভাবে সাজাতে চান, তবে সিলেকশন সোর্টের if স্টেটমেন্টটি নিচের মতো পরিবর্তন করুন:

if array[i] > array[minimum]:

আমরা কম দানের চিহ্নটি বড় দানের চিহ্নে পরিবর্তন করেছি। এটি তালিকাটিকে অবরোহী ক্রমে সাজাবে, কারণ ন্যূনতম মানটি তালিকার সর্বোচ্চ মানে সেট হবে। تکنিক্যালি বলতে আমাদের ন্যূনতম মানটি একটি সর্বাধিক মানে পরিণত হয়ে যায়।

সিলেকশন সোর্ট কখন ব্যবহার করা উচিত?

বাবল সোর্টের মতো সিলেকশন সোর্ট ছোট তালিকাগুলোর জন্য সেরা। কারণ বড় তালিকাগুলোর ক্ষেত্রে এটি অন্যান্য অ্যালগরিদম (যেমন ইন্সারশন সোর্ট) চেয়ে কম দক্ষ।

সিলেকশন সোর্ট সাজানোর অ্যালগরিদম শিখতে শুরু করার সময় শেখার জন্য একটি চমৎকার অ্যালগরিদম। অন্যান্য সোর্টগুলো মास্টার করা কঠিন হতে পারে, কিন্তু সিলেকশন সোর্ট ভালোভাবে বুঝলে আপনি বিভিন্ন ধরনের তালিকা এবং সাজানোর কৌশল বুঝতে পারবেন।

সিলেকশন সোর্টের কমপ্লেক্সিটি (Complexity) কী?

সিলেকশন সোর্টের টাইম কমপ্লেক্সিটি হলো O(n²)। এর মানে হলো অ্যালগরিদমের কমপ্লেক্সিটি তালিকায় কতগুলো উপাদান আছে তার উপর নির্ভর করে এক্সপোনেনশিয়ালি বৃদ্ধি পাবে।

O(n²) এই অ্যালগরিদমের সবচেয়ে খারাপ ক্ষেত্র (worst-case), গড় ক্ষেত্র (average-case), এবং সবচেয়ে ভালো ক্ষেত্র (best-case) — সবকেসের কমপ্লেক্সিটি। সাজানোর কমপ্লেক্সিটি সম্পর্কে আরও জানতে আমাদের Big O Notation গাইডটি দেখুন।

উপসংহার

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

শিক্ষার বাইরে সিলেকশন সোর্ট বহুল ব্যবহৃত হয় না কারণ আরও দক্ষ অ্যালগরিদম রয়েছে। তবুও, এটি অন্যান্য সোর্ট (যেমন ইন্সারশন বা মার্জ সোর্ট) শিখতে একটি ভালো ঝাঁপি।

পাইথন সম্পর্কে আরও জানতে আগ্রহী? আমাদের সম্পূর্ণ How to Learn Python গাইডটি পড়ুন যা আপনার জ্ঞান বাড়াতে এক্সপার্ট পরামর্শ দেবে।