How to sort an array by finding min and max of subarrays?-CodePudding

I am trying to implement a sorting algorithm that will find the maximum and minimum elements in an array and then swap them with the last and first elements of the array, respectively. The algorithm will then shrink the array by two elements (the first and last elements, that have been placed in sorted position) and then perform the same operation repeatedly on the subarrays until the array is completely sorted.

I can't however seem to get it to function, and I'm not sure why. There are no errors of any kind, but the array is left completely unchanged after running the function. Here is what I have:

def novel_sort(arr, left, right):
    if left < right:
        min_index = left
        max_index = left
        for i in range(left, right 1):
            if arr[i] < arr[min_index]:
                min_index = i
            if arr[i] > arr[max_index]:
                max_index = i
        arr[left], arr[min_index] = arr[min_index], arr[left]
        arr[right], arr[max_index] = arr[max_index], arr[right]
        novel_sort(arr, left   1, right - 1)

Input

l = [235, 25, 123, 1]
novel_sort(l, 0, len(l) - 1)
print(l)

Expected output

[1, 25, 123, 235]

Observed Output

[235, 25, 123, 1]

If I change the for loop to for i in range(left, right) then every element of the array will be sorted except for the last element ([1, 123, 235, 25]). I've tried following along by iteration, but I still cannot seem to figure out what is happening.

CodePudding user response：

Because you're doing the swapping in two separate steps, you run the risk of having swapped the original highest value (if it happens to be at index left) when you placed the lowest values there. Then, on the next line, the index of the max value (max_index being equal to left) no longer references the highest value (there are actually 3 tricky cases like this: max on the left, min on the right, and both at the same time).

When you changed your loop to for i in range(left, right) the relative positions of left and right are affected and you may not get into that situation for the same list (although a different list content might still have the same issue).

As pointed out by don't talk just code, compensating for the index conflicts is going to be more involved than merely performing the swaps in one operation.

Something like this (I haven't checked all edge cases mind you):

low,high,swapLow,swapHigh = arr[min_index],arr[max_index],arr[left], arr[right]
if right == min_index: swapLow,swapHigh = high,swapLow
if left  == max_index: swapLow,swapHigh = swapHigh,low
arr[left],arr[right],arr[min_index],arr[max_index] = low,high,swapLow,swapHigh

when the lowest value is at the right, the swapping will want to put the original value that was at index left into the min_index position (which is also index right) where we actually want the highest value to be. So we need to change the temporary variable (swapLow) to the highest value. And the max_index position now needs to receive what was originally at min_index. The same reasoning applies when the highest value is at the left.

Another way to avoid the issue is to ensure that the index conflicts never occur by swapping left and right before the loop if the left value is larger than the right one. By making the value at index left smaller than the value at index right, neither of them will be an opposing swap target at the end of the loop.

def novel_sort(arr, left, right):
    if left < right:
        min_index = left
        max_index = left
        if arr[left]>arr[right]:         # avoid swapping conflicts
            arr[left],arr[right]=arr[right],arr[left]
        for i in range(left 1, right 1): # left 1 saves one comparison
            if arr[i] < arr[min_index]:
                min_index = i
            if arr[i] >= arr[max_index]: # changed to >=
                max_index = i
        arr[left], arr[min_index] = arr[min_index], arr[left]
        arr[right], arr[max_index] = arr[max_index], arr[right]
        novel_sort(arr, left   1, right - 1)

note that I also changed the comparison for the max_index so that the sort properly processes lists containing duplicate values. This makes sure that the swapped maximum is the one at the highest index (so, if left and right are equal and the highest value, we don't get into an index conflict again)

CodePudding user response：

Your first swap might involve the max value, making your max_index wrong. Simple fix between the two swaps: If the max was at left, then after that first swap it's now at min_index:

        arr[left], arr[min_index] = arr[min_index], arr[left]
        if max_index == left:
            max_index = min_index
        arr[right], arr[max_index] = arr[max_index], arr[right]

You can ignore the case of max_index having been min_index, as then all remaining values are the same so it doesn't matter.

CodePudding user response：

Just use sort() if you are trying to sort an array.

example

array=[1,20,4,56,78,3,307]
array.sort()
print(array)
# prints [1, 3, 4, 20, 56, 78, 307]

The sort method will change the original variable to a sorted version.