পাইথনে বুদ্বুদ সাজানো কি? উদাহরণ দিয়ে ব্যাখ্যা কর?

বাবল সর্ট হল একটি তালিকাকে আরোহী (বা অবরোহ) ক্রমে সাজানোর জন্য একটি সাজানোর অ্যালগরিদম। এটি সবচেয়ে সহজ বাছাই অ্যালগরিদম কিন্তু এটি খুব দক্ষ নয়। এটি ছোট ইনপুট আকারে ব্যবহার করা যেতে পারে তবে বৃহত্তর দৈর্ঘ্যের তালিকা বা অ্যারের জন্য সময় দক্ষ নয়। এর সময় জটিলতা হল O(n^2)। যাইহোক, এটি একটি ইন-প্লেস বাছাই অ্যালগরিদম, যার মানে এটি কোনও অতিরিক্ত স্থান ব্যবহার করে না। এইভাবে, স্থান জটিলতার পরিপ্রেক্ষিতে এটি দক্ষ। যাইহোক, এটি খুব বেশি ব্যবহার করা হয় না কারণ বুদ্বুদ সাজানোর চেয়ে ভাল সাজানোর অ্যালগরিদম রয়েছে৷

বাবল সাজানোর কাজ কিভাবে?

বুদ্বুদ সাজানোর মধ্যে, লুপের জন্য দুটি ব্যবহার করা হয়। লুপের জন্য বাইরের তালিকার উপর পুনরাবৃত্তি হয়। লুপের জন্য অভ্যন্তরীণটি সমস্ত বাইরের লুপের পুনরাবৃত্তির জন্য তালিকার উপরেও পুনরাবৃত্তি করে৷

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

আমরা একটি উদাহরণের সাহায্যে আরও ভালভাবে বুঝতে পারি।

উদাহরণ

আমাদের নিম্নলিখিত তালিকাটি সাজাতে হবে৷

Outer loop=1

5>2, তাই উভয় অদলবদল করুন

5>1, তাই উভয় অদলবদল করুন

5>3, তাই উভয় অদলবদল করুন

5>4, তাই উভয় অদলবদল করুন

(প্রথম বাইরের পুনরাবৃত্তির পরে সবচেয়ে বড় উপাদান 5 শেষ সূচকে পৌঁছেছে)

Outer loop=2

2>1, তাই অদলবদল করুন

কোন অদলবদল প্রয়োজন নেই

কোন অদলবদল প্রয়োজন নেই

আমরা দেখতে পাচ্ছি যে তালিকাটি ২য় বাইরের পুনরাবৃত্তিতে সাজানো হয়েছে। কিন্তু বাইরের লুপ আর কোন সোয়াপ অপারেশন ছাড়াই আরও 3 বার পুনরাবৃত্তি করবে। সুতরাং, উদাহরণে শুধুমাত্র 2টি পুনরাবৃত্তি দেখানো হয়েছে। কখনও কখনও, তালিকাটি প্রথম পুনরাবৃত্তিতেই সাজানো যেতে পারে। কখনও কখনও, তালিকাটি শেষ পুনরাবৃত্তিতে সাজানো হতে পারে। এইভাবে, বাইরের লুপ সবসময় n বার পুনরাবৃত্তি করবে।

উদাহরণ

def bubble_sort(arr):জন্য i in range(len(arr)):j এর জন্য রেঞ্জে(len(arr)-1):if(arr[j]>arr[j+1]):temp=আরআর 
আউটপুট
 
[1, 2, 3, 4, 5]