У вас вопросы?
У нас ответы:) SamZan.net

й шаг алгоритма К этому шагу первые i записей исходного массива уже отсортированы по возрастанию и на рисунк

Работа добавлена на сайт samzan.net: 2015-07-10

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 28.4.2025

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, поэтому и минимальное значение вычислительной сложности




1. наука главная редакция восточной литературы МОСКВА 1982 4И Древнеиндийск
2. LEGISLTIVE JUDICIL ND EXECUTIVE BRNCHES IN THE US The Legisltive Brnch The US is presidentil republic
3. а Федеральный закон 151ФЗ от 17
4. Реферат- Этические проблемы искусственного оплодотворения
5. ВВЕДЕНИЕ Современная телекомуникационная аппаратура вычислительные и радиотехнические комплексы треб
6. Liebe Flugg~ste Sie m~ssen ds Ruchen einstellen und sich nschnllen
7. ЛАБОРАТОРНАЯ РАБОТА 60 РЕГИСТРАЦИЯ ПОТЕНЦИАЛА ФОТОСИНТЕЗА НА РАСТЕНИИ Цель работы ознакомит
8. Производственный цикл изготовления сварных конструкций
9. Фридерик Шопен
10. Контрольная работа ’ 1.html