Чем отличается сортировка с помощью прямого включения от сортировки с помощью прямого обмена?

+1 голос
53 просмотров спросил 21 Март, 14 enginr (111 баллов) в категории Образование и наука

1 Ответ

+1 голос
 
Лучший ответ

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

Число сравнений, при включении i-го элемента в отсортированную часть массива, в среднем равно i/2. Т. к. операция выполняется для каждого из n-1 элементов множества, то алгоритм имеет сложность n² .

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

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

В наилучшем случае число перестановок равно нулю, однако в среднем число перестановок также пропорционально размерности n². Число сравнений для каждого элемента массива, в отличие от прямого включения, постоянно и равно (n²-n)/2.

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

ответил 22 Март, 14 Александра-lab (404 баллов)
выбран 27 Март, 14 enginr


Знаете ответ? Помогите другим! (без регистрации)

Отображаемое имя (по желанию):
Конфиденциальность: Ваш электронный адрес будет использоваться только для отправки уведомлений.
Анти-спам проверка:

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

Похожие вопросы

...