Блог

Недавно я снова начал изучать алгоритмы сортировки, и мне было интересно, какая категория алгоритмической парадигмы лучше описывает insertion sort . Я исследовал Интернет, чтобы связать сортировку по вставке с определенной парадигмой, однако я не смог найти определенного ответа. Для других алгоритмов сортировки, таких как quicksort или mergesort , ответ очень очевиден, т.е. Divide and Conquer парадигма. Единственные данные, которые я смог найти для сортировки по вставке, гласят, что у нее «инкрементный подход«. Однако я не смог найти конкретную парадигму, касающуюся инкрементного подхода. Я был бы очень признателен, если кто-нибудь сможет прояснить их определение и объяснить это мне.

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

Как это связано с сортировкой по вставке, так это то, что при сортировке по вставке, скажем, мы планируем отсортировать массив до позиции «j», когда мы достигнем этой конкретной позиции, алгоритм сортировки по вставке отсортирует подмассив A [1 … j — 1], а затем мы вставляем единственный элемент A [ j] на свое место, получая отсортированный подмассив A [1 … j].