Merge Sort
Merge Sort ডিভাইড-এন্ড-কনকার (divide-and-conquer) টাইপ সর্টিং অ্যালগরিদমের একটি উদাহরণ। Merge Sort-এর ইনপুট হলো কিছু এলিমেন্টের একটি অ্যারে, যেগুলো সাধারণত ছোট থেকে বড় ক্রমে সাজাতে হয়।
Merge Sort-এ অনুসরণ করতে হয় এমন ধাপগুলো
- Merge Sort অ্যারেকে দুটি সাব-অ্যারেতে ভাগ করে, তারপর প্রতিটি অ্যারে আবার দুটি করে ভাগ করে, এভাবে চলতে থাকে যতক্ষণ না একক এলিমেন্টের অ্যারেগুলো বাকি থাকে। উদাহরণস্বরূপ, [4,7,5,9,1,3,8,2] অ্যারে একক এলিমেন্টের অ্যারে [4], [7], [5], [9], [1], [3], [8], [2]-এ ভাগ হয়।
- এটি অ্যারেগুলো তুলনা করে জোড়া করে কনক্যাটেনেট করে শুরু করে। উদাহরণে, [4], [7] তুলনা করে কনক্যাটেনেট করা হয়, তারপর [5], [9] এবং এভাবে [4,7], [5,9], [1,3], [2,8] অ্যারেগুলো তৈরি হয়।
- একই পদ্ধতিতে দুটি করে অ্যারে তুলনা করে কনক্যাটেনেট করা হয় বড় অ্যারে বানাতে। উদাহরণে [4,7] এবং [5,9] তুলনা করে [4,5,7,9] এবং [1,3] ও [2,8] থেকে [1,2,3,8] তৈরি হয়।
- একই নিয়ম অনুযায়ী শেষের দুটি অ্যারে তুলনা করে ফাইনাল সর্টেড অ্যারে [1,2,3,4,5,7,8,9] পাওয়া যায়।
উদাহরণ
<html> <body> <script> function mSort (array) { if (array.length === 1) { return array // return once we hit an array with a single item } const middle = Math.floor(array.length / 2) // get the middle item of the array rounded down const left = array.slice(0, middle) // items on the left side const right = array.slice(middle) // items on the right side document.write(middle); return merge( mSort(left), mSort(right) ) } // compare the arrays item by item and return the concatenated result function merge (left, right) { let result = [] let leftIndex = 0 let rightIndex = 0 while (leftIndex < left.length && rightIndex < right.length) { if (left[leftIndex] < right[rightIndex]) { result.push(left[leftIndex]) leftIndex++ document.write("</br>"); } else { result.push(right[rightIndex]) rightIndex++ } } return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex)) } const list = [4,7,5,9,1,3,8,2] document.write(mSort(list)); </script> </body> </html>
আউটপুট
1,2,3,4,5,7,8,9
