Сортировка методом простого выбора сводится к следующим шагам:
1. Установить номер наибольшего элемента массива.
2. Поменять местами наибольший и последний элементы массива.
3. Оставив в покое последний элемент, выполнить пункты 1 и 2 над остатком массива (массивом без последнего элемента).
Пункт 3 повторять, пока остаток массива не сократится до одного элемента.
Пример
Опишем процедуру сортировки на языке проектирования программ (псевдокоде).
For i := n downto 2 do
Begin
найти максимальный элемент из а[1], ..., a[i];
запомнить его индекс в переменной k;
если i<>k поменять местами a[i] и a[k];
End;
Вот как изменяется значение массива из пяти элементов (30,20,10,50,40)
30 20 10 50 40
30 20 10 40 50
30 20 10 40 50
10 20 30 40 50
10 20 30 40 50
Подчеркнута область поиска наибольшего элемента.
Контрольные вопросы
1. Что понимается под сортировкой массива?
2. Чем отличается сортировка по убыванию от сортировки по невозрастанию?
3. Сформулировать идею сортировки массива методом простого выбора.
4. Почему время выполнения одного шага прямо пропорционально размеру неупорядоченной части массива?
Варианты заданий
ВНИМАНИЕ!!! Входные данные (исходный массив) и выходные данные (отсортированный массив) формировать в виде текстового файла, содержащего целые числа!
1. Изменить процедуру сортировки так, чтобы сортировка производилась по убыванию элементов.
2. Проверить, является ли данная последовательность целых чисел упорядоченной по убыванию. Если нет, упорядочить ее.
3. Отсортировать данный массив и подсчитать количество уникальных чисел в массиве.
4. Изменить процедуру сортировки так, чтобы значение параметра i с каждым шагом увеличивалось.
5. Отсортировать четные элементы массива с помощью простого выбора.
6. Отсортировать с помощью простого выбора элементы массива, стоящие на нечетных местах.
7. Отсортировать положительные элементы массива с помощью простого выбора.
8.Отсортировать отрицательные элементы массива с помощью простого выбора.
9. В матрице n*m отсортируйте столбцы в порядке возрастания.
10. Даны список футбольных команд высшей лиги России и количество очков, набранных каждой командой в чемпионате России. Известно, что нет команд с равным числом очков. Распечатать список призеров.
11. В неупорядоченном массиве могут быть совпадающие элементы. Из каждой группы одинаковых элементов оставить только один, удалив остальные и «поджав» массив к его началу.
12. Турнирная таблица соревнований представлена квадратной матрицей A, каждый элемент которой aij есть число голов, забитых i-ой командой в ворота j-ой команды. По диагонали расположить место каждой команды (по числу побед за вычетом числа поражений; в случае равенства – по разности забитых и пропущенных голов).
Назад
На главную
Нет комментариев.
Оставить комментарий:
|
