Сортировка методом простого выбора

Цель работы: Исследовать сортировку массива методом простого выбора и оценить эффективность этого алгоритма.

Сортировка методом простого выбора сводится к следующим шагам:
1. Установить номер наибольшего элемента массива.
2. Поменять местами наибольший и последний элементы массива.
3. Оставив в покое последний элемент, выполнить пункты 1 и 2 над остатком массива (массивом без последнего элемента). Пункт 3 повторять, пока остаток массива не сократится до одного элемента.

Опишем процедуру сортировки на языке проектирования программ (псевдокоде).

Вот как изменяется значение массива из пяти элементов (30,20,10,50,40)

Подчеркнута область поиска наибольшего элемента.

2. Чем отличается сортировка по убыванию от сортировки по невозрастанию?

3. Сформулировать идею сортировки массива методом простого выбора.

4. Почему время выполнения одного шага прямо пропорционально размеру неупорядоченной части массива?

ВНИМАНИЕ!!! Входные данные (исходный массив) и выходные данные (отсортированный массив) формировать в виде текстового файла, содержащего целые числа!

1. Изменить процедуру сортировки так, чтобы сортировка производилась по убыванию элементов.

2. Проверить, является ли данная последовательность целых чисел упорядоченной по убыванию. Если нет, упорядочить ее.

3. Отсортировать данный массив и подсчитать количество уникальных чисел в массиве.

4. Изменить процедуру сортировки так, чтобы значение параметра i с каждым шагом увеличивалось.

5. Отсортировать четные элементы массива с помощью простого выбора.

6. Отсортировать с помощью простого выбора элементы массива, стоящие на нечетных местах.

7. Отсортировать положительные элементы массива с помощью простого выбора.

8. Отсортировать отрицательные элементы массива с помощью простого выбора.

9. В матрице n*m отсортируйте столбцы в порядке возрастания.

10. Даны список футбольных команд высшей лиги России и количество очков, набранных каждой командой в чемпионате России. Известно, что нет команд с равным числом очков. Распечатать список призеров.

11. В неупорядоченном массиве могут быть совпадающие элементы. Из каждой группы одинаковых элементов оставить только один, удалив остальные и «поджав» массив к его началу.

12. Турнирная таблица соревнований представлена квадратной матрицей A, каждый элемент которой aij есть число голов, забитых i-ой командой в ворота j-ой команды. По диагонали расположить место каждой команды (по числу побед за вычетом числа поражений; в случае равенства – по разности забитых и пропущенных голов).

Исследовать сортировку массива методом простого обмена и оценить эффективность этого алгоритма.

Как и предыдущий, этот алгоритм состоит из отдельных шагов. На каждом шаге проходят массив от начала к концу, сравнивая пары соседних элементов. Если очередная пара нарушает требуемый порядок, ее элементы меняют местами. Шаги повторяют до тех пор, пока очередной проход не вызовет ни одного обмена.

Отсортируем по возрастанию методом простого обмена массив из 5 элементов: 5 1 8 4 9. Длина текущей части массива – n-k+i, где k – номер просмотра, i – номер проверяемой пары, п - k – номер последней пары. За вертикальной чертой располагаются отсортированные элементы.

Для самого маленького элемента (2) остается только одно место – первое.

Итак, наш массив отсортирован по возрастанию элементов методом простого обмена. Этот метод также называют методом «пузырька». Название это происходит от образной интерпретации, при которой в процессе выполнения сортировки более «легкие» элементы (элементы с заданным свойством) мало-помалу всплывают на «поверхность».

1. Как поменять местами два элемента массива?

3. В чем сходство и отличие методов простого выбора и простого обмена?

Для всех вариантов предварительно написать процедуру «пузырьковой» сортировки.

1. Подсчитать количество выполненных сравнений и перестановок в лучшем, худшем случаях и в среднем.

2. Упорядочить первые n элементов данного ряда в порядке возрастания. Напечатать эти элементы в порядке убывания.

3. В нашем примере два последних прохода не влияют на порядок элементов, так как они уже отсортированы. Следовательно, можно улучшить наш алгоритм, если запоминать, производились ли перестановки элементов в процессе некоторого прохода. Если их не было, то сортировку можно закончить. Модифицировать процедуру с учетом этой возможности улучшения.

4. Если известен не только факт последнего обмена, но и его место, то нетрудно заметить, что все пары соседних элементов, расположенные правее этого места, уже находятся в нужном порядке. Поэтому просмотр можно закончить на этом индексе, а не продолжать до конца. Модифицировать процедуру с учетом этой возможности улучшения.

5. Написать процедуру «пузырьковой» сортировки по убыванию.

6. Найти второй по величине (после наименьшего) элемент данного ряда.

7. Найти так называемую медиану ряда, т. е. такой его элемент, который больше любого из одной половины элементов и меньше любого из другой (если число элементов ряда четно, следует взять среднее значение из двух значений, обладающих указанным свойством).

8. В методе «пузырьковой» сортировки если какие-то два соседние элементы ряда (например, a[4] и a[5]) не упорядочены, они переставляются, после чего алгоритм предписывает перейти к сравнению следующей пары – a[5] и a[6]. Вместо этого можно попытаться проследить за элементом a[4], дав ему возможность «всплывать» в сторону меньших индексных позиций ряда. Для этого сравним a[4] с a[3]. Если окажется, что a[3] больше, осуществим перестановку и затем сравним a[3] с a[2] и т. д. Осуществить указанный метод.

9. В целочисленном массиве найти наибольшее число одинаковых элементов.

10. Дано n целых чисел. Сколько чисел лежит между данными a и b?

11. Дано n отрезков [a[i], b[i]] на прямой (i=1..n). Найти максимальное k, для которого существует точка прямой, покрытая k отрезками ("максимальное число слоев"). Подсказка. Упорядочим все левые и правые концы отрезков вместе (при этом левый конец считается меньше правого конца, расположенного в той же точке прямой). Далее двигаемся слева направо, считая число слоев. Встреченный левый конец увеличивает число слоев на 1, правый - уменьшает.

12. Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Подсказка. Упорядочим точки по x-координате, а при равных x-координатах - по y-координате. В таком порядке и можно проводить ломаную.

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: