Проблемы с получением количества свопов и прохождением в простой пузырьковой сортировке - PullRequest
Новая
       16

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

0 голосов
/ 02 апреля 2020

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

step = int(input())
a = list(map(int, input().split()))
passage_number = 0
swap_number = 0
for x in range(step):
    for i in range(step-x-1):
        passage_number += 1
        if a[i] <= a[i+1]:
            a[i], a[i+1] = a[i+1], a[i]
            swap_number += 1

print(passage_number, swap_number)

Пример ввода (две строки) и вывод:

8
3 1 4 1 5 9 2 6

5 8

(теперь он возвращает что-то вроде "21 14" и c, зависит от положения переменных)

Я думаю, что проблема в неправильной переменная позиция, но я не могу решить эту легкую проблему в течение 6 часов. Я пытался установить переменные в разных позициях и срок действия переменной 'step', но все попытки были безуспешными. Я буду очень признателен, если вы покажете мне, что я должен изменить в своем коде, чтобы решить эту проблему (внезапно Google не отвечает, кстати: D)

Ответы [ 2 ]

0 голосов
/ 02 апреля 2020

Похоже, что задача использует так называемую «модифицированную сортировку пузырьков», которая использует флаг, который останавливает алгоритм, если один проход через него не приводит к перестановкам. Чтобы реализовать это, вам просто нужно установить флаг перед началом цикла, сделать так, чтобы внешний круг сбросил его, и любой своп перевернул его, а затем имел оператор условного прерывания для проверки после каждого прохода. Секция l oop вашего кода будет выглядеть примерно так: 

for x in range(step - 1):
    passage_number += 1
    flag = True
    for i in range(step - 1):
        if a[i] > a[i+1]:
            a[i], a[i+1] = a[i+1], a[i]
            swap_number += 1
            flag = False
    if flag:
        break

Это дает 5 8 для вашей последовательности.

0 голосов
/ 02 апреля 2020
  1. сортируете ли вы в порядке возрастания? если да, условие обмена должно быть if a[i] > a[i+1]:, а не if a[i] <= a[i+1]:
  2. passage_number += 1 необходимо установить между for x in range(step): и for i in range(step-x-1):
...