стабильная сортировка с использованием питона-пузыря сортировка

Итак, я получил список кортежей для сортировки по порядку. То, что мне не хватает, делает сортировку стабильной.стабильная сортировка с использованием питона-пузыря сортировка

Как я могу создать стабильный пузырь? (Поддерживать порядок на аналогичных предметах)

def bubble_sort_2nd_value(tuples_list): 
    NEWLIST = [] 
    ITEM_MOVE = 0 
    for i in tuples_list: 
     NEWLIST.append(i) 
    for i in range(len(NEWLIST)): 
     for j in range(i+1, len(NEWLIST)): 
      if(NEWLIST[j][1] < NEWLIST[i][1]): 
       ITEM_MOVE = 1 
       NEWLIST[j],NEWLIST[i] = NEWLIST[i],NEWLIST[j] 

    if (ITEM_MOVE == 0): 
     print(tuples_list) 
    else: 
     print(NEWLIST) 

tuples_list = [('h2', 8), ('h4', 30), ('h6', 7), ('h8', 54), ('h1', 72), ('h3', 8), ('h5', 7), ('h7', 15), ('h7', 24)] 

bubble_sort_2nd_value(tuples_list)

тестера resault, который, как ожидается, и у resault сравнения: Отображения выходного сигнала от элемента 0 ожидаемого: [('h6', 7), (H5 ', 7), ('h2', 8), ('h3', 8), ('h7', 15), ('h9', 24), ('h4', 30), ('h8', 54), (' h1 ', 72)] фактический: [(' h6 ', 7), (' h5 ', 7), (' h3 ', 8), (' h2 ', 8), (' h7 ', 15), ('h4', 30), ('h8', 54), ('h1', 72)] result_code bubble_14 wrong 1

Обратите внимание на смесь h2/3 ... нужно исправить это .. что я имею в виду под нестабильным

источник

2013-11-08 David

Переменные имена во всех CAPS, случайные символы табуляции в середине строк, с использованием '0' и' 1' для обозначения 'False' и' True', ненужных парсеров и т. Д. ... все это значительно усложняет читать и, следовательно, отлаживать ваш код. – abarnert

Между тем, это не пузырь. Весь смысл выбора пузырьков заключается в том, что каждый раз вы сравниваете каждый элемент только с его ближайшим соседом. Причина, по которой вы храните флаг 'ITEM_MOVE', заключается в том, что вам нужно продолжать цикл, пока он не станет ложным. Таким образом, нет никакого способа превратить это в стабильный вид пузыря, чтобы выбросить его и написать сначала пузырь, который будет автоматически стабильным. – abarnert

@abarnet Я почти уверен, что его текущий код - это пузырь. 'ITEM_MOVE' не делает ничего, кроме короткого замыкания логики печати, которая, возможно, не нужна. –

Лучшее, что вы могли бы сделать прямо сейчас, это понять, почему он переключает эти предметы. На каждом шаге печатайте, какие элементы меняются. Тогда вы можете понять поведение.

Таким образом, я пошел на это, вы не сравниваете текущий элемент со следующим элементом в списке, вы сравниваете текущий элемент со всеми перечисленными ниже элементами в списке. Изменения, которые я сделал, могут дать вам результат, который вы хотите.

def bubble_sort_2nd_value(tuples_list): 
    NEWLIST = [] 
    ITEM_MOVE = 0 
    for i in tuples_list: 
     NEWLIST.append(i) 
    for i in range(len(NEWLIST)): 
     for j in range(len(NEWLIST)-1): 
      k=j+1 
      if(NEWLIST[j][1] > NEWLIST[k][1]): 
       ITEM_MOVE = 1 
       NEWLIST[j],NEWLIST[k] = NEWLIST[k],NEWLIST[j] 

    if (ITEM_MOVE == 0): 
     print(tuples_list) 
    else: 
     print(NEWLIST) 

tuples_list = [('h2', 8), ('h4', 30), ('h6', 7), ('h8', 54), ('h1', 72), ('h3', 8), ('h5', 7), ('h7', 15), ('h7', 24)] 

bubble_sort_2nd_value(tuples_list)

Так что вы делаете не сорт 100% пузыря. Попробуйте это и скажите мне, если вы хотите, чтобы я объяснил, почему вы не работаете.

источник

2013-11-08 22:21:36

для ввода tuples_list = [('a', 2), ('b', 2), ('c', 1)] ваш код возвращает [('a', 2), ('b', 2) , ('c', 1)]. правильный результат должен быть [('c', 1), ('a', 2), ('b', 2)] – David

Я пробовал пару раз, и он работает нормально. Вы уверены, что используете (NEWLIST [j] [1]> NEWLIST [k] [1]), а не (NEWLIST [j] [1]

стабильная сортировка с использованием питона-пузыря сортировка

ответ

Смежные вопросы