বাবল সর্ট (Bubble Sort)

Aug 17, 2013

সর্টিং এলগোরিদমগুলোর মধ্যে সম্ভবত সবচেয়ে সহজ এবং ছোট এলগোরিদমটি হল বাবল সর্ট। এটি বোঝা অত্যন্ত সহজ এবং এর কোডিং অংশটিও অন্যান্য সর্টিং এলগোরিদমের তুলনায় খুবই ছোট এবং সহজ।

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

এনিমেশনের মাধ্যমে দেখা যাচ্ছে, আমরা প্রথমে ১ নাম্বার এলিমেন্টটি নিচ্ছি। এরপর সেটির সাথে ৮ নাম্বার এলিমেন্ট থেকে শুরু করে ২ নাম্বার পর্যন্ত সবগুলো এলিমেন্টের তুলনা করছি। প্রতিবার তুলনা করার সময় যদি আমরা দেখি যে ১ নাম্বার এলিমেন্টে যে সংখ্যাটি আছে সেটি অপর সংখ্যাটি থেকে বড় তাহলে তাদের মধ্যে স্থান বিনিময় করে দিচ্ছি। এতে করে আস্তে আস্তে ছোট এলিমেন্টটি ১ নাম্বার স্থানে চলে আসছে এবং যখন আমরা ৮ নাম্বার থেকে শুরু করে ২ নাম্বার এলিমেন্ট পর্যন্ত প্রতিটির সাথে ১ নাম্বার এলিমেন্টটির তুলনা শেষ করব তখন ১ থেকে ৮ এর মধ্যে অবস্থিত সবচেয়ে ছোট এলিমেন্টটি ১ নাম্বার অবস্থানে চলে আসবে।

তাহলে ১ নাম্বার পজিশনে যার থাকার কথা সে চলে আসলো। এখন আমরা ২ নাম্বারটি নিয়ে আবার একই কাজ করব। ৮ নাম্বার হতে ৩ নাম্বার পর্যন্ত সবগুলো এলিমেন্টের সাথে ২ নাম্বার এলিমেন্টের তুলনা করা হয়ে গেলে ২ থেকে ৮ এর মধ্যে অবস্থিত সবচেয়ে ছোট নাম্বারটি এখন ২ নাম্বার অবস্থানে চলে আসবে। এভাবে সবগুলো এলিমেন্ট নিয়ে তুলনা করে করে স্থান বিনিময় করতে থাকলে সব শেষে আমাদের নাম্বারগুলো সর্টেড হয়ে যাবে। আমরা যদি এই কাজটিকে কোডে রূপান্তর করি তাহলে এরকম হবেঃ

int array[ELEMENTS];
// ELEMENTS হল মোট এলিমেন্ট সংখ্যা
for( int i = 0; i < ELEMENTS - 1; i++ ) {
  for( int j = ELEMENTS - 1; j > i; j-- ) {
    if( array[i] > array[j] ) { // C++ এ <algorithm> হেডার ফাইলের
      int temp = array[i];      // অন্তর্ভুক্ত swap() ফাংশন ব্যবহার করে
      array[i] = array[j];      // সহজেই কাজটি করা যায় এভাবে
      array[j] = temp;          // swap( array[i], array[j] );
    }
  }
}

এখানে i এর মাধ্যমে আমরা বামদিক থেকে একটি করে এলিমেন্ট নিচ্ছি এবং ভিতরের লুপের j এর মাধ্যমে আমরা i এর পরে অবস্থিত প্রতিটি এলিমেন্ট নিয়ে i এ অবস্থিত এলিমেন্টটির সাথে তুলনা করে প্রয়োজন অনুযায়ী swap করে দিচ্ছি। সমগ্র প্রক্রিয়াটি শেষ হলে অ্যারেটি ছোট থেকে বড় হিসেবে সর্টেড হয়ে যাবে। যদি বড় থেকে ছোট করতে চাই তাহলে if( array[i] > array[j] ) এর স্থানে if( array[i] < array[j] ) করে দিলেই হয়ে যাবে। কিভাবে করে সর্টেড হয়ে গেল সেটি যদি এখনও বুঝতে অসুবিধা থাকে লেখাটি আরেকবার পড়তে অনুরোধ করব। এছাড়া নিজের মত করে একটি অ্যারে বানিয়ে কাগজে কলমে ছবি এঁকে সমগ্র প্রক্রিয়াটি চালিয়ে দেখলেও আশা করি পরিষ্কার হয়ে যাবে।

বাবল সর্ট সর্টিং এলগোরিদমগুলোর মধ্যে অত্যন্ত সহজ একটি এলগোরিদম হলেও এর এফিসিয়েন্সি ভালো নয়। এভারেজ কেসে এর কমপ্লেক্সিটি O(n^2)। ফলে এলিমেন্ট সংখ্যা তুলনামূলকভাবে কম হলে এটি নিয়ে কাজ করা গেলেও যখন এলিমেন্ট সংখ্যা অনেক হয়ে যায় তখন এলগোরিদমটি অনেকটাই অকার্যকর হয়ে পড়ে।

প্র্যাকটিস প্রবলেমঃ
১। UVa 299 - Train Swapping
২। UVa 10327 - Flip Sort
৩। UVa 11850 - Alaska