Because selection sort divides the input list into two parts: a sublist of sorted items and a sublist of still unsorted items, would it be possible to create two different functions and connect them together? I have my sorting algorithm done but I cannot figure out how to split them.

def selection_sort(l):
    for i in range(len(l)):
        start_index = i

    for j in range(i   1, len(l)):

        if l[start_index] > l[j]:
            min_value = j

    l[i], l[start_index] = l[start_index], l[i]

l = [64, 25, 12, 22, 11]
print(l)

What I would like to have is to split it into this:

def min_index(l, start_index) & def selection_sort(l)

CodePudding user response：

First of all, the code you have presented is not correct:

• There is only one swap happening, unconditionally, as the last statement of the function. This cannot be right of course. The number of swaps needed to sort a list varies depending its order.

• The second loop never iterates: i has reached the length of the input, and so range(i 1, len(i)) is an empty range.

• The value of min_value is never used.

The first two issues are probably because you copied the code in a wrong way, and missed some necessary indentation. The second issue is because of two different names which should really be the same name.

Here is a corrected version:

def selection_sort(l):
    for i in range(len(l)):
        start_index = i

        for j in range(i   1, len(l)):
            if l[start_index] > l[j]:
                start_index = j

        l[i], l[start_index] = l[start_index], l[i]

Now to your question: you can indeed put the logic of the inner loop into another function. Like this:

def min_index(l, i):
    for j in range(i   1, len(l)):
        if l[i] > l[j]:
            i = j
    return i

def selection_sort(l):
    for i in range(len(l)):
        j = min_index(l, i)
        l[i], l[j] = l[j], l[i]

CodePudding user response：

Your selection sort was buggy, so I corrected it. In short:

1. The indentation was incorrect so the loops were not nested (which I assume probably happened due to formatting issue on this platform).
2. in your inner loop you test start_index against j but update min_value.
3. at the end of the inner loop you use start_index for swapping. start_index is always equal to i.

Here's the corrected version with some variable renaming for better reading.

def selection_sort(arr): 
    for i in range(len(arr)): 
        min_index = i 
 
        for j in range(i   1, len(arr)): 
 
            if arr[min_index] > arr[j]:  
                min_index = j 
 
        arr[i], arr[min_index] = arr[min_index], arr[i]

The refactored version into 2 parts:

def selection_sort2(arr):  
    for i in range(len(arr)-1):  
        min_index = get_min_index(i, arr)  
   
        arr[i], arr[min_index] = arr[min_index], arr[i]


def get_min_index(i, arr):  
    min_index = i  
    for j in range(i   1, len(arr)):  
  
        if arr[min_index] > arr[j]:   
            min_index = j 
    return min_index