Insert elements in the correct position in an ordered list

Question

I wonder why this code does not work for the exercise below, because when it comes to the values that will be intermediate in the list, they end up being reversed (the example I used to test if it would work was (15, 5, 6, 7, 8)).

Create a program where the user can enter five numerical values and register them in a list, already in the correct position of insertion(without using o Sort()). At the end, display the sorted list on the screen.

numeros = []
maior = menor = meio = 0
for i in range(0, 5):
    num = int(input("Digite um número: "))
    if i == 0:
        maior = menor = num
        numeros.append(num)
    elif num >= maior:
        maior = num
        numeros.append(num)
    elif num <= menor:
        menor = num
        numeros.insert(0, num)
    elif menor < num < maior:
        if meio == 0:
            meio = num
            numeros.insert(menor < num < maior, num)
        elif meio <= num:
            numeros.insert(meio < num < maior, num)
            meio = num
        elif meio >= num:
            numeros.insert(menor < num < meio, num)
print(numeros)

Answer 1

One of the problems is in numeros.insert(menor < num < maior, num).

The expression menor < num < maior is a comparison (checks whether num is among menor and maior), whose result will be a boolean (that is to say, True or False). Only that one boolean in Python, according to the documentation, in numerical contexts is interpreted as the values 1 (True) and 0 (False). Example:

lista = [1, 2, 3]

# mudando a posição zero
lista[False] = 10
# mudando a posição 1
lista[True] = 20

print(lista) # [10, 20, 3]

That is, instead of the result of a comparison, you should pass only the value of the index.

---

That being said, you don’t have to go through the whole list - and don’t even do a lot of if/elif - to find the right position. As we are always ensuring that the list will be sorted, you can start searching from the middle of the list.

If the number to be inserted is less than the middle element, you check the first half of the list, if it is larger, check the second half, and continue doing so until you find the correct position:

lista = []
for _ in range(5):
    n = int(input('digite o número: '))
    # se a lista for vazia, insere
    if not lista:
        lista.append(n)
    else:
        # procura a posição
        inicio, fim = 0, len(lista)
        while inicio < fim:
            meio = (inicio + fim) // 2
            if n < lista[meio]:
                fim = meio
            else:
                inicio = meio + 1
        lista.insert(inicio, n)

To check if the list is empty I did if not lista, since an empty list is considered False.

Just to illustrate how the algorithm works (all right for a small list like this, which will only have 5 elements, it makes no difference, but imagine a list of arbitrary size). Assuming the list has 1000 elements, I start searching for element 500.

If the number is greater than the 500 element, I check the second half (i.e., I now take the middle element of the second half, which is at position 750). If the number is less than the element of position 500, I check the first half (take the element of position 250 and see if the number should be before or after it - and depeded from the case, take the position 125 or 375, and so on).

And I keep doing it, narrowing my search (I’m going to take the middle element of half of half of the list, after half of half of half, etc - I don’t need to check the rest of the list because the previous steps already assured me that the element should not be inserted there). That’s only possible because I always make sure the list is sorted.

Doing so is much more efficient than going through the entire list (or making a complicated chain of if/elif). Even if the list has 1 billion elements, in about 30 steps I can find the right position.

---

In fact, I wouldn’t even need to check if the list is empty:

lista = []
for _ in range(5):
    n = int(input('digite o número: '))
    inicio, fim = 0, len(lista)
    while inicio < fim:
        meio = (inicio + fim) // 2
        if n < lista[meio]:
            fim = meio
        else:
            inicio = meio + 1
    lista.insert(inicio, n)

When the list is empty, so much inicio how much fim will have the value zero, then will not enter the while and the element will normally be inserted in the list.

---

I know it’s an exercise, but in any case, the language already has it ready in the module bisect:

from bisect import insort
lista = []
for _ in range(5):
    insort(lista, int(input('digite o número:')))

Answer 2

this program became much, much, more complicated than it was supposed to be. But it is not possible to "fix it" - better to write another one.

You can read the comment above as a scolding - but it’s not the idea - welcome, and thank you for using the platform. And yes, when we are learning, some things are unclear - and some concept we learn sometimes may seem like a "Swiss Army knife" that does everything. So, no bad feelings - the program you did is part of a learning stage - just like it does "crumple, throw away, and start over" - it got confused - with variables that don’t make sense, it’s really not worth trying to unravel and correct it. Let’s take a shower and think about the problem:

• the hint is this: after asking a number (input), Voce has to go through the list to find the place of the next number - then you need a "for" inside the first "for" (it can be a while, if you prefer) - but try to guess where the new number is at the base of the "if...Elif" without going through the list is unfeasible - and if instead of five elements, list had 300?

The basic structure has to be:

lista = []
for i in range(comprimento_desejado):
    num = int(input("digite o numero: ")
    for posicao, elemento in enumerate(lista):
        # aqui voce poe um unico if e decide
        # se insere o novo número ou não
    # aqui, fora do "for" internom você testa se o número ainda
    # não foi inserido, se não foi, acrescenta-o
    # o final da lista

That’s all. I explain the "enumerate" - it is a special Python function that takes each element of a sequence and returns the position (index) and the element - and then you can use two tillers on one for - one with the position, the other with the element. The two sections below are equivalent:

for posicao, elemento in enumerate(lista):
    ...

and

for posicao in range(len(lista)):
    elemento = lista[posicao]
   ...