Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
26.
Алгоритмы сортировки выбором
1
Алгоритм простого выбора
Этот алгоритм является непосредственной реализацией идеи сортировки выбором: из ещё не отсортированных записей выбирается минимальная (максимальная) и добавляется последней (первой) к уже отсортированным записям.
На рис. 1 схематично представлен i-й шаг алгоритма. К этому шагу первые i записей исходного массива уже отсортированы по возрастанию и на рисунке помечены серым цветом. Среди оставшихся (n – i) записей k(j), j = i, …, n, необходимо выбрать минимальный элемент и сохранить его индекс во вспомогательной переменной temp. С этой целью переменной temp присваивается значение i. Затем последовательно сравниваются k(j), j = i + 1, …, n – 1, со значением k(temp). В случае если k(j) < k(temp), переменной temp присваивается значение j. Шаг алгоритма завершается перестановкой местами элементов k(i) и k(temp).
Пример работы алгоритма сортировки простым выбором последовательности 6, 1, 8, 2, 5, 3, хранящейся в массиве, представлен на рис. 2.
Реализация на языке С++ алгоритма сортировки простым выбором на примере хранящихся n записей типа T в массиве k представлена в листинге 1. Комментарии в правой части листинга содержат число выполнения соответствующей строки алгоритма и поясняют определение его вычислительной сложности. В формулах через ui обозначено число записей k(j), j = i – 1, i – 2, ..., 0, которые больше записи k(i), то есть составляют с ней инверсию.
Листинг 1. Алгоритм сортировки простым выбором
template <typename T>
void SortSelect(T * k, int n) {
int temp, i, j; T work;
for (i = 0; i < n - 1; ++i) { // n – 1
temp = i; // n – 1
for (j = i + 1; j < n; ++j) // 10)(niin
if (k[j] < k[temp]) // 10)(niin
temp = j; // 11niiu
work = k[i]; // n – 1
k[i] = k[temp]; // n – 1
k[temp] = work; // n – 1
}
}
Вычислительная сложность алгоритма
Вычислительная сложность алгоритма сортировки простым выбором равна
Если исходный файл упорядочен, то ui = 0 для всех i, поэтому и минимальное значение вычислительной сложности