Python List sort algo, unepected last element of the list

Question

The algorithm works as follow:

1. I find the minimum of a given list.
2. Then pop it and append it to another list.
3. Repeat step 1 and 2 until there is one element, in which case i simply append it to the other list and end the program.

Issue

The last element is always some random number which should be sorted long ago.

Source Code

lst=[randrange(1, 100) for i in range(100)]
lst2=[]
while True:
    if len(lst) > 1:
        min = 0
        for i in range(len(lst) -1):
                if min == 0:
                    min = lst[i]
                else:
                    if lst[i] < min:
                         min = lst[i]
        for j in range(len(lst) -1):
            if lst[j] == min:
                lst2.append(lst[j])
                lst.pop(j)
                break
    else:
        lst2.append(lst[0])
        break
lst = lst2
print(lst)

Answer 1

Your code has just one minor flaw. As @Tomerikoo pointed out already, there is just a little mistake at the iterators. The correct code would look like this:

lst=[randrange(1, 100) for i in range(100)]
lst2=[]
while True:
    if len(lst) > 1:
        min = 0
        for i in range(len(lst)):
                if min == 0:
                    min = lst[i]
                else:
                    if lst[i] < min:
                         min = lst[i]
        for j in range(len(lst)):
            if lst[j] == min:
                lst2.append(lst[j])
                lst.pop(j)
                break
    else:
        lst2.append(lst[0])
        break
lst = lst2
print(lst)

There is a bit more elegant implementation, that iterates over the list items instead of just the indices.

lst=[randrange(1, 100) for i in range(100)]
lst2=[]
while True:
    if len(lst) > 1:
        min = 0
        for item in lst:
                if min == 0:
                    min = item
                else:
                    if item < min:
                         min = item
        for idx, item in enumerate(lst):
            if item == min:
                lst2.append(item)
                lst.pop(idx)
                break
    else:
        lst2.append(lst[0])
        break
lst = lst2
print(lst)

In the one case where you actually need an index an enumerate is your tool of choice. This improvement makes your code easier to read in general and utilizes one of the features of Python instead of, for example, C.

Answer 2

1. Change for i in range(len(lst) -1): to for i in range(len(lst)):

2. You can improve the Algorithm by finding the index directly without loping twice as so:

from random import randrange


lst = [randrange(1, 100) for i in range(100)]
lst2 = []
while True:
    if len(lst) > 1:
        min = 0
        for i in range(len(lst)):  # FIND min value
                if not min:
                    min = lst[i]
                else:
                    if lst[i] < min:
                         min = lst[i]
        get_index = lst.index(min)  # Get index of Value
        min_value = lst.pop(get_index) # Pop min value
        lst2.append(min_value)  # Append min Value
    else:
        lst2.append(lst[0])
        break
lst = lst2
print(lst)

EDIT

@MatsLindh & @Tomerikoo Pointed out that index function internally runs a loop (so basically is the same) but just more readable

Hence the following code would be much cleaner and with a better performance:

from random import randrange


lst = [randrange(1, 100) for i in range(100)]
lst2 = []
while True:
    if len(lst) > 1:
        min = 0
        idx = 0
        for i in range(len(lst)):  # FIND min value
                if not min:
                    min = lst[i]
                    idx = i
                else:
                    if lst[i] < min:
                        min = lst[i]
                        idx = i  #Store Index of min_value
        min_value = lst.pop(idx) # Pop min value
        lst2.append(min_value)  # Append min Value
    else:
        lst2.append(lst[0])
        break
lst = lst2
print(lst)

---

Guides

• index Function