আমি পাইথন দিয়ে মার্জ সর্ট ইমপ্লিমেন্ট করার চেষ্টা করছিলাম। নিচের কোডটি লিখেছি:

#!/usr/bin/env python

def mergesort(data_list, p, r):
    if p < r:
        q = (p + r) / 2
        mergesort(data_list, p, q - 1)
        mergesort(data_list, q, r)
        merge(data_list, p, q, r)

def merge(data_list, p, q, r):
    left = data_list[p:q]
    right = data_list[q:r + 1]

    left.append(float('inf'))
    right.append(float('inf'))

    i = 0
    j = 0
    for k in range(p, r + 1):
        if left[i] < right[j]:
            data_list[k] = left[i]
            i += 1
        else:
            data_list[k] = right[j]
            j += 1

data_list = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
print data_list
mergesort(data_list, 0, len(data_list) - 1)
print data_list

সমস্যা হচ্ছে p = 2 এবং r = 3 এই সাব অ্যারে এর জন্য q = 2 আসছে যেহেতু q = floor((p + q) / 2) নিচ্ছি। পরবর্তী রিকার্শনে যেহেতু q এর মানই p এর মান হয়ে যাবে এবং r এর মান অপরিবর্তিত থাকবে তাই আবারও p = 2 এবং r = 3 হয়ে যাচ্ছে। যেকারণে অসীম রিকার্শন হয়ে মেমরি স্ট্যাক ওভারফ্লো হচ্ছে।

এর একটা সহজ সমাধান হচ্ছে q = floor((p + r + 1) / 2) ব্যবহার করা। কিন্তু এটা সব টেস্ট কেস এর জন্য খাটবে কি?

আমি কি অ্যালগরিদম ইমপ্লিমেন্ট করতে গিয়ে কোন কিছু ভুল করেছি?

asked 30 Dec '17, 19:40

Ashfaqur%20Rahman's gravatar image

Ashfaqur Rahman
78310

edited 31 Dec '17, 03:16

Mosharraf%20Hosain's gravatar image

Mosharraf Hosain ♦
74618


নিচের মতো করে লিখলে সমস্যা হওয়ার কথা না -

mergesort(data_list, p, q)
mergesort(data_list, q+1, r)

আর মার্জ করার ফাংশনটা ঠিক আছে কী না, সেটা পরীক্ষা করা যায় এভাবে (তোমার কোড অনুসারে একটু পরিবর্তন করতে হবে)-

if __name__ == "__main__":
    a = [1]
    b = [2]
    expected_merged_list = [1, 2]
    merged_list = merge(a, b)
    try:
        assert expected_merged_list == merged_list
    except AssertionError:
        print("Output didn't match expected output")
        print("expected:", expected_merged_list)
        print("got:", merged_list)

    a = [1, 3, 5, 6]
    b = [2, 4, 7, 8]
    expected_merged_list = [1, 2, 3, 4, 5, 6, 7, 8]
    merged_list = merge(a, b)
    try:
        assert expected_merged_list == merged_list
    except AssertionError:
        print("Output didn't match expected output")
        print("expected:", expected_merged_list)
        print("got:", merged_list)
permanent link

answered 16 Jan '18, 01:25

Tamim%20Shahriar%20Subeen's gravatar image

Tamim Shahriar Subeen ♦♦
6.2k21128

edited 16 Jan '18, 08:24

সেক্ষেত্রে ভুল আউটপুট দিচ্ছে:

ইনপুট: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

আউটপুট: [5, 3, 2, 4, 1, 0, 8, 7, 9, 6]

(16 Jan '18, 08:14) Ashfaqur Rahman
1

merge() ফাংশনটা ঠিক আছে কী না দেখতে হবে। এজন্য কয়েকটা ইউনিট টেস্ট লেখা যায়। আমার উত্তরটা আপডেট করলাম।

(16 Jan '18, 08:19) Tamim Shahriar Subeen ♦♦

ইউনিট টেস্ট করে দেখিনি তবে আপনার ইউনিট টেস্ট এক্সাম্পল থেকে সমস্যাটা ধরতে পেরেছি।

(16 Jan '18, 20:53) Ashfaqur Rahman

যদিও মূল প্রশ্নের সমাধান @Tamim Shahriar Subeen ভাইয়ার উত্তরে দেয়া আছে, তবুও সম্পূর্ণতার জন্য এই উত্তর:

ভাইয়ার উত্তর অনুযায়ী কোড মডিফাই করা হলে ইনফাইনাইট রিকার্শন হবে না তবে এলগরিদম ভুল উত্তর দিবে যেহেতু merge() প্রসিডিউরে ভুল আছে। মার্জ প্রসিডিউরে যখন দুই ইলিমেন্ট যুক্ত সাব লিস্ট যাচ্ছে তখন সমস্যাটা হচ্ছে। ধরা যাক দুটি ইলিমেন্ট যুক্ত সাব লিস্টটির লোয়ার ইনডেক্স x তাহলে অবশ্যই আপার ইনডেক্স হবে x + 1। সেক্ষেত্রে merge(data_list, p, q, r) কে যখন কল করা হচ্ছে তখন p = x, r = x + 1 এবং যেহেতু q = (p + r) / 2 তাই q = x। মার্জ প্রসিডিউরে সাব লিস্টটিকে লেফ্ট এবং রাইট এই দুটি অংশে ভাগ করা হচ্ছে। সমস্যাটা হচ্ছে মার্জ প্রসিডিউরে সাব লিস্টের লেফ্ট পার্টটা কপি করার সময়। কপি করা হচ্ছে স্লাইসিং করে left = data_list[p:q]। যেটা আসলে দাড়াচ্ছে left = data_list[x:x] যেটা আসলে একটা ইম্পটি লিস্ট! মার্জ প্রসিডিউরে লেফ্ট এবং রাইট সাবলিস্টে ভাগ করার সঠিক কোড হবে left = data_list[p:q + 1] এবং right = data_list[q + 1:r + 1]

permanent link

answered 16 Jan '18, 20:52

Ashfaqur%20Rahman's gravatar image

Ashfaqur Rahman
78310

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×39
×9

question asked: 30 Dec '17, 19:40

question was seen: 772 times

last updated: 16 Jan '18, 20:53