বাবল সর্ট (Bubble sort) হলো একটি সোর্টিং অ্যালগরिदম যা একটি লিস্টকে আরোহী (ascending) বা অবরোহী (descending) ক্রমে সর্ট করে। এটি সবচেয়ে সহজ সোর্টিং অ্যালগরিদম কিন্তু খুব দক্ষ নয়। এটি ছোট ইনপুট সাইজে ব্যবহার করা যায় কিন্তু বড় দৈর্ঘ্যের লিস্ট বা অ্যারেতে টাইম-এফিশিয়েন্ট নয়। এর টাইম কমপ্লেক্সিটি O(n²)। যাইহোক, এটি একটি ইন-প্লেস (in-place) সোর্টিং অ্যালগরিদম, অর্থাৎ এটি কোনো এক্সট্রা স্পেস ব্যবহার করে না। তাই স্পেস কমপ্লেক্সিটি দৃষ্টিতে এটি দক্ষ। কিন্তু এটি বেশি ব্যবহার হয় না কারণ বাবল সর্ট চেয়ে ভালো সোর্টিং অ্যালগরিদম আছে।
বাবল সর্ট কীভাবে কাজ করে?
বাবল সর্টে দুটি ফর লুপ ব্যবহার করা হয়। আউটার ফর লুপ লিস্টের ওপর ইটারেট করে। ইনার ফর লুপ আউটার লুপের সব ইটারেশনের জন্য লিস্টের ওপর ইটারেট করে।
বাবল সর্টের মূল অপারেশন হলো দুটি সংলগ্ন (consecutive) এলিমেন্ট তুলনা করা। যদি প্রথম এলিমেন্ট পরের এলিমেন্টের চেয়ে বড় হয়, তবে দুটিকে সওয়্যাপ (swap) করা হয় যাতে ছোট এলিমেন্ট আগে আসে এবং বড় এলিমেন্ট পিছে যায়। আউটার লুপের এক ইটারেশনে লিস্টের সর্বোচ্চ এলিমেন্ট লাস্ট ইনডেক্সে চলে যায়। আউটার লুপের দ্বিতীয় ইটারেশনে লিস্টের দ্বিতীয় সর্বোচ্চ এলিমেন্ট সেকেন্ড লাস্ট ইনডেক্সে চলে যায় এবং এভাবে চলে। সুতরাং সব ইটারেশন শেষে আমরা সর্ট করা লিস্ট পাই।
এটি একটি উদাহরণ দিয়ে ভালোভাবে বুঝা যাবে।
উদাহরণ
নিচের লিস্টটি সর্ট করতে হবে।
| 5 | 2 | 1 | 3 | 4 |
Outer loop = 1
| 5 | 2 | 1 | 3 | 4 |
5 > 2, তাই দুটো সওয়্যাপ
| 2 | 5 | 1 | 3 | 4 |
5 > 1, তাই দুটো সওয়্যাপ
| 2 | 1 | 5 | 3 | 4 |
5 > 3, তাই দুটো সওয়্যাপ
| 2 | 1 | 3 | 5 | 4 |
5 > 4, তাই দুটো সওয়্যাপ
| 2 | 1 | 3 | 5 | 4 |
(সর্বোচ্চ এলিমেন্ট ৫ প্রথম আউটার ইটারেশন után লাস্ট ইনডেক্সে পৌঁছেছে)
Outer loop = 2
| 2 | 1 | 3 | 5 | 4 |
2 > 1, তাই সওয়্যাপ
| 1 | 2 | 3 | 5 | 4 |
সওয়্যাপ দরকার নেই
| 1 | 2 | 3 | 4 | 5 |
সওয়্যাপ দরকার নেই
| 1 | 2 | 3 | 4 | 5 |
যে 모습을 보이고 있습니다, ২য় আউটার ইটারেশনে লিস্টটি সর্ট হয়ে গেছে। কিন্তু আউটার লুপ ৩ বার আর ইটারেট করবে কোনো ফर्दার সওয়্যাপ ছাড়া। তাই শুধু ২ ইটারেশন উদাহরণে দেখানো হয়েছে। কখনও লিস্ট প্রথম ইটারেশনে সর্ট হয়ে যেতে পারে। কখনও লিস্ট লাস্ট ইটারেশনে সর্ট হতে পারে। তাই আউটার লুপ সবসময় n বার ইটারেট করবে।
উদাহরণ
def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr)-1):
if arr[j] > arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
return arr
array = [2, 3, 1, 5, 4]
print(bubble_sort(array))
আউটপুট
[1, 2, 3, 4, 5]
