জাভা সিলেকশন সোর্ট: সম্পূর্ণ গাইড

জাভা সিলেকশন সোর্ট একটি লিস্ট থেকে সবচেয়ে ছোট আইটেম খুঁজে বের করে সেটিকে লিস্টের শুরুতে নিয়ে আসে। এই প্রক্রিয়া প্রতিটি এলিমেন্ট সর্টেড হওয়া পর্যন্ত বারবার চলে। সিলেকশন সোর্ট সর্টেড লিস্ট রিটার্ন করে।

জাভাতে লিস্ট কীভাবে সর্ট করবেন? আপনার কাছে কয়েকটি অপশন আছে। একটি সাধারণ অপশন হলো সিলেকশন সোর্ট।

এই গাইডে আমরা আলোচনা করব সিলেকশন সোর্ট কী, কীভাবে কাজ করে, এবং জাভাতে সিলেকশন সোর্ট কীভাবে বিল্ড করবেন যাতে আপনি নিজেরাও বানাতে পারেন।

জাভা সিলেকশন সোর্ট কী?

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

লিস্টের প্রথম আইটেমকে sementara সবচেয়ে ছোট ধরা হয়। এই আইটেমটি পরবর্তী এলিমেন্টের সাথে তুলনা করা হয়। যদি পরবর্তী এলিমেন্ট ছোট হয়, তবে তাদের স্থান বদলানো হয়। এই অ্যালগরিদম লাস্ট এলিমেন্ট পাওয়া পর্যন্ত মিনিমাম এলিমেন্ট খুঁজে বের করে। তারপর প্রোগ্রাম সবচেয়ে ছোট আইটেমটি লিস্টের শুরুতে সরিয়ে দেয়।

সিলেকশন সোর্টে একটি লিস্টের দুটি অংশ থাকে: সর্টেড লিস্ট এবং আনসর্টেড লিস্ট। এলিমেন্টগুলো সর্টেড হয়ে যাওয়ার সাথে সাথে আনসর্টেড সাব-অ্যারে থেকে সর্টেড সাব-অ্যারেতে চলে আসে।

আপনি লিস্টকে অ্যাসেন্ডিং বা ডিসেন্ডিং অর্ডারে সাজাতে পারেন।

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

সিলেকশন সোর্ট ছোট লিস্ট সর্ট করার জন্য আপ্টিমাল। কারণ বড় লিস্ট সর্ট করার আরও দক্ষ উপায় আছে। মার্জ সোর্ট, ইনসারশন সোর্ট, কুইক সোর্টের মতো অ্যালগরিদম জাভা প্রোগ্রামিং-এ সিলেকশন সোর্ট চেয়ে বেশি দক্ষ।

সিলেকশন সোর্ট তখন সেরা পারফর্ম করে যখন অ্যারে-এর সকল এলিমেন্ট চেক করা বাধ্যতামূলক হয়। এটি হয় যদি লিস্টের খুব কম বা কোনো আইটেম সর্টেড না থাকে। সিলেকশন সোর্ট সাধারণত বাবল সোর্ট চেয়ে ভালো পারফর্ম করে, যদিও বাবল সোর্ট বোঝা সহজ।

সিলেকশন সোর্ট কীভাবে কাজ করে?

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

নিচের আনসর্টেড অ্যারে বিবেচনা করুন:

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

"minimum" আইটেমটি দ্বিতীয় এলিমেন্টের সাথে তুলনা করা হয়। এই এলিমেন্টটি আনসর্টেড অংশে আছে; সর্টেড এলিমেন্টগুলোর পরের সব এলিমেন্ট আনসর্টেড।

যদি দ্বিতীয় এলিমেন্ট "minimum" আইটেম চেয়ে ছোট হয়, তবে "minimum" এর ভ্যালু দ্বিতীয় আইটেমের ভ্যালু হয়ে যায়। 14, 17 চেয়ে ছোট, তাই নতুন মিনিমাম ভ্যালু 14।

এই প্রক্রিয়া লিস্টের প্রতিটি আইটেমের জন্য повтор হয়। 9, 14 চেয়ে ছোট। তাই "minimum" হয়ে যায় 9। 9, 12 চেয়ে ছোট নয়, তাই মিনিমাম ভ্যালু একই থাকে।

