DjangoBB LoFi version

Полная версия: Подсчет индекса Сортировки вставками

Начало » Центр помощи » Подсчет индекса Сортировки вставками

doketor

Фев. 27, 2021 10:06:16

Всем привет!
Помогите пожалуйста решить задачу.
“Дан массив целых чисел. Ваша задача — отсортировать его в порядке неубывания с помощью сортировки вставками.

Сортировка вставками проходится по всем элементам массива от меньших индексов к большим («слева направо») для каждого элемента определяет его место в предшествующей ему отсортированной части массива и переносит его на это место (возможно, сдвигая некоторые элементы на один индекс вправо). Чтобы проконтролировать, что Вы используете именно сортировку вставками, мы попросим Вас для каждого элемента массива, после того, как он будет обработан, выводить его новый индекс.”

Саму сортировку я сделал, но сложность в том что необходимо вывести новый цикл. И обязательно что бы отсчет начинался с 1, а не с 0:

Пример:

input.txt output.txt
10 1 2 2 2 3 5 5 6 9 1
1 8 4 2 3 7 5 6 9 0 0 1 2 3 4 5 6 7 8 9

Если прописывать for i in range (1, len(list)), то получается:
1 1 1 2 4 4 5 8 9
0 1 2 3 4 5 6 7 8 9
Если оставлять только длину списка for i in range(len(list)), то получается:
0 1 1 1 2 4 4 5 8 9
0 1 2 3 4 5 6 7 8 9
А нужно что бы было как в примере иначе не проходит проверку.

PEHDOM

Фев. 27, 2021 13:13:20

doketor
Пример:

input.txt output.txt
10 1 2 2 2 3 5 5 6 9 1
1 8 4 2 3 7 5 6 9 0 0 1 2 3 4 5 6 7 8 9

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

doketor
Чтобы проконтролировать, что Вы используете именно сортировку вставками, мы попросим Вас для каждого элемента массива, после того, как он будет обработан, выводить его новый индекс.”

в каком виде это должно быть сделано?

doketor
И обязательно что бы отсчет начинался с 1, а не с 0:

зачем?

 def sort_insert(lst):
    for i in range (len(lst)):
        for j in range(i):
            if lst[i] < lst[j]:
                print('move {} from index {} to {}'.format(lst[i], i, j))
                lst.insert(j, lst.pop(i))
      
in_data = [10, 1, 2, 2, 2, 3, 5, 5, 6, 9, 1]
sort_insert(in_data)
print(in_data)
>>> 
move 1 from index 1 to 0
move 2 from index 2 to 1
move 2 from index 3 to 2
move 2 from index 4 to 3
move 3 from index 5 to 4
move 5 from index 6 to 5
move 5 from index 7 to 6
move 6 from index 8 to 7
move 9 from index 9 to 8
move 1 from index 10 to 1
[1, 1, 2, 2, 2, 3, 5, 5, 6, 9, 10]
>>>

или я чтото не так понял?

doketor

Фев. 27, 2021 13:40:35

doketor
input.txt
10
1 8 4 2 3 7 5 6 9 0
output.txt
0 1 2 3 4 5 6 7 8 9
1 2 2 2 3 5 5 6 9 1

извиняюсь текст слипся

PEHDOM
зачем?

Не пропускает программа в случае если начинается с 0.

Вот сама задача.

Дан массив целых чисел. Ваша задача — отсортировать его в порядке неубывания с помощью сортировки вставками.

Сортировка вставками проходится по всем элементам массива от меньших индексов к большим («слева направо») для каждого элемента определяет его место в предшествующей ему отсортированной части массива и переносит его на это место (возможно, сдвигая некоторые элементы на один индекс вправо). Чтобы проконтролировать, что Вы используете именно сортировку вставками, мы попросим Вас для каждого элемента массива, после того, как он будет обработан, выводить его новый индекс.

Формат входного файла
В первой строке входного файла содержится число n — число элементов в массиве. Во второй строке находятся n различных целых чисел, по модулю не превосходящих .

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

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

PEHDOM

Фев. 27, 2021 15:46:44

 def sort_insert(lst):
    indexes=[]
    for i in range (len(lst)):
        for j in range(i+1):
            if lst[i] < lst[j]:
                lst.insert(j, lst.pop(i))
                indexes.append(j+1)
                break
        else:
            indexes.append(j+1)
    return indexes
in_data = [1, 8, 4, 2, 3, 7, 5, 6, 9, 0]
res = sort_insert(in_data)
print(in_data)
print(res)
>>> 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 2, 2, 3, 5, 5, 6, 9, 1]
>>>

привести входные/выходные данные в требуемый вид , сможете самостоятельно?