একটি জাভা সন্নিবেশ বাছাই তালিকার প্রতিটি আইটেম মূল্যায়ন করে। যদি একটি আইটেম আগেরটির থেকে কম হয়, বাছাই আইটেমগুলিকে অদলবদল করে। অন্যথায়, আইটেমগুলি একই জায়গায় থাকে এবং পরবর্তী দুটি আইটেম তালিকায় তুলনা করা হয়৷
৷কম্পিউটার আইটেম তালিকা বাছাই করতে ভাল. লুপ ব্যবহার করে, আপনি একটি তালিকার সমস্ত আইটেম অনুসন্ধান করতে পারেন এবং একটি নির্দিষ্ট উপায়ে প্রদর্শিত না হওয়া পর্যন্ত তাদের ক্রম পরিবর্তন করতে পারেন৷
প্রোগ্রামিং-এ, তালিকা বাছাই করার কয়েকটি আদর্শ পদ্ধতি রয়েছে। আমরা এই সাজানোর অ্যালগরিদম কল. একটি তালিকার সমস্ত আইটেমের মাধ্যমে পড়া অ্যালগরিদমগুলি সাজান এবং নির্দেশের একটি নির্দিষ্ট সেট ব্যবহার করে সাজান৷ সবচেয়ে সাধারণ সাজানোর অ্যালগরিদমগুলির মধ্যে একটি হল একটি সন্নিবেশ বাছাই।
এই নির্দেশিকায়, আমরা কীভাবে জাভা সন্নিবেশ সাজানোর অ্যালগরিদম প্রয়োগ করতে হয় তা নিয়ে আলোচনা করতে যাচ্ছি। আমরা পথ ধরে একটি উদাহরণ দিয়ে হাঁটব যাতে আপনি শিখতে পারেন যে এই সাজানোর পিছনে যুক্তিটি কীভাবে কাজ করে৷
চলুন শুরু করা যাক!
একটি জাভা সন্নিবেশ বাছাই কি?
একটি জাভা সন্নিবেশ বাছাই একটি কার্ড গেমে আপনার হাতে কার্ড সাজানোর অনুরূপ কাজ করে। সন্নিবেশ বাছাই একটি তালিকার প্রতিটি আইটেম পরীক্ষা করে এবং একটি আইটেমের সাথে বাম দিকে অদলবদল করে। একটি আইটেম অদলবদল করা হবে কিনা তা নির্ভর করে আইটেমটি আগের আইটেমের চেয়ে বড় বা কম কিনা।
এক মুহূর্তের জন্য কল্পনা করুন যে আপনি একটি তাস খেলা খেলছেন – হুইস্ট, রামি, যাই হোক না কেন। আপনি যখন আপনার কার্ড বাছাই করছেন, তখন আপনি কী করবেন?
আপনি বাম দিকে শুরু করবেন এবং দ্বিতীয় কার্ডটি সাজানো হয়েছে কিনা তা পরীক্ষা করবেন। যদি সেই কার্ডটি শেষের থেকে বড় হয়, তবে এটি একই অবস্থানে থাকা উচিত। অন্যথায়, এটি তালিকায় একটি অবস্থান উপরে নিয়ে যাওয়া উচিত।
81% অংশগ্রহণকারী বলেছেন যে তারা বুটক্যাম্পে যোগ দেওয়ার পরে তাদের প্রযুক্তিগত কাজের সম্ভাবনা সম্পর্কে আরও আত্মবিশ্বাসী বোধ করেছেন। আজই একটি বুটক্যাম্পের সাথে মিলিত হন৷
৷গড় বুটক্যাম্প গ্র্যাড একটি বুটক্যাম্প শুরু করা থেকে শুরু করে তাদের প্রথম চাকরি খোঁজা পর্যন্ত ক্যারিয়ারের পরিবর্তনে ছয় মাসেরও কম সময় ব্যয় করেছে।
আপনি আপনার হাতে থাকা প্রতিটি কার্ডের মধ্য দিয়ে যাবেন এবং প্রতিটি কার্ড সঠিক ক্রমে প্রদর্শিত না হওয়া পর্যন্ত এই অপারেশনটি সম্পাদন করবেন৷
৷আপনি কখন একটি সন্নিবেশ বাছাই ব্যবহার করবেন?
সন্নিবেশ বাছাইগুলি সবচেয়ে বেশি ব্যবহৃত হয় যখন বাম দিকে কয়েকটি উপাদান থাকে যা সাজানোর প্রয়োজন হয়৷
আরও দক্ষ অ্যালগরিদম রয়েছে যা আপনি ডেটার বড় তালিকা সাজানোর জন্য ব্যবহার করতে পারেন, যেমন মার্জ সাজানোর জন্য। এই কারণেই আপনার সর্বদা একটি সন্নিবেশ বাছাই ব্যবহার করার জন্য ডিফল্ট হওয়া উচিত নয়। এর সাথে বলা হয়েছে, তালিকার উপাদানগুলিকে সাজানোর ক্ষেত্রে বুদবুদ সাজানোর এবং নির্বাচনের সাজানোর চেয়ে সন্নিবেশের প্রকারগুলি আরও কার্যকর৷
একটি সন্নিবেশ বাছাই হল একটি সহজ বাছাই করার অ্যালগরিদম যার অর্থ নতুনদের শেখার জন্য এটি ভাল৷
সন্নিবেশ সাজানোর ওয়াকথ্রু
কার্ডের একটি ডেক ভিজ্যুয়ালাইজ করা বিশ্বের সবচেয়ে স্বজ্ঞাত নয়। আপনাকে শুরু করার জন্য একটি প্রোগ্রামিং উদাহরণের মাধ্যমে চলুন। নিম্নলিখিত তালিকা বিবেচনা করুন:
| 8 | 6 | 3 | 9 |
এই তালিকায়, আমরা ধরে নিই প্রথম উপাদানটি সাজানো হয়েছে।
আমাদের পরবর্তী ধাপ হল আমাদের তালিকার দ্বিতীয় আইটেমটিকে প্রথমটির সাথে তুলনা করা। যদি প্রথম আইটেমটি দ্বিতীয় আইটেমের থেকে বড় হয়, তাহলে সেই আইটেমটি প্রথম আইটেমের সামনে রাখা হয়।
এই ক্ষেত্রে, 6 হল 8 এর থেকে বড়। এর মানে হল 6 আমাদের তালিকায় একটি অবস্থান দ্বারা পিছনে যাবে, এবং 8 একটি অবস্থান দ্বারা এগিয়ে যাবে:
| 6 | 8 | 3 | 9 |
এখন আমাদের তৃতীয় উপাদানটিকে তার বাম দিকের উপাদানগুলির সাথে তুলনা করতে হবে:3 কি 8 থেকে বড়? না, তাই 8 অবস্থান ডানদিকে নিয়ে যায়:
| 6 | 3 | 8 | 9 |
3 কি 6 এর চেয়ে বড়? না, তাই আমরা 6 নম্বর স্থানান্তর করি:
| 3 | 6 | 8 | 9 |
এখন, আমাদের তালিকার চতুর্থ আইটেমটি - শেষ আইটেমটি - আমাদের তালিকার অন্যান্য আইটেমের চেয়ে বড় কিনা তা তুলনা করতে হবে। এই ক্ষেত্রে, 9 এর আগে আসা সমস্ত আইটেমগুলির থেকে বড়:8, 6, এবং 3৷
আমাদের তালিকা সাজানোর জন্য আমরা যে অ্যালগরিদম ব্যবহার করেছি তা এখানে:
- প্রথম উপাদানটি সাজানো হয়েছে।
- দ্বিতীয় আইটেমটির বাম দিকের আইটেমের সাথে তুলনা করুন।
- যদি এই আইটেমটি তার বাম দিকের মানের থেকে বড় হয়, তাহলে আইটেমটি একই জায়গায় থাকবে। অন্যথায়, আমরা মানটিকে বাম দিকে নিয়ে যাই।
- সব আইটেম ক্রমানুসারে না আসা পর্যন্ত পুনরাবৃত্তি করুন।
আমরা এখন একটি সাজানো অ্যারে আছে. সন্নিবেশ বাছাই এক সময়ে একটি আইটেম মাধ্যমে সাজান. চলুন আলোচনা করা যাক কিভাবে জাভাতে এই সাজানোর অ্যালগরিদম প্রয়োগ করা যায়।
কিভাবে জাভাতে একটি সন্নিবেশ বাছাই করতে হয়
তুলনা করা হচ্ছে দুটি মানের সর্বোচ্চ মান প্রতিবার সাজানোর ফাংশন চালানোর সময় ডানদিকে একটি অবস্থান সন্নিবেশ করা হয়।
তাত্ত্বিক পদে এটি সম্পর্কে ভাল কথা বলা হচ্ছে, তবে আপনি কীভাবে এটি জাভাতে প্রয়োগ করবেন? এটা একটা ভালো প্রশ্ন. আসুন একটি ক্লাস লিখি যা শিক্ষার্থীদের গ্রেডের তালিকায় একটি সন্নিবেশ বাছাই করে।
অ্যারে লাইব্রেরি প্রস্তুত করুন
আমাদের জাভা প্রোগ্রামে অ্যারে লাইব্রেরি আমদানি করে শুরু করা যাক। আমরা এই লাইব্রেরিটি ব্যবহার করব আমাদের তালিকাটি একবার সাজানোর পরে কনসোলে মুদ্রণ করতে:
import java.util.Arrays;
একটি সাজানোর পদ্ধতি ঘোষণা করুন
আমরা একটি পদ্ধতি ঘোষণা করে শুরু করব যা আমাদের তালিকার মধ্য দিয়ে যায় এবং আমাদের ডেটাকে আরোহী ক্রমে সাজায় :
class SortGrades {
public static void insertionSort(int [] numbersToSort) {
int itemCount = numbersToSort.length;
for (int value = 1; value < itemCount; value++) {
int key = numbersToSort[value];
int last = value - 1;
while (last >= 0 && key < numbersToSort[last]) {
numbersToSort[last + 1] = numbersToSort[last];
--last;
}
numbersToSort[last + 1] = key;
}
}
}
আমরা আমাদের ইনপুট অ্যারেতে কতগুলি আইটেম খুঁজে বের করে শুরু করি। এটি আমাদের একটি লুপ তৈরি করতে দেয় যা আমাদের তালিকার প্রতিটি আইটেমের মধ্য দিয়ে যায়। আমরা একটি লুপের জন্য আরম্ভ করি যেটি লুপ না হওয়া পর্যন্ত আমরা আমাদের তালিকা সাজাই।
আমাদের ফর লুপের মধ্যে, আমরা দুটি ভেরিয়েবল ঘোষণা করেছি:কী এবং শেষ।
"কী" জাভা ভেরিয়েবল ট্র্যাক করে যে আইটেমটি আমরা বর্তমানে বাছাই করছি। "শেষ" ভেরিয়েবল ট্র্যাক করে আইটেমের বাম দিকে কতগুলি আইটেম সাজাতে হবে৷
যতক্ষণ না আমরা একটি ছোট উপাদান খুঁজে পাই ততক্ষণ আমাদের প্রোগ্রামটি বাম দিকের প্রতিটি উপাদানের সাথে "কী" এর মান তুলনা করবে। এটি আমাদের জাভা "যখন" লুপে ঘটে।
একটি প্রধান ফাংশন সংজ্ঞায়িত করুন
যখন আমরা এই কোডটি চালাই, তখন কিছুই হয় না। কারণ আমরা এখনও আমাদের প্রধান ফাংশন সংজ্ঞায়িত করতে পারিনি। আসুন একটি প্রধান ফাংশন সংজ্ঞায়িত করি যা একটি int অ্যারে (সংখ্যার অ্যারে) সংজ্ঞায়িত করে। এই প্রধান ফাংশনটি insertionSort() ব্যবহার করে ফাংশন আমরা সেই সংখ্যাগুলি সাজানোর ঘোষণা করেছি। আপনার সন্নিবেশ ঘোষণা করার পরে এই কোডটি আটকান জাভা পদ্ধতি সাজান:
public static void main(String args[]) {
int[] numbers = { 8, 6, 3, 9 };
InsertionSort sortNumbers = new InsertionSort();
sortNumbers.insertionSort(numbers);
String arrayToString = Arrays.toString(numbers);
System.out.println("Sorted list: " + arrayToString);
}
আমাদের প্রধান পদ্ধতিতে, আমরা সংখ্যার একটি তালিকা ঘোষণা করেছি যা আমরা সাজাতে চাই। আমরা আমাদের InsertionSort() এর একটি উদাহরণ তৈরি করেছি৷ sortNumbers নামক পদ্ধতি . আমরা আমাদের সংখ্যার তালিকাকে আরোহী ক্রমে সাজাতে এই পদ্ধতিটি ব্যবহার করি। এই পদ্ধতিটি আমাদের "সংখ্যা" অ্যারের মধ্যে মান পরিবর্তন করে; আমরা এর মান সঞ্চয় করার জন্য একটি পৃথক অ্যারে ঘোষণা করিনি।
এরপর, আমরা Arrays.toString() ব্যবহার করেছি আমাদের সংখ্যা অ্যারেকে একটি স্ট্রিংয়ে রূপান্তর করার পদ্ধতি। আমরা কনসোলে সাজানো তালিকা প্রিন্ট আউট করি।
জটিলতা পর্যালোচনা
সন্নিবেশের সাজানোর ক্ষেত্রে O(n^2) এর গড় কেস জটিলতা রয়েছে। এটি ঘটে যখন কোন উপাদানগুলি সাজানো হয় না৷
৷একটি অ্যারে সাজানো হলে সেরা ক্ষেত্রে জটিলতা ঘটে। এটি O(n) এর একটি সময় জটিলতা প্রদান করবে। এর কারণ হল একটি সন্নিবেশ সাজানোর ভিতরের লুপ এই ক্ষেত্রে মোটেও চলবে না৷
৷সবচেয়ে খারাপ ক্ষেত্রে, একটি সন্নিবেশ বাছাই O(n^2) এ সঞ্চালিত হয়। এটি ঘটবে যদি একটি অ্যারে আরোহী বা অবরোহী ক্রমে হয় এবং আপনি এটিকে বিপরীতভাবে সাজাতে চান (অর্থাৎ অবরোহীতে আরোহী)। এটি অন্যান্য সমস্ত উপাদানের সাথে প্রতিটি উপাদানের তুলনা জড়িত।
উপসংহার
সন্নিবেশ বাছাই ডেটা বাছাই করার একটি কার্যকর পদ্ধতি। সন্নিবেশ বাছাই তালিকার দ্বিতীয় দিয়ে শুরু হওয়া মানগুলির তুলনা করে। যদি এই মানটি এটির বাম দিকের মানটির চেয়ে বড় হয় তবে আমাদের তালিকা পরিবর্তন হবে না। অন্যথায়, মানটি সরানো হবে যতক্ষণ না আইটেমটি তার বাম দিকের থেকে কম হয়।
এখন আপনি জাভাতে আপনার নিজের সন্নিবেশ সাজানোর অ্যালগরিদম লেখা শুরু করতে প্রস্তুত! আপনি যদি আরও জাভা শেখার সংস্থান খুঁজছেন, আমাদের কীভাবে জাভা শিখবেন নির্দেশিকা দেখুন।
