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:')))
this program is very confusing - you don’t need the variables "bigger" and "smaller" - you have to compare with the numbers that are inside the list. What’s more, besides not needing it, you are not putting values inside them in a way that makes sense - you only fill "bigger" and "smaller" within the "if" conditions"
– jsbueno
When you do
numeros.insert(menor < num < meio, num)
the first parameter is something that should be an integer that means where it will be inserted. You are passing something that will be true or false (a<b<c).– Naslausky