#python-3.x #algorithm #sorting
Вопрос:
Я хочу сделать свой алгоритм более эффективным, удалив элементы, которые он уже отсортировал, но я не знаю, как я могу сделать это эффективно. Единственный способ, который я нашел, — это переписать весь список.
l = [] #Here you put your list
sl = [] # this is to store the list when it is sorted
a = 0 # variable to store which numbers he already looked for
while True: # loop
if len(sl) == len(l): #if their size is matching it will stop
print(sl) # print the sorted list
break
a = a 1
if a in l: # check if it is in list
sl.append(a) # add to sorted list
#here i want it to be deleted from the list.
Комментарии:
1. Есть гораздо лучшие способы сортировки списка. Просто проведите небольшой поиск.
2. Этот алгоритм вообще не выполняет сортировку. Он просто фильтрует натуральные числа по месту жительства в списке; он не работает для нецелых чисел, отрицательных чисел и дубликатов. Вы ищете а) добавление удаления в эту фильтрацию, б) повышение эффективности этой фильтрации или в) создание эффективного алгоритма сортировки?
3.
sl = sorted(l), который имеет преимущество завершения, даже если входной список не состоит исключительно из уникальных положительных чисел.4. На самом деле, он сортирует список, предполагая, что список состоит только из отдельных натуральных чисел. Он вернет неправильный результат, если список содержит дубликаты, отрицательные числа или нецелые числа.
5. @Stef Я не думаю, что он завершается, если только список ввода не состоит из уникальных положительных чисел. Условием расторжения является
len(sl) == len(l).
Ответ №1:
Переменная a немного неудобна. Он начинается с 0 и увеличивается 1 на 1, пока не будет соответствовать элементам из списка l
Представь, если l = [1000000, 1200000, -34] бы . Затем ваш алгоритм сначала будет выполняться в течение 1000000 итераций, ничего не делая, просто увеличиваясь a с 0 до 1000000. Затем он добавит 1000000 к sl . Затем он снова выполнит 200000 итераций, ничего не делая, просто увеличиваясь a с 1000000 до 1200000.
А затем он будет продолжать увеличиваться a в поисках числа -34, которое ниже нуля…
Я понимаю, что идея вашей переменной a состоит в том, чтобы выбрать элементы l по порядку, начиная с самого маленького элемента. Существует функция, которая делает это: она называется min() . Попробуйте использовать эту функцию , чтобы выбрать наименьший элемент из l и добавить этот элемент sl . Затем удалите этот элемент из l ; в противном случае при следующем вызове снова min() будет выбран тот же элемент вместо выбора следующего наименьшего элемента.
Обратите внимание, что у этого min() есть недостаток: он возвращает значение наименьшего элемента, но не его позицию в списке. Таким образом, не совсем очевидно, как удалить элемент из l после того, как вы его нашли min() . Альтернативой является написание собственной функции, которая возвращает как элемент, так и его положение. Вы можете сделать это с помощью одного цикла: в следующем фрагменте кода i ссылается на позицию в списке (0-позиция первого элемента, 1-позиция второго и т. Д.) И a ссылается на значение этого элемента. Я оставил пробелы, и вам нужно выяснить, как выбрать положение и значение самого маленького элемента в списке.
....
for i, a in enumerate(l):
if ...:
...
...
Если вам удалось все это сделать, поздравляю! Вы реализовали «сортировку выбора». Это хорошо известный алгоритм сортировки. Это один из самых простых. Существует множество других алгоритмов сортировки.