Составь программу, сортирующую данный список по возрастанию вставками:
1-8, -79, -68, -128, -33, 26, -
30, -57, -99, 19, -80, -97,11,
75,3 .
На какой итерации по внешнему циклу достигается нужный результат?
Например, на таком списке:
[35, 73, 75,
-146, -42, 19, -95, -54, 9, 65, -136, 25, 7, -59, 951
35 73 -146 -42 19 -95 -54 9 65 -136 25 7 -59 75 95
35 -146 -42 19-95 -54 9 65 -136 25 7 -59 73 75 95
146 -42 19 -95 -54 9 35 -136 25 7 -59 65 73 75 95
146 -42 -95 -54 9 19 -136 25 7 -59 35 65 73 75 95
146 -95 -54 -42 9 -136 19 7 -59 25 35 65 73 75 95
146-95 -54 -42 -136 9 7 -59 19 25 35 65 73 75 95
146-95 -54 -136 -42 7 -59 9 19 25 35 65 73 75 95
146 -95 -136 -54 -42 -59 7 9 19 25 35 65 73 75 95
146 -136 -95 -54 -59 -42 7 9 19 25 35 65 73 75 95
146-136 -95 -59 -54-42 7 9 19 25 35 65 73 75 95
146 -136 -95 -59 -54 -42 7 9 19 25 35 65 73 75 95
146 -136 -95 -59 -54 -42 7 9 19 25 35 65 73 75 95
146-136 -95 -59 -54 -42 7 9 19 25 35 65 73 75 95
146 -136 -95 -59 -54 -42 7 9 19 25 35 65 73 75 95
Давайте разберем, как работает алгоритм сортировки вставками (insertion sort) на вашем примере и выясним, на какой итерации внешнего цикла он достигнет нужного результата для данного списка чисел.
### Алгоритм сортировки вставками
Сортировка вставками организована следующим образом:
1. Мы начинаем с первого элемента, предполагая, что он уже отсортирован.
2. Затем берем следующий элемент и вставляем его на правильную позицию относительно уже отсортированных элементов.
3. Продолжаем этот процесс, пока не пройдем весь список.
### Пример
Заданный список:
```
1, 8, -79, -68, -128, -33, 26, -30, -57, -99, 19, -80, -97, 11, 75, 3
```
### Шаги алгоритма:
1. Начнем с элементом `1`. Это наш первый отсортированный элемент.
```
[1], 8, -79, -68, -128, -33, 26, -30, -57, -99, 19, -80, -97, 11, 75, 3
```
2. Вставляем `8`. Он больше `1`, остается на месте.
```
[1, 8], -79, -68, -128, -33, 26, -30, -57, -99, 19, -80, -97, 11, 75, 3
```
3. Берем `-79`: это меньше, чем `1`, ставим его на первое место.
```
[-79, 1, 8], -68, -128, -33, 26, -30, -57, -99, 19, -80, -97, 11, 75, 3
```
4. Далее `-68`: помещаем между `-79` и `1`.
```
[-79, -68, 1, 8], -128, -33, 26, -30, -57, -99, 19, -80, -97, 11, 75, 3
```
5. Вставляем `-128`: он становится первым элементом.
```
[-128, -79, -68, 1, 8], -33, 26, -30, -57, -99, 19, -80, -97, 11, 75, 3
```
6. Вставляем `-33`: его место между `-68` и `1`.
```
[-128, -79, -68, -33, 1, 8], 26, -30, -57, -99, 19, -80, -97, 11, 75, 3
```
7. `26` больше `8`, остается на месте.
```
[-128, -79, -68, -33, 1, 8, 26], -30, -57, -99, 19, -80, -97, 11, 75, 3
```
8. `-30`: вставляется перед `1`.
```
[-128, -79, -68, -33, -30, 1, 8, 26], -57, -99, 19, -80, -97, 11, 75, 3
```
9. `-57`: вставляется перед `-33`.
```
[-128, -79, -68, -57, -33, 1, 8, 26], -99, 19, -80, -97, 11, 75, 3
```
10. `-99`: становится первым элементом.
```
[-99, -128, -79, -68, -57, -33, 1, 8, 26], 19, -80, -97, 11, 75, 3
```
11. `19`: вставляется после `8`.
```
[-99, -128, -79, -68, -57, -33, 1, 8, 19, 26], -80, -97, 11, 75, 3
```
12. `-80`: вставляется перед `-79`.
```
[-99, -128, -80, -79, -68, -57, -33, 1, 8, 19, 26], -97, 11, 75, 3
```
13. `-97`: вставляется между `-99` и `-128`.
```
[-99, -128, -97, -80, -79, -68, -57, -33, 1, 8, 19, 26], 11, 75, 3
```
14. `11`: вставляется между `8` и `19`.
```
[-99, -128, -97, -80, -79, -68, -57, -33, 1, 8, 11, 19, 26], 75, 3
```
15. `75`: вставляется между `26` и `-`.
```
[-99, -128, -97, -80, -79, -68, -57, -33, 1, 8, 11, 19, 26, 75], 3
```
16. `3`: вставляется между `1` и `8`.
```
[-99, -128, -97, -80, -79, -68, -57, -33, 1, 3, 8, 11, 19, 26, 75]
```
### Итоги
Итак, весь список отсортирован на 16 итерации внешнего цикла. Каждый элемент проходил путь для поиска своего места среди уже отсортированных элементов.
Таким образом, ответ: **16 итерация внешнего цикла приводит к получению отсортированного списка.**