এক ইটারেশনের পর লিস্টে 9 সবচেয়ে ছোট সংখ্যা বলে পাওয়া গেল। এই আইটেমটি লিস্টের শুরুতে সরানো হয়:

এই প্রক্রিয়া আবার প্রথম আনসর্টেড এলিমেন্ট থেকে শুরু হয়। পরবর্তী কম্প্যারিজন 17 থেকে শুরু হবে:

• 17 মিনিমামের সমান।
• প্রোগ্রাম 17 কে 14 দিয়ে কম্প্যার করে। "minimum" হয়ে যায় 14।
• প্রোগ্রাম 14 কে 12 দিয়ে কম্প্যার করে। "minimum" হয়ে যায় 12।
• প্রোগ্রাম 12 কে লিস্টের সর্টেড আইটেমগুলোর শেষে সরিয়ে দেয়।

লিস্ট এখন এই রকম দেখাবে:

এই প্রক্রিয়া লিস্ট সাজানো পর্যন্ত চলবে। অ্যালগরিদম শেষ হলে নিচের লিস্ট রিটার্ন হবে:

লিস্ট অ্যাসেন্ডিং অর্ডারে সর্টেড হয়েছে।

জাভাতে সিলেকশন সোর্ট কীভাবে বিল্ড করবেন

সিলেকশন সোর্ট কীভাবে কাজ করে জানা এক回事, আবার এটি বিল্ড করা অন্য একটি বিষয়। চলুন জাভাতে সিলেকশন সোর্ট কোড করি যেটি উপরের লজিক ব্যবহার করে।

প্রোগ্রাম সেট আপ করুন

selection_sort.java নামে একটি ফাইল তৈরি করুন। প্রথমে জাভা অ্যারে লাইব্রেরি ইম্পোর্ট করুন:

import java.util.Arrays;

এই লাইব্রেরি পরে কোডে ব্যবহার করব সর্টেড অ্যারেকে স্ট্রিং-এ কনভার্ট করে কনসোলে প্রিন্ট করার জন্য।

সর্ট ফাংশন তৈরি করুন

এখন একটি ক্লাস ডিক্লেয়ার করুন এবং একটি মেথড তৈরি করুন যা সিলেকশন সোর্ট পারফর্ম করবে। আপনার selection_sort.java ফাইলে নিচের কোড যোগ করুন:

class SelectionSort { 
    void sortNumbers(int array[]) { 
        int size = array.length; 
        for (int item = 0; item < size - 1; item++) { 
            int minimum = item; 
            for (int number = minimum + 1; number < size; number++) { 
                if (array[number] < array[minimum]) { 
                    minimum = number; 
                } 
            } 
            int temporary = array[item]; 
            array[item] = array[minimum]; 
            array[minimum] = temporary; 
        } 
    } 
} 

এই ক্লাসে sortNumbers নামে একটি মেথড ডিফাইন করা হয়েছে যা সর্ট পারফর্ম করে। প্রথমে অ্যারে-এর দৈর্ঘ্য ক্যালকুলেট করা হয়। একটি জাভা ভেরিয়েবলে অ্যারে-এর দৈর্ঘ্য স্টোর করা হয়।

তারপর একটি জাভা ফর লুপ তৈরি করা হয়। এই লুপ লিস্টের প্রতিটি আইটেমের মধ্য দিয়ে ইটারেট করে। এই ফর লুপের ভিতরে মিনিমাম আইটেম খুঁজে বের করা হয়, যা লিস্টের প্রথম আইটেম।

তারপর একটি অন্য ফর লুপ শুরু করা হয় মিনিমাম আইটেমকে লিস্টের প্রতিটি আইটেমের সাথে কম্প্যার করার জন্য।

যদি ফর লুপ পড়া সংখ্যাটি মিনিমাম সংখ্যা চেয়ে ছোট হয়, তবে "minimum" এর ভ্যালু সেই সংখ্যাটি হয়ে যায়। আমাদের লুপে "number" রিপ্রেজেন্ট করে যে সংখ্যার ইনডেক্স ভ্যালুটিকে আমরা মিনিমাম ভ্যালুর সাথে কম্প্যার করছি।

মিনিমাম সংখ্যা লিস্টের সকল সংখ্যার সাথে কম্প্যার হয়ে গেলে ইনার ফর লুপ থামে। মিনিমাম সংখ্যাটি লিস্টের সকল সর্টেড সংখ্যার পরে সরানো হয়।

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

