Минимальное количество для сортировки массива в Python путем отправки элемента в конец

Question

Вот объяснение того, что я пытаюсь сказать: -

Input:- 5 1 3 2 7

Output:- 3

Объяснение:

В первом шаге мы переместились на 3 до конца.Наш список становится 5,1,2,7,3

На втором ходу мы переместимся на 5 в конец.Наш список становится 1,2,7,3,5

На третьем ходу мы переместимся на 7 в конец.Наш окончательный список = 1,2,3,5,7

Итак, общее количество ходов: - 3.

Вот то, что я пытался сделать, но не получилось.

a = [int(i) for i in input().split()]
count = 0
n = 0
while (n < len(a) - 1):
    for i in range(0,n+1):
        while (a[i] > a[i + 1]):
            temp = a[i]
            a.pop(i)
            a.append(temp)
            count += 1
    n += 1

print(count, end='')

I 'Я хотел бы попросить вас помочь в решении этого вопроса.

Answer 1

Ответ jdehesa в основном правильный, но не оптимален для случаев, когда имеется больше элемента с таким же значением.Может быть, более сложное решение?

def min_moves(a):
    c = 0
    while(1):
        tmp = None
        for i in range(0, len(a)):
            if a[i] != min(a[i:]) and (tmp is None or a[i] < a[tmp]):
                tmp = i
        if tmp is None:
            return c
        else:
            a.append(a.pop(tmp))
            c += 1

Редактировать: Или, если вам не нужен упорядоченный список, есть гораздо более простое решение - просто считать элементы, которые вышли из строя по причине из решения jdehesa: -D

def min_moves(a):
    c = 0
    for i in range(0, len(a)):
        if a[i] != min(a[i:]):
            c += 1
    return c

Редактировать 2: Или, если вам больше нравится ответ jdehesa, небольшим исправлением является уменьшение lst для установки, поэтому он получит наименьший индекс

sorted_index = {elem: i for i, elem in enumerate(sorted(set(lst)))}

Я пока не могу комментировать.

Answer 2

Я думаю, что вы можете упростить вашу проблему,

Подсчет элементов, которые нужно нажать в конце, эквивалентен подсчету длины элементов, которые не в отсортированном порядке.

l = [5, 1, 3, 2, 7]

sorted_l = sorted(l)

current_element = sorted_l[0]
current_index = 0
ans = 0

for element in l:
    if current_element == element:
        current_index += 1
        if current_index < len(l):
            current_element = sorted_l[current_index]
    else:
        ans += 1
print(ans)

Здесь ответ 3

Answer 3

Я не знаю, можно ли это сделать лучше, но я думаю, что следующий алгоритм дает правильный ответ:

def num_move_end_sort(lst):
    # dict that maps each list element to its index in the sorted list
    sorted_index = {elem: i for i, elem in enumerate(sorted(lst))}
    moves = 0
    for idx, elem in enumerate(lst):
        if idx != sorted_index[elem] + moves:
            moves += 1
    return moves

print(num_move_end_sort([5, 1, 3, 2, 7]))
# 3

Идея состоит в следующем.Каждый элемент списка должен быть перемещен до конца не более одного раза (должно быть легко увидеть, что решение, которое перемещает один и тот же элемент в конец более одного раза, может быть упрощено).Таким образом, каждый элемент в списке может или не может быть перемещен один раз до конца.Если элемент не нужно перемещать, это потому, что после всех ходов он оказался в правильном положении.Таким образом, если элемент в данный момент находится в позиции i и должен в конечном итоге оказаться в позиции j, то элемент не нужно будет перемещать, если число предыдущих элементов, которые необходимо переместить, n, удовлетворяет j == i + n (потому что после этих n перемещений элемент действительно будет в позиции j).

Итак, чтобы вычислить это, я отсортировал список и взял индексы каждого элемента в отсортированномсписок.Затем вы просто подсчитываете количество элементов, которые не находятся в правильном положении.

Обратите внимание, что этот алгоритм не сообщает вам фактическую последовательность шагов, которые вам нужно будет выполнить (порядок, в котором элементы должны бытьпереехал), только граф.Сложность O (n · log (n)) (из-за сортировки).