বুদবুদ বাছাই জাভা

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

কি বাছাই করা হয়

প্রথমত, আপনাকে বুঝতে হবে সাধারণভাবে সাজানো কী এবং জাভা প্রোগ্রামে আমরা কী সাজাতে পারি। যদি আমরা দুই বা ততোধিক উপাদান বা বস্তুকে তাদের যেকোন বৈশিষ্ট্যের সাথে তুলনা করতে পারি, তাহলে এর মানে হল যে তারা এই বৈশিষ্ট্য দ্বারা সাজানো যেতে পারে। উদাহরণস্বরূপ, ঊর্ধ্বমুখী বা অবরোহ ক্রমে সংখ্যা বা বর্ণানুক্রমিক শব্দ। অতএব, উপাদানগুলি একে অপরের সাথে তুলনীয় হতে হবে। উপায় দ্বারা, উপাদান কি? জাভাতে, আমরা সংগ্রহের উপাদানগুলির তুলনা করতে পারি। উদাহরণস্বরূপ আমরা পূর্ণসংখ্যা, স্ট্রিং ইত্যাদির অ্যারে বা অ্যারেলিস্ট সাজাতে পারি।

কিভাবে বুদ্বুদ সাজানোর কাজ করে

ধরা যাক, আমাদের পূর্ণসংখ্যার একটি অ্যারেকে আরোহী ক্রমে সাজাতে হবে, অর্থাৎ ছোট থেকে বড় সংখ্যা পর্যন্ত। প্রথমত, আমরা পুরো অ্যারে বরাবর যাচ্ছি এবং প্রতি 2টি প্রতিবেশী উপাদানের তুলনা করছি। যদি তারা ভুল ক্রমে থাকে (বাম প্রতিবেশী ডানের চেয়ে বড়), আমরা তাদের অদলবদল করি। শেষে প্রথম পাসে এটি সবচেয়ে বড় উপাদান দেখাবে (যদি আমরা আরোহী ক্রমে সাজাই)। আপনি বলতে পারেন, সবচেয়ে বড় উপাদান "পপ আপ"। যে বাবল বাছাই অ্যালগরিদম নাম কারণ. আমরা প্রথম থেকে পরবর্তী থেকে শেষ উপাদান পর্যন্ত প্রথম ধাপটি পুনরাবৃত্তি করি। আমরা পরের থেকে শেষ স্থানে দ্বিতীয় বৃহত্তম উপাদান পেয়েছি। ইত্যাদি। পূর্ববর্তী ধাপে অন্তত একটি বিনিময় করা হয়েছে কিনা তা পরীক্ষা করে আমরা একটি অ্যালগরিদমকে কিছুটা উন্নত করতে পারি। এটা না হলে আমরা অ্যারে বরাবর আমাদের চলমান বন্ধ.

বুদবুদ সাজানোর উদাহরণ

