Решение: Создаем одномерный случайный массив с числом элементов

Скачать 35.22 Kb.

Название	Решение: Создаем одномерный случайный массив с числом элементов
Дата публикации	14.05.2014
Размер	35.22 Kb.
Тип	Решение

literature-edu.ru > Информатика > Решение

Информатика-3 Вариант 8

Задание №1. Сортировка простым обменом (метод пузырька).
Постановка задания:

Составить программу сортировки целочисленного массива методом простого обмена (метод пузырька).

Условие задания: Размерность сортируемого массива: n = 10, n = 40, n = 160.
Решение:
Создаем одномерный случайный массив с числом элементов

n1 = 10 - a1:array[1..n1] of integer;

Например, создание случайного массива из 10 целых чисел выглядит так:

randomize;

end;
Создаем одномерный случайный массив с числом элементов

n2 = 40 – a2:array[1..n2] of integer;

Создание случайного массива из 40 и более целых чисел выглядит так же, как в предыдущем пункте, но меняются обозначения самих массивов и количество элементов.

Создаем одномерный случайный массив с числом элементов n3 = 160 – a3:array[1..n3] of integer;

Создание этого массива аналогично предыдущему.

Методом пузырька сортируем первый массив;

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

Например, сортировка происходит по следующей схеме:

writeln('Сортировка первого массива n=10');

end;

Методом пузырька сортируем второй массив;

Сортировка аналогична предыдущему пункту.
Методом пузырька сортируем третий массив;

Сортировка аналогична предыдущему пункту.
Результаты работы программы показаны в таблице:

Вопрос: как соотносится зависимость среднего числа обменов от размерности сортируемого массива с теоретической оценкой, приведенной в

учебном пособии?
Ответ:
Сортировка простыми обменами, сортировка пузырьком — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
Наихудший случай: Число обменов равно (N-1)*N/2;

Наилучший случай (на вход подаётся уже отсортированный массив): Число обменов равно 0.

Приложение

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

program zadanie36;

uses crt;

END.
Скриншот программы

Добавить документ в свой блог или на сайт

Похожие:

	Решение задач 141-153 из учебника 99 Решение задач 154-165 из учебника... Издание разработано при поддержке Отдела теории алгоритмов и математических основ кодирования Вычислительного центра им. А. А. Дородницына...		Памяти Леонарда Андреевича Растригина Гринченко С. Н. ( sng @ kynosoft ru ) Случайный поиск, адаптация и эволюция: от моделей биосистем к языку представления о мире. Часть 1
	Решение тестовых задач по математике Разработка методических рекомендаций обусловлена тем, что самым трудным для ученика является решение задач, а также оформление этого...		Методика преподавания элементов теории вероятности в общеобразовательной... Особенности изучения элементов теории вероятности и математической статистики в общеобразовательной средней школе
	Литература не меняется в один день. С середины 10 гг по серед. 30х.... Эйфория после революции октябрьской. Революции у нас были с минимальным числом жертв		Тема: «Использование развивающих игр Никитиных, элементов триз в... Тема: «Использование развивающих игр Никитиных, элементов триз в интеллектуальном развитии дошкольников»
	Книга представляет собой пособие по изучению языка программирования... Книга представляет собой пособие по изучению языка программирования C#, который является одним из важных элементов платформы Microsoft....		Книга "Книга единобожия", автор Мухаммад ибн Сулейман ат-Тамими,... Музыкальный альбом "Музыка белых", автор Музыкальная группа Order, решение вынесено Первомайским районным судом г. Омска от 23. 11....
	Литература зачёт №1 7 класс былины. Самостоятельная работа Б организация отдельных элементов, частей и эпизодов художественного произведения		Криптоанализ блочного шифра KeyLoq Об ожидаемом числе циклов случайного преобразования Известно, что количество преобразований с заданным числом циклов равно числу Стирлинга первого рода. Ожидаемое число циклов -мерного...

Литература