WedX - журнал о программировании и компьютерных науках

Пузырьковая сортировка Python с пониманием списка

Я новичок в Python, и я пытаюсь реализовать алгоритм с пузырьковой сортировкой, но используя понимание списка. Хотя я использовал понимание списка, используя if и for, я не мог найти способ реализовать вложенный for, а также своп для сортировки.

Ниже приведен код, который я пытался использовать.

import random as rn
l=[]
N=int(input('Give an integer: '))
for i in range(N):
    l.append(rn.randint(1,100))
print(l)

listset = [l[:k-1] + [l[k]] + [l[k-1]] + l[k+1:] if l[k] > l[k-1] else l for k in range(1,len(l)) ]

print(listset)

Есть ли у вас какие-либо предложения о том, как правильно использовать понимание списка для реализации алгоритма пузырьковой сортировки?

Заранее спасибо.

python list list-comprehension bubble-sort
31.10.2017

  • Я не думаю, что это практическая цель. Большинство алгоритмов сортировки зависят от частичного результата для достижения следующего шага, что на самом деле несовместимо с пониманием списка. 31.10.2017
  • Вы можете использовать этот код, чтобы указать правильное направление. 31.10.2017
  • Здравствуйте, спасибо за ответ. К сожалению, это требование короткого проекта, над которым я работаю для курса, и нас явно просят использовать понимание списка для алгоритма пузырьковой сортировки. 31.10.2017

Ответы:


1

Пузырьковая сортировка в основном заключается в том, что наименьшие (в порядке возрастания) значения поднимаются вверх в списке, что достигается за время O(n^2).

В случае понимания списка, поскольку мы создаем новый список, я не думаю, что точный алгоритм пузырьковой сортировки с заменой номеров на месте достижим. Создавая новый список, выбирая наименьшее (в порядке возрастания) число из несортированного списка n раза. В конце концов он создаст аналогичную сортировку выбора алгоритма, как показано ниже:

def extractMin(numberList):
   minValue = min(numberList)
   numberList.remove(minValue)
   return minValue

import random as rn
l=[]
N=int(input('Give an integer: '))
for i in range(N):
    l.append(rn.randint(1,100))
print(l)

sorted_list = [extractMin(l) for k in range(len(l))]
print(sorted_list)

Функция extractMin(..) имеет временную сложность O(n), которая вызывается n раз, следовательно, временная сложность всей сортировки составляет O(n^2).

31.10.2017
  • Это не пузырьковая сортировка. Если у вас есть 3, 1, 4, 2, то один проход пузырьковой сортировки превратит это в 1, 3, 2, 4, а второй проход превратит его в 1, 2, 3, 4. Алгоритм, показанный здесь в основном сортировка выбором. 01.11.2017

    • 2

    Вот решение, которое выполняет сортировку исключительно с использованием понимания списка.

    import itertools
s = [5, 6, 2, 4, 5, 6, 7]
new_s = s[:]
temp1 = 0
final_data = [[globals().update(temp1=s[b]), globals().update(s=s[:b]+[temp1]+s[b+1:]), globals().update(s= s[:b]+[s[b+1]]+s[b+1:])] for i in range(len(s)) for b in range(len(s)-1) if s[b+1] < s[b]]
new_final_list = list(itertools.chain.from_iterable([[a]*new_s.count(a) for a, b in itertools.groupby(s)]))

    Выход:

    [2, 4, 5, 5, 6, 6, 7]
    31.10.2017
  • Запутанные решения обычно сопровождаются каким-либо объяснением. 01.11.2017
    • Новые материалы
    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..
    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..
    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..
    Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
    Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..
    Учебные заметки: создание моего первого пакета Node.js
    Это мои обучающие заметки, когда я научился создавать свой самый первый пакет Node.js, распространяемый через npm. Оглавление Глоссарий I. Новый пакет 1.1 советы по инициализации..
    Забудьте о Matplotlib: улучшите визуализацию данных с помощью умопомрачительных функций Seaborn!
    Примечание. Эта запись в блоге предполагает базовое знакомство с Python и концепциями анализа данных. Привет, энтузиасты данных! Добро пожаловать в мой блог, где я расскажу о невероятных..
    ИИ в аэрокосмической отрасли
    Каждый полет – это шаг вперед к великой мечте. Чтобы это происходило в их собственном темпе, необходима команда астронавтов для погони за космосом и команда технического обслуживания..
    Для любых предложений по сайту: [email protected]