আমাদের কোড এখনও কিছু করছে না। আমরা এখনও আমাদের ক্লাস কল করিনি এবং সর্ট করার জন্য লিস্ট দিয়েনি।

sortNumbers মেথডের নিচে নিচের কোড যোগ করুন:

public static void main(String args[]) { 
    int[] toSort = { 17, 14, 9, 12 }; 
    SelectionSort newSort = new SelectionSort(); 
    newSort.sortNumbers(toSort); 
    System.out.println(Arrays.toString(toSort)); 
} 

আমাদের মেইন মেথডে toSort নামে সর্ট করার জন্য একটি লিস্ট ডিক্লেয়ার করা হয়েছে। তারপর আমাদের SelectionSort ক্লাসের একটি ইনস্ট্যান্স newSort নামে ইনিশিয়ালাইজ করা হয়েছে। এটি ব্যবহার করে আমাদের sortNumbers মেথড কল করা হয়েছে, যা toSort অ্যারে-এর ভ্যালুগুলো সর্ট করে।

sortNumbers মেথড এক্সিকিউট হলে, আমরা সর্টেড অ্যারেকে কনসোলে প্রিন্ট করি। এজন্য Arrays.toString() মেথড ব্যবহার করা হয়েছে, যা আমাদের অ্যারেকে স্ট্রিংয়ের লিস্টে কনভার্ট করে।

কোড রান করলে আউটপুট:

[9, 12, 14, 17]

আমাদের লিস্ট সর্টেড হয়েছে!

সিলেকশন সোর্ট জাভা: ডিসেন্ডিং অর্ডারে ভ্যালু সর্ট করুন

আপনি ডিসেন্ডিং অর্ডারে ভ্যালু সর্ট করতে পারেন। এর জন্য আপনার sortNumbers মেথডের নিচের লাইনটি রিপ্লেস করুন:

if (array[number] < array[minimum]) {

এটি দিয়ে:

if (array[number] > array[minimum]) {

এই কোড চেক করে "minimum" ভ্যালুটি ফর লুপ দ্বারা অ্যাক্সেস করা ভ্যালু চেয়ে বড় কিনা। এর মানে "minimum" এর ভ্যালু লিস্টের হাইএস্ট ভ্যালু রিফ্লেক্ট করবে, লোয়েস্ট না।

বিভ্রান্তি এড়াতে, ডিসেন্ডিং অর্ডারে সর্ট করলে "minimum" কে "maximum" নাম দিতে পারেন।

আপনি সফল হয়েছেন। আপনি সিলেকশন সোর্টিং অ্যালগরিদম ব্যবহার করে জাভাতে একটি লিস্ট সর্ট করেছেন।

জাভা সিলেকশন সোর্টের কমপ্লেক্সিটি কী?

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

সিলেকশন সোর্টের বেস্ট, অ্যভারেজ, ও ওয়ার্স্ট কেস কমপ্লেক্সিটি O(n^2)। এর মানে লিস্টে আইটেমের সংখ্যা বড় হলে অ্যালগরিদম এক্সপোনেনশিয়ালি বেশি সময় নেবে।

অ্যালগরিদম কমপ্লেক্সিটি নিয়ে বিভ্রান্ত? আমাদের বিগ ও নোটেশন সম্পর্কে দু-পর্বের সিরিজ দেখুন। এই নোটেশনটি অ্যালগরিদম কমপ্লেক্সিটি বর্ণনা করতে ব্যবহৃত হয়।

উপসংহার

সিলেকশন সোর্ট ডেটা লিস্ট সর্ট করার একটি দক্ষ পদ্ধতি। এটি আনসর্টেড লিস্ট থেকে সবচেয়ে ছোট আইটেম সিলেক্ট করে সেটিকে আনসর্টেড লিস্টের শুরুতে সরিয়ে দেয়। এই প্রক্রিয়া লিস্ট সর্টেড হওয়া পর্যন্ত পুনরাবৃত্তি হয়।

আপনি কি জাভা ডেভেলপার হতে চান? আমাদের "How to Learn Java" গাইড দেখুন। সেখানে টপ লার্নিং টিপস এবং সেরা অনলাইন কোর্স ও লার্নিং রিসোর্স সম্পর্কে পরামর্শ পাবেন।