Методические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "




НазваниеМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
страница2/19
Дата публикации28.09.2013
Размер1.39 Mb.
ТипМетодические указания
vbibl.ru > Информатика > Методические указания
1   2   3   4   5   6   7   8   9   ...   19
^

Метод "пузырька"


Отличие метода "пузырька" от сортировки линейным выбором заключается в том, что вместо поиска наименьшей записи с последующей ее перестановкой две записи меняются местами сразу, как только обнаружится, что между ними нарушена упорядоченность.

В течение первого просмотра (прохода) таблицы сравниваются ключи первой (^ R[1]) и второй (R[2]) записей, и, если порядок между ними нарушен, то записи R[1] и R[2] меняются местами. Затем этот процесс повторяется для записей R[2] и R[3], R[3] и R[4],..., R[n-1] и R[n], причем при выполнении сравнения записи с меньшими ключами будут "всплывать" (то есть перемещаться на позицию с меньшим индексом). В результате первого прохода запись с наибольшим значением ключа "осядет" в позиции n. При втором проходе таблицы сравниваются ключи записей R[1] и R[2], R[2] и R[3],...,R[n-2] и R[n-1]. Запись с наибольшим значением ключа "осядет" в позиции (n-1).

Для сортировки таблицы требуется максимально (n-1) проходов, причем при каждом проходе один "пузырек" располагается на уровне, соответствующем его весу. Рассмотренный алгоритм можно сделать эффективнее, если после каждого прохода выполнять проверку: были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что таблица уже отсортирована, и процесс можно завершить. Кроме того, нужно запоминать не только сам факт, что обмен имел место, но и положение (индекс) последнего обмена. Это позволит уменьшить на следующем шаге просматриваемую часть таблицы.

Характеристики сортировки методом "пузырька" в худшем случае составляют сравнений и перестановок (худшим считается случай, когда записи наиболее удалены от своих конечных позиций). Среднее число сравнений и перестановок пропорционально n2 /2.

Рассмотрим пример сортировки методом "пузырька" (процедура, реализующая метод "пузырька" на языке Паскаль, приведена на рисунке 1):


^ Начальные ключи

Проходы


1

2

3

4

5

15

15

8

8

3

1

23

8

15

3

1

3

8

16

3

1

8

8

16

3

1

15

15

15

3

1

16

16

16

16

1

20

20

20

20

20

20

23

23

23

23

23
1   2   3   4   5   6   7   8   9   ...   19

Похожие:

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница