Python 3: Вставка Сортировка счетчиков сравнений

Мне нужно добавить счетчик общих сравнений для моей программы сортировки вставки, но я не знаю, почему я получаю в общей сложности 0 сравнений!Python 3: Вставка Сортировка счетчиков сравнений

Я знаю, что выход сравнения должен быть 15 (для моего конкретного массива) не 0.

Это мой код до сих пор:

def insertionSort(values): 
    k = 0 
    n = len(values) - 1 
    comparisons = 0 
    while k+1 <= n: 
     i = k 
     while values[i] > values[i+1]: 
      temp = values[i] 
      values[i] = values[i+1] 
      values[i+1] = temp 
      comparisons += 1 #I think this is wrong 
     k = k + 1 
    return comparisons, values

Что я делаю неправильно?

источник

2016-05-17 a_guy

Я просто проверил ваш код и не выполнил его для сортировки [7,5,4,6].

Вот модифицированная версия -

def insertionSort_mod(values): 
    k = 0 
    n = len(values) - 1 
    comparisons = 0 
    while k+1 <= n: 
     i = k+1 
     curr_val = values[i] 
     comparisons += 1 
     while i>0 and values[i-1] > curr_val: 
      values[i] = values[i-1] 
      i=i-1 
      comparisons += 1 
     values[i] = curr_val 
     k = k + 1 
    return comparisons, values 

print insertionSort_mod([1, 2, 3, 55, 5, 6, 8, 7, 9, 111])

Выходы это:

(15, [1, 2, 3, 5, 6, 7, 8, 9, 55, 111])

В вашем контексте к + 1 должен быть текущий индекс, так что я должен быть к + 1 и должно быть по сравнению с предыдущее значение i-1

источник

2016-05-17 05:52:07

Я просто попробовал вашу модифицированную версию, но когда я тестирую массив [1, 2, 3, 55, 5, 6, 8, 7, 9, 111], он дает мне общее сравнение «6» должно быть 15. –

переменная сравнения претерпевает прирост только в том случае, если существует своп, поэтому он точно не сообщает о количестве сравнений, которые происходят. Чтобы сообщить об этом полностью, вам нужно увеличить свой счетчик до внутреннего и внутри внутреннего цикла while - оба места. 'в то время как к + 1 <= п: я = к + 1 curr_val = значения [I] сравнения + = 1 в то время как я> 0 и значения [I-1]> curr_val: значения [I] = значения [i-1] i = i-1 сравнения + = 1' Сделайте эту модификацию, которая должна это сделать ... –

только что отредактировал мой ответ, пожалуйста, проверьте ... –

Надеется, что это работает

def insertion(a,length): 
    count=0 
    for i in range(1,length): 
     key=a[i] 
     jj=i 
     while(jj>0 and a[jj-1]>key): 
      a[jj]=a[jj-1] 
      jj=jj-1 
      count += 1 
     a[jj]=key 
    print count

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

источник

2016-05-17 05:38:32

Python 3: Вставка Сортировка счетчиков сравнений

ответ

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