জাভা বাবল সোর্ট কীভাবে লিখবেন
প্রোগ্রামাররা বাবল সোর্ট বলতে যা বোঝায় সেটি আপনি যেসব পানির বাবল ফুঁকে বের করেছেন সেটি নয়। এখানে একটি সর্টিং অ্যালগরিদমের কথা বলা হচ্ছে যা আইটেমের একটি তালিকা ক্রমানুসারে সাজাতে ব্যবহৃত হয়।
এই গাইডে আমরা বাবল সোর্ট কী, কীভাবে কাজ করে, এবং জাভা-তে কীভাবে ইমপ্লিমেন্ট করবেন তা আলোচনা করব। এই অ্যালগরিদম কোডে কীভাবে অনুবাদ হয় সেটি বুঝতে আমরা জাভা-তে একটি বাবল সোর্ট ইমপ্লিমেন্ট করব। চলুন জাভা বাবল সোর্টে ডুব মেরে যাই!
জাভা বাবল সোর্ট কী?
একটি বাবল সোর্ট হলো একটি অ্যালগরিদম যা সংলগ্ন এলিমেন্টগুলো তুলনা করে এবং যদি সেগুলো ভুল ক্রমে থাকে তবে সেগুলো স্ব্যাপ করে মানগুলো সাজায়।
এই প্রক্রিয়া তখন까지 চলতে থাকে যতক্ষণ না তালিকার প্রতিটি আইটেম সঠিক ক্রমে সাজায়। বাবল সোর্ট ব্যবহার করে তালিকা অ্যাসেন্ডিং বা ডেসেন্ডিং অর্ডারে সাজানো যায়।
বাবল সোর্ট হলো অ্যালগরিদম ক্লাসে শেখানো প্রথম সোর্ট। কারণ এটি অন্যান্য সোর্ট (যেমন ইনসারশন সোর্ট বা সিলেকশন সোর্ট) চেয়ে সহজে বোঝা যায় এবং সর্টিং অ্যালগরিদমের একটি ভালো পরিচয় দেয়।
বাবল সোর্ট তখন সবচেয়ে কার্যকর হয় যখন ডেটা প্রায়ই সর্টেড অবস্থায় থাকে। কিন্তু যদি আপনার ডেটা সম্পূর্ণ অসর্টেড থাকে, তবে অন্য কোনো সোর্ট বেশি দক্ষ হতে পারে।
বাবল সোর্ট কীভাবে কাজ করে?
জাভা বাবল সোর্টের কোড লেখার আগে আমাদের প্রথমে বুঝতে হবে এই অ্যালগরিদম প্র্যাক্টিক্যালি কীভাবে ইমপ্লিমেন্ট হয়।
নিচের তালিকা বিবেচনা করুন:
| 5 | 9 | 2 | 7 |
আমাদের বাবল সোর্ট তালিকার প্রথম এবং দ্বিতীয় এলিমেন্ট তুলনা করে শুরু করে।
যদি প্রথম এলিমেন্ট দ্বিতীয় এলিমেন্ট চেয়ে বড় হয়, তবে এগুলো অবস্থান বদলাবে। এই কেসে ৫, ৯ চেয়ে বড় নয়, তাই এগুলো একই জায়গায় থাকবে।
তারপর সোর্ট তালিকার পরের দুটি আইটেম তুলনা করবে। ৯, ২ চেয়ে বড়, তাই এই দুটি নম্বর স্ব্যাপ হবে:
| 5 | 2 | 9 | 7 |
এই প্রক্রিয়া তালিকার প্রতিটি আইটেম তুলনা হওয়া পর্যন্ত চলবে। এই কেসে একটু আরও তুলনা বাকি: ৯ কি ৭ চেয়ে বড়? ৯, ৭ চেয়ে বড়, তাই এগুলো স্ব্যাপ হবে:
| 5 | 2 | 7 | 9 |
আমাদের তালিকা প্রায় সাজায় গেছে। একবার সব আইটেম তুলনা হলে, বাবল সোর্ট আবার শুরু থেকে শুরু করবে যতক্ষণ না সব এলিমেন্ট সর্ট হয়।
৫, ২ চেয়ে বড়, তাই এগুলো স্ব্যাপ হবে।
| 2 | 5 | 7 | 9 |
এখন আমাদের তালিকা সঠিক ক্রমে সাজায় গেছে। বাবল সোর্ট নম্বরগুলো তুলনা করতে থাকবে যতক্ষণ না তালিকার শেষে পৌঁছায়, এবং তারপর থামবে। এটিই হলো বাবল সোর্ট। একবার বুঝতে পারলে এটি ব্যবহার করা খুব সহজ।
জাভা বাবল সোর্ট কীভাবে লিখবেন
তেওরি জানা এক回事 কিন্তু আপনি এখানে জাভা বাবল সোর্ট শিখতে এসেছেন। আমরা জাভা-তে বাবল সোর্ট ইমপ্লিমেন্ট করার পদ্ধতি আলোচনা করব।
বাবল সোর্ট দুই ধরনের:
- স্ট্যান্ডার্ড বাবল সোর্ট
- অপ্টিমাইজড বাবল সোর্ট
স্ট্যান্ডার্ড বাবল সোর্ট সব সম্ভাব্য তুলনা করে এমনকি যদি অ্যারে সর্টেড থাকে। এটি বাবল সোর্ট এক্সিকিউট হওয়ার সময় বাড়ায়, ফলে সোর্ট কম দক্ষ হয়।
অপ্টিমাইজড বাবল সোর্ট একটি অতিরিক্ত ভেরিয়েবল ব্যবহার করে তালিকা সর্টেড কিনা তা ট্র্যাক করে। এটি আমাদের সোর্টটি তালিকা সর্টেড হয়ে যাওয়ার সাথে সাথে বন্ধ করার সুবিধা দেয়।
প্রথমে স্ট্যান্ডার্ড বাবল সোর্ট লিখি।
স্ট্যান্ডার্ড বাবল সোর্ট
শুরুতে আমরা আমাদের কোডে Arrays লাইব্রেরি ইম্পোর্ট করব। এটি পরে সর্টেড নম্বরের তালিকা কনসোলে প্রিন্ট করতে ব্যবহার করব:
import java.util.Arrays;এখন আমরা আমাদের অ্যালগরিদম লিখতে শুরু করি।
একটি BubbleSort ক্লাস ডিফাইন করব যা আমাদের জাভা প্রোগ্রামের কোড ধারণ করবে, এবং একটি ফাংশন যা সর্টিং করবে:
class BubbleSort {
void sortNumbers(int array[]) {
int size = array.length;
for (int item = 0; item < size - 1; item++) {
for (int j = 0; j < size - item - 1; j++) {
if (array[j] > array[j + 1]) {
int temporary = array[j];
array[j] = array[j + 1];
array[j + 1] = temporary;
}
}
}
}
}আমরা sortNumbers নামে একটি ফাংশন ঘোষণা করেছি যা একটি ভেরিয়েবল প্যারামিটার হিসেবে গ্রহণ করে। এই ফাংশন আমাদের নির্দিষ্ট নম্বর তালিকার সাইজ ক্যালকুলেট করে শুরু করে।
এটি ক্যালকুলেট হয়ে গেলে একটি for লুপ আরম্ভ হয়। এই লুপ আমাদের অ্যারেতে প্রতিটি আইটেমের মধ্য দিয়ে যায়। আমরা আরেকটি for লুপ আরম্ভ করি যা আমাদের অ্যারেতে প্রতিটি আইটেম তুলনা করতে দেয়।
যদি তালিকার বাম পাশের আইটেম ডান পাশের নম্বর চেয়ে বড় হয়, তবে মানগুলো স্ব্যাপ হবে। অন্যথায় কিছুই হবে না।
এই স্ব্যাপ আমরা বাম পাশের মানকে "temporary" নামে একটি ভেরিয়েবলে অ্যাসাইন করে করি। তারপর তুলনার ডান পাশের মানের মান বাম পাশের মান দিয়ে আপডেট করি। তারপর বাম পাশের মানকে temporary ভেরিয়েবলের মান দিয়ে আপডেট করি।
যদি ৬ এবং ৫ তুলনা করা হত, তবে এগুলো স্ব্যাপ হত। তাহলে আমাদের তালিকা দেখাত: ৫, ৬।
আমাদের প্রোগ্রাম এখনো কিছুই করছে না। আমরা এখনো মেইন প্রোগ্রাম লিখিনি যা আমাদের ফাংশনকে কল করবে এবং সর্ট করার জন্য একটি তালিকা দেবে।
sortNumbers ফাংশনের নিচে নিচের কোড যোগ করুন:
public static void main(String args[]) {
int[] toSort = { 5, 9, 2, 7 };
BubbleSort sortingAlgorithm = new BubbleSort();
sortingAlgorithm.sortNumbers(toSort);
System.out.println(Arrays.toString(toSort));
}আমরা toSort নামে একটি ভেরিয়েবল ঘোষণা করেছি যেটি আমাদের সর্ট করতে চাই সেই মানগুলো ধারণ করে। তারপর BubbleSort ক্লাসের একটি ইনস্ট্যান্স তৈরি করেছি sortingAlgorithm নামে, যা পরবর্তী লাইনে sortNumbers ফাংশন কল করতে ব্যবহৃত হয়েছে। এই ফাংশন কল হলে আমাদের তালিকা সর্ট হয়।
শেষে, আমরা Arrays.toString() মেথড ব্যবহার করে আমাদের তালিকাকে স্ট্রিংয়ে রূপান্তর করি যাতে কনসোলে প্রিন্ট করতে পারি। আমাদের কোড ফেরত দেবে:
[2, 5, 7, 9]এখন আমাদের কাছে একটি সর্টেড অ্যারে রয়েছে!
অপ্টিমাইজড বাবল সোর্ট
আমাদের কোড আরও দক্ষ করা যায়। এখন আমাদের সর্ট সব সম্ভাব্য তুলনা করতে থাকে এমনকি যদি অ্যারে সর্টেড থাকে। এর মানে সর্টেড হওয়ার পরও সেটি তুলনা চালিয়ে রাখবে।
এই আচরণ রোধ করতে আমরা আমাদের কোডে একটি নতুন ভেরিয়েবল যোগ করতে পারি। এটি আমাদের সোর্ট বন্ধ করতে দেবে যদি তালিকা সর্টেড হয়ে যায়। এই ভেরিয়েবল আমাদের আগের sortNumbers ফাংশনে যোগ করি:
class BubbleSort {
void sortNumbers(int array[]) {
int size = array.length;
for (int item = 0; item < size - 1; item++) {
boolean hasSwapped = false;
for (int j = 0; j < size - item - 1; j++) {
if (array[j] > array[j + 1]) {
int temporary = array[j];
array[j] = array[j + 1];
array[j + 1] = temporary;
hasSwapped = true;
}
}
if (hasSwapped == false) {
break;
}
}
}
}আমরা আমাদের কোডে তিনটি পরিবর্তন আনলাম। প্রথম for লুপের ভেতরে আমরা hasSwapped নামে একটি ভেরিয়েবল ঘোষণা করেছি। এই ভেরিয়েবল ট্র্যাক করে কোনো স্ব্যাপ হয়েছে কিনা। ডিফল্টভাবে এটি false সেট করা থাকে। যদি কোনো স্ব্যাপ হয়, তবে এই ভেরিয়েবলের মান true হবে।
আমাদের for লুপের শেষে আমরা একটি if স্টেটমেন্ট যোগ করেছি চেক করার জন্য hasSwapped কি false এর সমান। যদি কোনো স্ব্যাপ না হয়, মানে অ্যারে সর্টেড। আমরা break কিওয়ার্ড ব্যবহার করি লুপ বন্ধ করার জন্য যদি hasSwapped false এর সমান হয়।
আগের মেইন প্রোগ্রাম ব্যবহার করে কোড চালালে:
[2, 5, 7, 9]আমাদের তালিকা সর্টেড হয়েছে, কিন্তু এইবার আমাদের অ্যালগরিদম আরও দক্ষ। বড় তালিকা ব্যবহার করলে এই অ্যালগরিদমের সुपീരিয়র পারফরম্যান্স স্পষ্ট হবে। এটিই, আপনি জাভা-তে একটি অপ্টিমাইজড বাবল সোর্ট লিখে ফেলেছেন!
উপসংহার
বাবল সোর্ট তালিকা অ্যাসেন্ডিং বা ডেসেন্ডিং অর্ডারে সাজাতে ব্যবহৃত হয়। এটি সংলগ্ন মানগুলো তুলনা করে এবং যদি সেগুলো ভুল ক্রমে থাকে তবে সেগুলো স্ব্যাপ করে কাজ করে।
বাবল সোর্ট দুই ধরনের: স্ট্যান্ডার্ড এবং অপ্টিমাইজড। স্ট্যান্ডার্ড বাবল সোর্ট প্রিডিফাইন্ড সংখ্যক স্ব্যাপ করে,অপ্টিমাইজড বাবল সোর্ট শুধু তালিকা সর্টেড হওয়া পর্যন্ত সর্ট করে।
এখন আপনি জাভা-তে বাবল সোর্ট এক্সপার্টের মতো লিখতে পারবেন!
