318136
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
+Добавить материал
и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
Дистанционные курсы профессиональной переподготовки и повышения квалификации для педагогов

Дистанционные курсы для педагогов - курсы профессиональной переподготовки от 6.900 руб.;
- курсы повышения квалификации от 1.500 руб.
Престижные документы для аттестации

ВЫБРАТЬ КУРС СО СКИДКОЙ 50%

ВНИМАНИЕ: Скидка действует ТОЛЬКО сейчас!

(Лицензия на осуществление образовательной деятельности № 5201 выдана ООО "Инфоурок")

ИнфоурокИнформатикаДругие методич. материалыЛабораторная работа "Сортировка одномерных массивов"

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

Исходный массив длиной 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. Выполнить сортировку элементов, записанных на нечетных местах

Общая информация

Номер материала: ДБ-107263

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

Вам будут интересны эти курсы:

Курс повышения квалификации «Табличный процессор MS Excel в профессиональной деятельности учителя математики»
Курс повышения квалификации «Современные информационные технологии и их использование в работе преподавателей. Системы автоматизированного проектирования одежды и организация технологического процесса»
Курс повышения квалификации «Организация работы по формированию медиаграмотности и повышению уровня информационных компетенций всех участников образовательного процесса»
Курс профессиональной переподготовки «Информатика: теория и методика преподавания в образовательной организации»
Курс «Фирменный стиль» (Corel Draw, Photoshop)
Курс «WEB-ВЕРСТКА (HTML, CSS)»
Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»
Курс повышения квалификации «Развитие информационно-коммуникационных компетенций учителя в процессе внедрения ФГОС: работа в Московской электронной школе»
Курс повышения квалификации «Введение в программирование на языке С (СИ)»
Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»
Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Современные тенденции цифровизации образования»
Курс повышения квалификации «Специфика преподавания дисциплины «Информационные технологии» в условиях реализации ФГОС СПО по ТОП-50»
Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»
Курс повышение квалификации «Применение интерактивных образовательных платформ на примере платформы Moodle»

Благодарность за вклад в развитие крупнейшей онлайн-библиотеки методических разработок для учителей

Опубликуйте минимум 3 материала, чтобы БЕСПЛАТНО получить и скачать данную благодарность

Сертификат о создании сайта

Добавьте минимум пять материалов, чтобы получить сертификат о создании сайта

Грамота за использование ИКТ в работе педагога

Опубликуйте минимум 10 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Свидетельство о представлении обобщённого педагогического опыта на Всероссийском уровне

Опубликуйте минимум 15 материалов, чтобы БЕСПЛАТНО получить и скачать данное cвидетельство

Грамота за высокий профессионализм, проявленный в процессе создания и развития собственного учительского сайта в рамках проекта "Инфоурок"

Опубликуйте минимум 20 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Грамота за активное участие в работе над повышением качества образования совместно с проектом "Инфоурок"

Опубликуйте минимум 25 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Почётная грамота за научно-просветительскую и образовательную деятельность в рамках проекта "Инфоурок"

Опубликуйте минимум 40 материалов, чтобы БЕСПЛАТНО получить и скачать данную почётную грамоту

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