Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Сравнение прямых методов сортировки.

Выводы:

1. Все прямые методы сортировки порядка О(n²), т.к. Т(n)» C n² в худшем случае.

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

3. Сортировка выбором никак не реагирует на упорядоченность элементов. Поэтому рекомендуется: в случае почти упорядоченной совокупности использовать сортировку Включением.

4. При небольших n затраты временные во всех трёх методах практически одинаковые. Из-за простоты метода лучше всего запоминается и часто используется именно метод Обменной сортировки.

Cортировка сложных данных

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

Для данных сложных типов не определены операции отношения, поэтому (если они определены в самой задаче) проверки типа if a [j] > a [j+1] { ….} оформляются в процедурах или функциях. Например, функция P(a,b) возвращает true, если a > b. Тогда указанный фрагмент запишется if (P(a [j], a [j+1])) { …}

В случае сортировки по значениям упорядочивающей функции f(x) рекомендуется сформировать вектор значений упорядочивающей функции U = {f(a ₁), f(a ₂), …,f(a _n)}. Сравнения элементов в описанных алгоритмах заменяются сравнением значений упорядочивающей функции, но переставлять в этом случае необходимо и сами элементы и значения упорядочивающей функции. Например, фрагмент пузырьковой сортировки запишется так

if (u [j] > u [j+1]) { u [j] Û u [j+1]; а [j] Û a [j+1]};

При сортировке сложных данных часто, чтобы не переставлять элементы в совокупности и значения упорядочивающей функции, применяют алгоритмы сортировки с использованием вектора индексов. Для этого заводят специальный вектор, назовём его Ind: помещают в Ind индексы элементов 1, 2, 3, …,n. В алгоритмах сортировки вместо перестановки элементов и значений упорядочивающей функции переставляют их индексы. Однако, необходимо помнить в этом случае, что доступ к элементам совокупности и значениям упорядочивающей функции выполняется через вектор индексов:

a [ Ind[j] ] вместо a [j], u [ Ind [j] ] вместо u [ j ]

if (a[ Ind[j] ] >a[ Ind[j+1] ]) { Ind[j] ÛInd[j+1] }

if (u [ Ind [j] ]> u [ Ind [j+1] ]) { Ind[j] ÛInd[j+1] }