মার্জ-সর্ট
মার্জ সর্ট হল ডিভাইড-এন্ড-কনকার টাইপ সর্টিং-অ্যালগরিদমের একটি উদাহরণ৷ মার্জ সাজানোর ইনপুট হল কিছু উপাদানের একটি অ্যারে, যেগুলিকে সাধারণত সর্বনিম্ন থেকে সর্বশ্রেষ্ঠ পর্যন্ত সাজানো প্রয়োজন৷
মার্জ সর্টে অনুসরণ করার জন্য ধাপগুলি
- মার্জ সর্ট অ্যারেটিকে দুটি সাব অ্যারেতে ভাগ করে এবং পরবর্তীতে প্রতিটি অ্যারেকে অন্য দুটি অ্যারেতে ভাগ করে এবং একইভাবে একগুচ্ছ একক উপাদান অ্যারে বাকি না হওয়া পর্যন্ত। উদাহরণস্বরূপ, নিম্নলিখিত উদাহরণে অ্যারে [4,7,5,9,1,3,8,2] একক অ্যারে উপাদানগুলিতে বিভক্ত হয় যেমন [4], [7], [5], [9], [১], [৩], [৮], [২]।
- এটি এমনভাবে অ্যারেগুলির তুলনা শুরু করে যাতে দুটি অ্যারে তুলনা করা হয় এবং একত্রিত হয়। নিম্নলিখিত উদাহরণে, এটি একটি সময়ে দুটি অ্যারে তুলনা করে যেটি [4], [7] তুলনা করা হয় এবং সংযুক্ত করা হয় তারপর [5], [9] তুলনা করা হয় এবং সংযুক্ত করা হয় এবং এইরকম যে অ্যারেগুলি [4,7], [ 5,9], [1,3], [2,8] গঠিত হয়।
- এটি একইভাবে অনুসরণ করে যেভাবে দুই-দুটি অ্যারে তুলনা করা হয় এবং দুটি অ্যারে গঠন করে। নিম্নলিখিত উদাহরণে [4,7] এবং [5,9] তুলনা করা হয়েছে এবং [4,5,7,9] হিসাবে একটি অ্যারে পাওয়ার জন্য সংযুক্ত করা হয়েছে এবং একইভাবে অন্যান্য দুটি অ্যারের ক্ষেত্রে একটি অ্যারে তৈরি করা হয়েছে [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