আসুন পূর্ণসংখ্যার অ্যারে সাজান, একটি, আপনি নীচে একটি ছবিতে দেখতে পারেন। ধাপ 1: আমরা অ্যারের মাধ্যমে যাচ্ছি। অ্যালগরিদম প্রথম দুটি উপাদান (সূচক 0 এবং 1 সহ), 8 এবং 7 দিয়ে শুরু হয় এবং তারা সঠিক ক্রমে আছে কিনা তা পরীক্ষা করে। স্পষ্টতই, 8 > 7, তাই আমরা তাদের অদলবদল করি। এর পরে, আমরা দ্বিতীয় এবং তৃতীয় উপাদানগুলির দিকে তাকাই (সূচক 1 এবং 2), এখন এইগুলি 8 এবং 1। একই কারণে, আমরা তাদের অদলবদল করি। তৃতীয়বারের জন্য আমরা 8 এবং 2 এবং কমপক্ষে 8 এবং 5 তুলনা করি। আমরা মোট চারটি এক্সচেঞ্জ করেছি: (8, 7), (8, 1), (8, 2) এবং (8, 5)। 8 এর একটি মান, এই অ্যারের মধ্যে সবচেয়ে বড়, তালিকার শেষে সঠিক অবস্থানে পপ আপ হয়েছে। বুদবুদ সাজানোর অ্যালগরিদম কাজ করার প্রথম ধাপের ফলাফল হল পরবর্তী অ্যারে: ধাপ 2. (7,1), (7,2) এবং (7,5) এর সাথে একই কাজ করা। 7 এখন অন্তিম অবস্থানে আছে, এবং আমাদের এটিকে তালিকার "লেজ" এর সাথে তুলনা করার দরকার নেই, এটি ইতিমধ্যেই সাজানো হয়েছে। বুদ্বুদ সাজানোর অ্যালগরিদম কাজ করার দ্বিতীয় ধাপের ফলাফল হল পরবর্তী অ্যারে: আপনি দেখতে পাচ্ছেন, এই অ্যারেটি ইতিমধ্যেই সাজানো হয়েছে। যাইহোক বাবল সাজানোর অ্যালগরিদম অন্তত আরও একবার যেতে হবে। ধাপ 3. আমরা আরো একবার অ্যারের মাধ্যমে যাচ্ছে. এখানে অদলবদল করার কিছু নেই, তাই আমরা যদি "উন্নত" বুদ্বুদ সাজানোর অ্যালগরিদম ব্যবহার করি (আগের ধাপে অন্তত একটি বিনিময় করা হয়েছে কিনা তা পরীক্ষা করে) এই ধাপটি শেষ।

বুদ্বুদ বাছাই জাভা কোড

বুদবুদ সাজানোর জাভা উপলব্ধি

বুদ্বুদ সাজানোর জন্য দুটি পদ্ধতি তৈরি করা যাক। প্রথমটি, bubbleSort(int[] myArray) একটি সমতল। এটি প্রতিবার অ্যারের মাধ্যমে সঞ্চালিত হয়। দ্বিতীয়টি, অপ্টিমাইজড বাবলসোর্ট(int myArray[]) অ্যালগরিদম বন্ধ করে অপ্টিমাইজ করা হয় যদি ভিতরের লুপ কোন অদলবদল না করে। কাউন্টার আপনাকে দেখায় যে বাছাই করার সময় আপনি কতগুলি পদক্ষেপ করেছিলেন৷ এখানে আমরা বুদ্বুদ সাজানোর জাভা উপলব্ধি পেয়েছি:

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array  
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

বুদবুদ সাজানোর জাভা অ্যালগরিদম কাজের ফলাফল:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

বুদ্বুদ সাজানোর কতটা দক্ষ?

বুদবুদ বাছাই বাস্তবায়নের জন্য সবচেয়ে সহজ অ্যালগরিদমগুলির মধ্যে একটি কিন্তু এটি কার্যকর নয়। এটি নেস্টেড লুপ একটি জোড়া প্রয়োজন. এমনকি সবচেয়ে খারাপ ক্ষেত্রে অ্যালগরিদমের একটি অপ্টিমাইজ করা সংস্করণেও (ডেটা সেটের প্রতিটি উপাদান পছন্দসই একের বিপরীতে থাকে) ডেটা সেটের প্রতিটি n উপাদানের জন্য বাইরের লুপ একবার পুনরাবৃত্তি করে। অভ্যন্তরীণ লুপটি প্রথমবারের জন্য n বার পুনরাবৃত্তি করে, দ্বিতীয়টির জন্য ( n-1 ) এবং আরও অনেক কিছু। সুতরাং, সমস্ত n , উপাদানগুলিকে সাজানোর জন্য , লুপগুলিকে n*(n-1)/2 বার সম্পাদন করতে হবে। এটিকে O(n ² ) বলেসময়ের জটিলতা এবং মানে অ্যালগরিদম একটি অ্যারের 1000টি উপাদানের জন্য প্রায় 500 000 তুলনা করে। যাইহোক, বুদ্বুদ সাজানোর অ্যালগরিদম মেমরি ব্যবহারের ক্ষেত্রে বেশ কার্যকর (মেমরির জটিলতা হল O(n) ) এবং প্রায় বাছাই করা ছোট ডেটাসেটের জন্য সত্যিই ভাল।