1

Q- I have an array A with the sizes of apples and have to create another array S which would contain the indices of the apples in sorted order given that we cannot directly access or touch A only a function is_large(A,i,j) function can access it. It returns -1 is A[i] > A[j] and 1 if A[i] < A[j]. I wrote the program but it is giving incorrect results even for small arrays what is the problem? The main problem is that the first element is not changing positions because of that the whole array is unsorted.

def is_large_apples(apple_size, i, j):
    """ Takes two indices and tells
    which one of them is larger or smaller """

    if apple_size[i] > apple_size[j]:
        return 1
    elif apple_size[i] < apple_size[j]:
        return -1

def mergesort_apples(s, l, r):
    """ This function takes indexed list and
     makes recursive calls to sort the array """
    if l < r:
        mid = (l+r)//2
        mergesort_apples(s, l, mid)
        mergesort_apples(s, mid+1, r)
        merge_apples(s, l, mid, r)


def merge_apples(s, l, mid, r):
    """ This function takes the list and
    the indices to merge them into the final array"""
    nl = mid - l + 1
    nr = r - mid
    left, right = [], []
    left = s[l:mid+1:1]
    right = s[mid+1:r+1:1]
    i, j, k = 0, 0, l;
    while i < nl and j < nr:
        print(s)
        if is_large_apples(apple_size, i, j) == -1:
            s[k] = left[i]
            i += 1
        else:
            s[k] = right[j]
            j += 1
        k += 1

    while i < nl:
        s[k] = left[i]
        k += 1
        i += 1
    while j < nr:
        s[k] = right[j]
        k += 1
        j += 1

apple_size = [5, 7, 1,44,2,33] # Given list of sizes.
s = [x for x in range(0,len(apple_size))] # Original list of indices.
mergesort_apples(s, 0, len(s)-1)
print(s)
3
  • You wrote: "it is giving incorrect results" - please describe incorrect and incorrect results. Include them into your question. Please read How to create a Minimal, Complete, and Verifiable example for inspiration Commented Mar 2, 2019 at 10:00
  • Your list s is [0, 1, 2] that is already orderly. Don't you want to sort apple_size, do you? Commented Mar 2, 2019 at 10:06
  • I want to sort apple_size indirectly using is_large() function and S should contain the indices of the sorted sizes. Commented Mar 2, 2019 at 10:17

1 Answer 1

1
if is_large_apples(apple_size, left[i], right[j]) == -1:

Because you want to check not i and j position, but left[i] position and right[j] position.

Sign up to request clarification or add additional context in comments.

1 Comment

Also it is worth to make elif apple_size[i] <= apple_size[j]: to propely treat equality cases

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.