Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Другие методич. материалы / Лабораторная работа "Сортировка одномерных массивов"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Информатика

Лабораторная работа "Сортировка одномерных массивов"

библиотека
материалов

Сортировка одномерных массивов

Цель работы

Изучить алгоритмы сортировки массивов и научиться использовать их при обработке данных.

Задачи лабораторной работы

После выполнения работы студент должен уметь:

  • применять алгоритмы сортировки массивов при обработке данных;

Общие теоретические сведения

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

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

  • метод сортировки выбором; 

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

  • метод сортировки включением.

Метод сортировки выбором

Исходный массив длиной N разбивается на две части: итог и остаток. Участок массива, называемый итогом, располагается с начала массива и должен быть упорядоченным, а участок массива, называемый остатком, располагается вплотную за итогом и содержит исходные числа не отсортированной части исходного массива. 

Текстуальный алгоритм сортировки выбором: 

Шаг 1. Полагается i=0, т.е. считается, что итоговый участок - пуст. 

Шаг 2. В остатке массива ищется минимальный элемент и он меняется местом с первым элементом остатка (i-ым элементом массива). После чего значение i увеличивается на единицу, тем самым расширяя итоговый участок массива ( отсортированную часть исходного массива). 

Шаг 3. Если i < N, то повторяется Шаг 2. В противном случае - конец алгоритма, т.к. итог становится равным всему массиву. 

Конец алгоритма. 

Схема алгоритма методом сортировки выбора представлена на рис. 1.

 

hello_html_322e2d2b.png

Рисунок 1. Схема алгоритма сортировки методом выбора 

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

Аналогично, как и в методе выбора, исходный массив длиной N разбивается на две части: отсортированную (итог) и не отсортированную (остаток). Первый элемент остатка является  i-ым элементом массива. 

Текстуальный алгоритм сортировки пузырьком:

Шаг 1. Пусть k=N-1 , т.е. итоговый участок состоит из одного элемента. 

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

Шаг 3. После того, как первый элемент остатка переместился в итоговый участок, уменьшается на единицу значение переменной k, тем самым увеличивая отсортированную часть массива. Если k>0, то управление передается на Шаг 2, в противном случае - работа алгоритма завершена. 

Конец алгоритма. 

Схема алгоритма методома сортировки пузырька представлена на рис. 2.

hello_html_762d96ac.png

 Рисунок 2. Блок-схема алгоритма сортировки методом пузырька

Метод сортировки включением

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

Текстуальный алгоритм методом включением:

Шаг 1. Пусть i=1 , т.е. итоговый участок состоит из одного элемента. 

Шаг 2. Берется первый элемент остатка и перемещается в отсортированную часть массива так, чтобы итоговый участок остался упорядоченным. 

Шаг 3. После того, как первый элемент остатка переместился в итоговый участок, увеличивается на единицу значение переменной i, тем самым увеличивая отсортированную часть массива. Если i < N, то управление передается на Шаг 2, в противном случае - работа алгоритма завершена. 

Конец алгоритма.

Схема алгоритма методом сортировки включением представлена на рис. 3.

hello_html_34386099.png

 Рисунок 3. Блок-схема алгоритма прямым включением

Задание:

Используя один из изученных алгоритмов сортировки, составить программы на Паскале, в тетрадь записать листинг программы и блок-схему.

Для помощи в составлении и отладке программ можно самостоятельно за своим рабочим местом просмотреть видеоматериалы (Student \ Шалыгина Т.С.\ 337 \ Теория Алгоритмов \ Сортировка массивов).

  1. Выполнить сортировку только четных элементов массива (нечетные элементы остаются на своих местах).

  2. Выполнить сортировку элементов, записанных на нечетных местах

Автор
Дата добавления 01.06.2016
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров595
Номер материала ДБ-107263
Получить свидетельство о публикации

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru

Похожие материалы

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