বাবল সর্ট এর শরবত

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

যেমনঃ যদি আগের সংখাটি পরের সংখ্যার চেয়ে বড় হয়, তাহলে ঐ দুটি সংখ্যার মধ্যে অবস্থানের পরিবর্তন হবে। ছোট সংখাটি আগে আসবে এবং বড় সংখ্যাটি পরে যাবে। এভাবে প্রক্রিয়াটি একদম লিস্ট বা অ্যারের শেষ পর্যন্ত চলতে থাকবে। প্রক্রিয়াটি একবার সম্পন্ন হলে, সবচেয়ে বড় সংখ্যাটি অ্যারের শেষ স্থানে গিয়ে পৌঁছাবে। দ্বিতীয় বারে দ্বিতীয় বড় সংখাটি অ্যারের সঠিক স্থানে গিয়ে পৌঁছাবে। অর্থাৎ অ্যারেটি শেষ থেকে শুরুর দিকে সর্টেড হতে হতে আসবে। এভাবে প্রতিবার পুনরাবৃত্তিতে একটি করে সংখা সঠিক অবস্থানে গিয়ে পৌঁছাবে। সবগুলা সংখা পুরোপুরি সর্টেড না হওয়া পর্যন্ত এভাবে পুনরাবৃত্তি হতে থাকবে এবং একসময় গিয়ে আমরা আমাদের কাঙ্ক্ষিত সর্টেড লিস্ট পাব।

Pseudo Code (সুডোকোড):

for i = 0 to N – 1

মানে বাইরেরে লুপ N – 1 বার চলবে। প্রতিবার লুপ শেষ হলে সবচেয়ে বড় সংখ্যাটি লিস্টের শেষে বা সঠিক স্থানে চলে যাবে।

for j = 0 to N - i – 2

এটি হচ্ছে ভেতরের লুপ, যা অ্যারের শুরু থেকে শেষ অবধি চলবে যতক্ষন না সবচেয়ে বড় সংখ্যাটি সঠিক স্থানে পৌছায়। এখানে N - i – 2 হবার কারন হচ্ছে, যেহেতু প্রতিবারে লুপের পর বড় সংখাটি সঠিক স্থানে পৌঁছাবে, তাই আমাদের আর শেষ দুটি সংখ্যার মধ্যে তুলনা করার প্রয়োজন নেই।

if Array[j] > Array[j + 1]

যদি j তম পদ বড় হয় j+1 তম পদের চেয়ে, তবে তাদের মধ্যে অবস্থানের পরিবর্তন হবে।

Swap(Array[j], Array[j + 1])

দুটি সংখ্যার অবস্থানের পরিবর্তনের জন্য এই Swap ফাংশনটি ব্যাবহার করা হয়। যা একটি অস্থায়ী ভেরিয়েবল এর সহয়তা নিয়ে থাকে।

Example (উদাহরণ):

ধরি আমাদের কাছে একটি অ্যারে আছেঃ [5, 3, 8, 6, 2]

প্রথমে দুটি সংখ্যা ৫ এবং ৩ এর মধ্যে তুলনা হবে, ৩ ছোট হওয়ার স্থান পরিবর্তন হবে এবং আরেটি দারাবে [3, 5, 8, 6, 2]। এরপর ৫ এবং ৮ এর তুলনা হবে, সঠিক অবস্থানে থাকায় কোনো পরিবর্তন হবে না। এরপর ৮ এবং ৬ এর তুলনা হবে, ৬ ছোট হওয়ায় স্থান পরিবর্তন হয়ে অ্যারেটি দারাবে [3, 5, 6, 8, 2]। এরপর ৮ এবং ২ এর তুলনা হবে, ২ ছোট হওয়ায় স্থান পরিবর্তন হয়ে অ্যারেটি দারাবে [3, 5, 6, 2, 8]। এভাবে প্রথম লুপ শেষে আমরা দেখতে পাব, সবচেয়ে বড় সংখ্যাটি অ্যারের সঠিক স্থানে পৌঁছে গেছে। একইভাবে পরবর্তী লুপ গুলা শেষ হলে আমরা আমাদের কাঙ্ক্ষিত অ্যারেটি [২, 3, 5, 6, 8] পাব।

Time Complexity (সময় জটিলতা):

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

T(n)=(n−1) +(n−2) +(n−3) +...+1 (যা একটি গাণিতিক ধারা)

এই ধারা থেকে আমরা লিখতে পারি,

ð    ………. (১)

আমরা ক্যাল্কুলেশন বার বুঝার সুবিধার্থে সব সময়  এর বড় টার্মটি বিবেচনা করে থাকি। সেই ক্ষেত্রে আমরা  এর দুটি টার্ম থেকে শুধু  নিব এবং বাকি সব ধ্রুব (constant) বাদ দিয়ে দিব। তাহলে আমরা পাই । তাহলে এই -ই হচ্ছে আমাদের টাইম কমপ্লেক্সিটি। যাকে আমরা সাধারাণত O( লিখি।

সর্বোচ্চ ক্ষেত্রে (Worst Case): যদি এমন হয়, অ্যারের সংখাগুলি উল্টভাবে (Descending Order) সাজানো আছে। অর্থাৎ প্রতিটি ধাপে প্রতিটি তুলনা এবং স্থান পরিবর্তন করতে হবে। তখন এর টাইম কমপ্লেক্সিটি হবে O(।

সর্বনিম্ন ক্ষেত্রে (Best Case): যদি এমন হয়, অ্যারের সংখাগুলি ইতিমধ্যেই সাজানো (Ascending Order) আছে। অর্থাৎ শুধু তুলনা হবে, কোনো স্থান পরিবর্তন লাগবে না। তখন এর টাইম কমপ্লেক্সিটি হবে O(n)।

গড় ক্ষেত্রে (Average Case): যদি এমন হয়, সংখাগুলি নরমালি এলোমেলোভাবে আছে। সংখাগুলির তুলনা এবং স্থান পরিবর্তন উভয়ই গড় সংখ্যক বার করতে হবে। তখনও এর টাইম কমপ্লেক্সিটি হবে O(।

অর্থাৎ শুধু সর্বনিম্ন ক্ষেত্রে (Best Case) টাইম কমপ্লেক্সিটি হবে O(n)। আর বাকি সব ক্ষেত্রে O(।)