Сортировка с помощью прямого выбора.

Метод основан на следующих принципах. Как и в большинстве других подобных алгоритмов, в его основе лежит операция сравнения. Сравнивая каждый элемент с каждым, и в случае необходимости производя обмен, метод приводит последовательность к необходимому упорядоченному виду. Выбирается элемент с наименьшим значением. Он меняется с первым элементом x₁. Затем этот процесс повторяется с оставшимися n -1 элементами, n - 2 элементами и т.д. до тех пор, пока не останется один, самый больший элемент.

Сказанное можно описать следующим образом:

для j от 1 до N-1     выбрать среди M[j],. . ., M[N] наименьший элемент и     поменять его местами с M[j] кц

Сортировка с помощью прямого обмена (метод «пузырька»).

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

Каждый из изложенных выше методов сортировки допускает оптимизацию, основанную на анализе массива (отсортирован или нет), полученного на каждом шаге алгоритма.

Псевдокод сортировки методом пузырька представлен ниже под названием Bubblesort. На его вход подается массив А [1..п], содержащий последователь­ность из п сортируемых чисел (количество элементов массива А обозначено в этом коде как length [A].)

Пример. Составить блок-схему сортировки по неубыванию одномерного целочисленного массива размерности n методом «пузырька» (рис. 1).

Рис. 1. Блок-схема примера.

СОДЕРЖАНИЕ ОТЧЕТА

1. Тема, краткие теоретические сведения.

2. Задание согласно варианту.

3. Блок-схема.

4. Текст программы.

5. Результат работы программы (скриншоты).

6. Выводы.

Варианты заданий.

1. Рассмотрим массив целых чисел а₁,...,a_n. Переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию а₁<=а₂<=...<=a_n. Для решения этой задачи можно использовать следующий алгоритм: последовательным пересмотром чисел а₁,...,a_n найти наименьшее такое, что a_i>a_i+1. а₁,...,a_n Поменять местами a_i и a_i+1, дальше опять начать пересмотр с элемента a_i+1 и т.д. Следующие пересмотры начинать опять, уменьшая количество элементов, которые пересматриваются.

2. Упорядкувати масив А(N) за збільшенням квадратів значень елементів, методом бульбашки.

3. Упорядкувати масив А(N) за збільшенням синусів значень елементів, методом прямого включення.

4. Упорядкувати масив(N) по убуванню косинусів значень елементів, методом прямого вибору.

5. Рассмотрим массив действительных чисел а₁,...,a_n. Переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию а₁<=а₂<=...<=a_n. Для решения этой задачи можно использовать следующий алгоритм: последовательным пересмотром чисел а₁,...,a_n найти наименьшее такое, что a_i>a_i+1. а₁,...,a_n Поменять местами a_i и a_i+1, дальше опять начать пересмотр с элемента a_i+1 и т.д. Следующие пересмотры начинать опять, уменьшая количество элементов, которые пересматриваются.

6. В зависимости от того, образуют элементы заданного массива целых чисел из п элементов строго убывающую, не возрастающую, строго возрастающую, неубывающую последовательность, выдать соответствующее сообщение.

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

8. Ввести одномерный массив из п элементов. Отсортировать массив по неубыванию (невозрастанию) методом прямого выбора.

9. Получить упорядоченный по возрастанию массив С(n + m) путем слияния массивов А(n) и В(m); массивы А(n) и В(m) предварительно упорядочить по возрастанию.

10. Рассмотрим массив действительных чисел а₁,...,a_n. Переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию а₁<=а₂<=...<=a_n. Использовать алгоритм вставки.

11. Дан массив С(n). Поменять знаки на противоположный у всех отрицательных элементов массива, и отсортировать масив по возрастанию.

12. Задан массив А(n) символьных элементов. Отсортировать элементы в обратном алфавитном порядке.

13. Рассмотрим массив целых чисел а₁,...,a_n. Переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию а₁<=а₂<=...<=a_n. Для решения этой задачи можно использовать следующий алгоритм: пересмотреть последовательность а₂,...,a_n и каждый новый элемент a_i включить на то место, которое входит в уже упорядоченную последовательность а₁,...,a_i-1. Это место определяется последовательным сравнением a_i с упорядоченными элементами а₁,...,a_i-1.

14. Нехай задано впорядкований по збільшенню масив дійсних чисел a₁<=a₂<=...<=a_n та деяке число b, для якого потрібно знайти таке місце серед чисел a₁,...,a_n, щоб після вставки числа b на це місце впорядкованість не зруйнувалась. Якщо внаслідок рівності між собою деяких елементів масиву число b можна включити на різні місця, то потрібно визначити місце, яке є найближчим до початку масиву.

15. Упорядкувати масив А(N) по убуванню квадратів значень елементів.

16. Задан массив А(n) символьных элементов. Отсортировать элементы в алфавитном порядке.

17. Дан действительный массив А(n). Упорядочить массив по убыванию, методом пузырька.

18. Задан массив Х(n) целого типа, переменной t присвоить значение true, если элементы массива X упорядочены строго по возрастанию, и значение false иначе.

19. Получить упорядоченный по возрастанию массив С(n + m) путем слияния массивов А(n) и В(m); массивы А(n) и В(m) предварительно упорядочить по возрастанию.

20. Рассмотрим массив целых чисел а₁,...,a_n. Переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию а₁<=а₂<=...<=a_n. Для решения этой задачи можно использовать следующий алгоритм: последовательным пересмотром чисел а₁,...,a_n найти наименьшее такое, что a_i>a_i+1. а₁,...,a_n Поменять местами a_i и a_i+1, дальше опять начать пересмотр с элемента a_i+1 и т.д. Следующие пересмотры начинать опять, уменьшая количество элементов, которые пересматриваются.

21. Задан массив А(n) символьных элементов. Отсортировать элементы в алфавитном порядке.

22. Ввести одномерный массив из п элементов. Отсортировать массив по неубыванию (невозрастанию) методом прямого выбора.

23. Упорядкувати масив А(N) за збільшенням синусів значень елементів, методом прямого включення.

24. Получить упорядоченный по возрастанию массив С(n + m) путем слияния массивов А(n) и В(m); массивы А(n) и В(m) предварительно упорядочить по возрастанию.

25. Дан массив С(n). Поменять знаки на противоположный у всех отрицательных элементов массива, и отсортировать масив по возрастанию.

26. Задан массив А(n) символьных элементов. Отсортировать элементы в обратном алфавитном порядке.

27. Рассмотрим массив целых чисел а₁,...,a_n. Переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию а₁<=а₂<=...<=a_n. Для решения этой задачи можно использовать следующий алгоритм: пересмотреть последовательность а₂,...,a_n и каждый новый элемент a_i включить на то место, которое входит в уже упорядоченную последовательность а₁,...,a_i-1. Это место определяется последовательным сравнением a_i с упорядоченными элементами а₁,...,a_i-1.

28. Упорядкувати масив (N) по убуванню косинусів значень елементів, методом прямого вибору.

29. Задан массив Х(n) целого типа, переменной t присвоить значение true, если элементы массива X упорядочены строго по возрастанию, и значение false иначе.