Определение сортировки выбора и сортировки вставкой

Question

Я прочитал несколько статей о том, как работают сортировка по выбору и сортировка вставками, и, кажется, я понимаю их реализацию.Сортировка выбора перебирает несортированные числа во внутреннем цикле, тогда как сортировка вставок перебирает отсортированные числа во внутреннем цикле.Из того, что я понимаю, это, по сути, единственное отличие.

Мой вопрос заключается в сценарии, в котором вы задаете входной массив, допустим, он такой:

Input Array: 30, 70, 40, 60, 50

Теперь выВам дан дополнительный список, где показаны итерации:

30, 70, 40, 60, 50
30, 40, 70, 60, 50
30, 40, 50, 60, 70
30, 40, 50, 60, 70

Как определить, была ли использована сортировка вставкой или сортировка выбора на основе ТОЧНО этого?Код не указан, и мы не обязаны писать какой-либо код.Нам нужно только выбрать, какой алгоритм был использован из списка с множественным выбором.(Да, оба появляются в списке).

Для ясности, это не вопрос назначения.Однако этот помогает мне с подготовкой к экзамену.

Answer 1

После разговора с лектором по электронной почте у меня есть решение этого вопроса.Это действительно сортировка выбора, поэтому элементы меняются местами.(См. https://en.wikipedia.org/wiki/Selection_sort).

Теперь для объяснения:

Выбор сортировки:

Input Array: 30, 70, 40, 60, 50

Сортировка:

30, 70, 40, 60, 50 // 30 is already sorted.
30, 40, 70, 60, 50 // Swap 40 and 70.
30, 40, 50, 60, 70 // Swap 70 and 50.
30, 40, 50, 60, 70 // Array is sorted.

Вот как это выглядиткак для сортировки вставкой:

Input Array: 30, 70, 40, 60, 50

Сортировка:

30, 70, 40, 60, 50 // 30 is inserted.
30, 70, 40, 60, 50 // 70 is inserted.
30, 40, 70, 60, 50 // 40 is inserted.
30, 40, 60, 70, 50 // 60 is inserted.
30, 40, 50, 60, 70 // 50 is inserted. 
Array is now sorted.

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

Answer 2

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

сортировка выбора:

Sorted         | Unsorted
               | 30 70 40 60 50
30             | 70 40 60 50    # selects 30, the minimum unsorted element
30 40          | 70 60 50       # selects 40
30 40 50       | 70 60          # selects 50
30 40 50 60    | 70             # selects 60
30 40 50 60 70 |                # selects 70

сортировка вставки:

Sorted         | Unsorted
               | 30 70 40 60 50
30             | 70 40 60 50    # inserts 30, the first unsorted element
30 70          | 40 60 50       # inserts 70
30 40 70       | 60 50          # inserts 40
30 40 60 70    | 50             # inserts 60
30 40 50 60 70 |                # inserts 50

Массивы, перечисленные в каждой итерации, будут объединением отсортированных и несортированных частей массива.Похоже, что эти итерации не показывают ни сортировку выбора, ни сортировку вставкой.