Принцип метода
Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n-й позиции массива будет стоять максимальный элемент («всплыл» первый «пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется n-1 проход.
Пример:
Сравнение прямых методов сортировки
Теоретические и практические исследования алгоритмов прямых методов сортировки показали, что как по числу сравнений, так и по числу присваиваний они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.
Если сравнить рассмотренные прямые методы между собой, то в среднем методы вставки и выбора оказываются приблизительно эквивалентными и в несколько раз (в зависимости от длины массива) лучше, чем метод обмена («пузырька»).
Пример сортировки методом «пузырька»
Const N=100;
Var i, Temp: integer;
A: array[1..N] of integer;
Flag: boolean;
Begin
Randomize;
Writeln('Несортированный массив');
For i:=1 To N Do begin A[i]:=random(50); Write(A[i]:3); end;
Writeln;
Flag:=true;
While Flag Do
Begin
Flag:=false;
For i:=1 To N-1 Do
begin
If A[i]>A[i+1] Then
begin
Temp:=A[i];
A[i]:=A[i+1];
A[i+1]:=Temp;
Flag:=true;
end; {If}
end; {For}
end; {While}
Writeln('Отсортированный массив');
For i:=1 To N Do Write(A[i]:3);
readln;
End.
Порядок выполнения работы
Работа выполняется студентом самостоятельно и состоит из этапов:
1) изучение методических указаний по выполнению лабораторной работы и получение индивидуального задания;
2) составление алгоритма и программы на алгоритмическом языке Pascal;
3) отладка программы;
4) защита лабораторной работы.
Общие требования к программе:
· текст программы представляется в электронном виде и должен включать постановку задачи, сведения об авторе и подробные комментарии;
· названия переменных должны быть логически обоснованны и давать понятие о том, что в них предполагается хранить или обрабатывать;
· программа должна запрашивать входные данные и выводить итоговый результат с пояснениями.
Список заданий
Для выполнения данной лабораторной работы необходимо написать программу на языке Pascal, которая сортирует данные указанным методом.
Программа состоит из следующих этапов:
1. Объявление необходимой области данных (константы, переменные, массивы).
2. Заполнение массивов неупорядоченными данными.
3. Вывод массива с данными.
4. Формирование циклов, в которых выполняется сортировка данных.
5. Вывод массива с данными.
| № варианта | |||||||||||
| Задание | 1A | 1B | 1C | 1D | 1E | 2A | 2B | 2C | 2D | 2E | 3A |
| № варианта | |||||||||||
| Задание | 3B | 3C | 3D | 3E | 1A¯ | 1B¯ | 1C¯ | 1D¯ | 1E¯ | 2A¯ | 2B¯ |
| № варианта | |||||||||||
| Задание | 2C¯ | 2D¯ | 2E¯ | 3A¯ | 3B¯ | 3C¯ | 3D¯ | 3E¯ |
Примечание.
| 1. Методы сортировки: 1 – вставкой; 2 – выбором; 3 – обменом. | 2. Содержимое массива: A – прописные латинские; B – заглавные латинские; С – прописные русские; D – заглавные русские; E – вещественные числа. | 3. Направление сортировки: - по возрастанию; ¯ - по убыванию. |
5. Контрольные вопросы
1. Как объявляются одномерные массивы? Как выполняется доступ к элементам массива?
2. Каким образом можно обойти все элементы двумерного массива?
3. Какого типа данных могут быть элементы массива?
4. Какие строки бывают в языке Pascal?
5. Назовите подпрограммы для работы со строками длиной до 255 символов.
6. В чем состоит принцип методов сортировки вставки, обмена и выбора?
7. Какой метод сортировки эффективнее? Почему?
Список рекомендуемой литературы
1. Немнюгин, С.А. Turbo Pascal: программирование на языке высокого уровня / С.А. Немнюгин. – 2-е изд. – СПб.: Питер, 2006. – 544с.
2. Немнюгин, С.А. Turbo Pascal: практикум / С.А. Немнюгин. – 2-е изд. – СПб.: Питер, 2006. – 272с.
3. Фаронов, В.В. TurboPascal: учебное пособие / В.В. Фаронов. – М.: Изд.: ОМД Групп, 2007. – 368с.
4. Иванова, Г.С. Основы программирования: учебник для вузов / Г.С. Иванова. – 3-е изд., испр. – М.: МГТУ им. Н.Э. Баумана, 2004. – 416с.
5. Марченко, А.И. Программирование в среде Turbo Pascal 7.0. / А.И. Марченко, Л.А. Марченко. – М.: Бином Универсал, К.: ЮНИОР, 1997. – 496с.
6. Культин, Н.Б. Turbo Pascal в задачах и примерах / Н.Б. Культин. – СПб.: БХВ-Петербург, 2007. – 256с.
7. Коффман, Э.М. Turbo Pascal / Э.М. Коффман. – 5-е изд. – М.: Вильямс, 2005. – 896с.
8. Рапаков Г.Г. Программирование на языке Pascal: учебное пособие / Г.Г. Рапаков, С.Ю. Ржеуцкая – СПб.: БХВ-Петербург, 2004. – 480с.
Алгоритмические языки и программирование. Работа с массивами: методические указания к выполнению лабораторной работы №4 для студентов очной формы обучения специальности 230201 – "Информационные системы и технологии".
Сергей Михайлович Рощин
Юрий Алексеевич Леонов
Научный редактор Ю.М. Казаков
Редактор издательства Л.И. Афонина
Компьютерный набор С.М. Рощин
Темплан 2007г., п. 457
| Подписано в печать Формат 60х84 1/16. Бумага офсетная. Офсетная печать. Усл. печ. л. 0,87 Уч. – изд. л. 0,87 Тираж 50 экз. Заказ Бесплатно |
Брянский государственный технический университет.
Брянск, бульвар 50-летия Октября, 7, тел. 58-82-49.
Лаборатория оперативной полиграфии БГТУ, ул. Институтская, 16