Как "отловить" место элемента при сортировке вставкой

Question

Есть такой код, который сортирует вставкой последовательность из input.txt, выводит в output.txt отсортированную последовательность, но еще надо отловить как-то места, куда они становятся после сортировки

Вот формулировка задания:
В первой строке выходного файла выведите n чисел. При этом i-ое число равно индексу, на который, в момент обработки его сортировкой вставками, был перемещен i-ый элемент исходного массива. Индексы нумеруются, начиная с единицы. Между любыми двумя числами должен стоять ровно один пробел.

Во второй строке выходного файла выведите отсортированный массив. Между любыми двумя числами должен стоять ровно один пробел.

Пример:
input.txt

10   
1 8 4 2 3 7 5 6 9 0

output.txt

1 2 2 2 3 5 5 6 9 1
0 1 2 3 4 5 6 7 8 9

код

with open('input.txt', 'r', encoding='utf-8') as f:
    n = int(f.readline())
    arr = list(map(int, f.read().split()))
    def insertion(array):
        for k in range(0,n):
            if array[k]<10**9:
                for i in range(1, n):
                    j = i - 1
                    key = array[i]
                    while array[j] > key and j >= 0:
                            array[j + 1] = arr[j]
                            j = j-1
                    array[j + 1] = key
    if not (n < 1 and n > 1000):
        insertion(arr)
with open('output.txt', 'w', encoding='utf-8') as f:
        f.write(" ".join(map(str, arr)))`

Answer 1

Вот в этой строчке array[j + 1] = key i-й элемент ставится на место с индексом j + 1.

Это число, увеличенное ещё на 1 (нумеруются, начиная с единицы), и выводите.

Без файлов:

n = 10
inp = '1 8 4 2 3 7 5 6 9 0'
arr = list(map(int, inp.split()))

def insertion(array):
    indexlist = []
    for i in range(n):
        j = i - 1
        key = array[i]
        while j >= 0 and array[j] > key:
            array[j + 1] = arr[j]
            j -= 1
        array[j + 1] = key
        indexlist.append(j+2)
    return indexlist

il = insertion(arr)
print(" ".join(map(str, il)))
print(" ".join(map(str, arr)))

1 2 2 2 3 5 5 6 9 1
0 1 2 3 4 5 6 7 8 9

P.S. а это зачем вообще ?

for k in range(0,n):
    if array[k]<10**9:

БЛОГ НА HUSL

Как "отловить" место элемента при сортировке вставкой

Ответы (1 шт):