CODEWITHSUNDEEP
pythonpython-3.xalgorithmselection-sort
new_user_who_this
new_user_who_this

Reputation: 23

Program does not properly sort lowest value in list in selection sort algorithm

I'm writing a program in Python that implements a selection sort algorithm and sorts the elements of a list in descending order.

Let's say my input is l = [242, 18, 44, 201, 1111].

My logic is as follows:

The output would be [1111, 242, 201, 44, 18].

So, here's the code I'm implementing based on the above logic:

def selSort(l):
    '''Sorts the list in descending order using a selection sort algorithm.

    Params: l (list): unsorted list
    Sorts: unsorted list in descending order
    '''
    start = len(l)-1
    while start != 0:
        for i in range(len(l)):
            if l[i] < l[start]:
                l[i], l[start] = l[start], l[i]
        start -= 1

It seems as though I overestimated my logic because the algorithm's output is [1111, 18, 242, 201, 44].

After some debugging, I was able to find that after a couple traversals l is properly sorted, but the while loop still hasn't met its terminating condition. This means that there's going to be some unwanted overlap between start and i. For example, when start = 3 and i = 4, l[i] < l[start], resulting in l = [1111, 242, 201, 18, 44]. After an additional traversal, we're at the incorrect output I showed above.

What would be an elegant (I'm aware selection sort isn't the most efficient algorithm) and Pythonic solution to this issue? I'm trying to achieve this without using any built-in functions (with the exception of len and range), methods, or outside libraries (if possible).

I've checked out the Selection Sort Algorithm Python and Selection Sort Algorithm in Java posts here on SO. The former uses list methods (which I'm trying to avoid) and I don't understand java syntax well enough to make use of the latter.

Upvotes: 1

Views: 222

Answers (2)

florex
florex

Reputation: 963

The logic of the select sort algorithm (descending order) : is to iterate over the table n-1 times(n being the number of elements in the list). at the ith iteration, we select the highest element between the indices i+1 and n and swap that element with the element at the position i in the list. This leads to the following code :

def selSort(l):
    '''Sorts the list in descending order using a selection sort algorithm.

    Params: l (list): unsorted list
    Sorts: unsorted list in descending order
    '''
    for i in range(len(l)-1) :
        posMax = i
        for j in range(i+1,len(l)):
            if l[j] > l[posMax]:
                posMax = j
        l[posMax], l[i] = l[i], l[posMax]
    return l

l = selSort([242, 18, 44, 201, 1111])
print(l) #prints [1111, 242, 201, 44, 18]

Upvotes: 2

Noah B. Johnson
Noah B. Johnson

Reputation: 312

This should work. It also uses range() to avoid having to use a while loop.

def selSort(l):
'''Sorts the list in descending order using a selection sort algorithm.

Params: l (list): unsorted list
Sorts: unsorted list in descending order
'''
for i in range(len(l)):

    # Find the largest element in list
    max_index = i
    for j in range(i + 1, len(l)):
        if l[max_index] < l[j]:
            max_index = j

    # Swap the first and max item
    l[i], l[max_index] = l[max_index], l[i]

Upvotes: 2

Related Questions