й шаг алгоритма К этому шагу первые i записей исходного массива уже отсортированы по возрастанию и на рисунк
Работа добавлена на сайт samzan.net:
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, поэтому и минимальное значение вычислительной сложности
2. зеленый светлосерый Коричневый Светлый орех Синий зеленый
3. курсовий проект з дисципліни Автомобільні двигуни Студентові групи
4. В VI веке до н.э. в Греции в составе персидской армии воевали- 2
5. приложений Принятой им Windows NT операционной системы Windows является а com внедрять в MS DOS версии высокий конец выч
6. новая эра общее название совокупности различных мистических течений и движений в основном оккультног
7. ЛЕКЦИЯ 6 ДРЕВНЯЯ ИНДИЯ
8. Правоохранительная деятельность.html
9. Дипломная работа- Психологические особенности профессиональной компетентности муниципальных служащих
10. Практическая энциклопедия бухгалтера1
11. Концепции социальной ответственности
12. тематика 5 Глава 1
13. тематикада физикада механикада т
14. круглые столы посвященные обсуждению перспектив развития партийной системы в России
15. Лабораторная работа 1 Электронные таблицы MS Excel
16. Работа банка АО Банк ТуранАлем в условиях перехода к рыночным отношениям
17. тема предупреждения ликвидации чрезвычайных ситуаций РСЧС Тема- Организация РСЧС ее структура и задачи
18. существует ли зависимость между двумя переменными; 2 носит ли эта зависимость причинный характер; 3 явл
19. ПО ТЕМЕ ldquo;ФУНКЦИИ И ЦИКЛЫrdquo; Условия выбора варианта подгруппа
20. модуль- Базовый курс Позитивной Динамической Психотерапии по окончании выдается Сертификат международного