Сортировка простым выбором

П.В. Лекомцев

Сортировка в MASM32

Методические указания к выполнению лабораторной работы №1

по дисциплине «Основы вычислительной техники»

Ижевск 2008

УДК

Рецензент: С.А.Трефилов, канд. техн. наук, доцент

Зав. кафедрой: Ю.В.Турыгин, докт. техн. наук, профессор

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

ã Издательство ИжГТУ, 2008

Содержание

Цель работы

Задание на лабораторную работу

Содержание отчета

Алгоритмы сортировок

Список рекомендуемой литературы

Приложение А. Варианты индивидуальных заданий

Приложение B. Пример программы в MASM32

Цель работы

Целью данной лабораторной работы является освоение навыков программирования на языке Assembler для Win32, в частности изучения команд работы с массивами данных и реализации простейших алгоритмов сортировок.

Задание на лабораторную работу

Разработать алгоритм и программу сортировки элементов массива в соответствии с индивидуальным заданием на языке Assembler для Win32. Ввод и вывод осуществить в диалоговом окне Windows. Варианты заданий приведены в Приложении A.

Содержание отчета

1. Титульный лист
2. Задание на лабораторную работу
3. Введение
4. Разработка схемы алгоритма решения задачи
5. Разработка программы
6. Результаты вычислительного эксперимента
7. Выводы
8. Список литературы

Алгоритмы сортировок

Сортировка простыми включениями

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность a ₁ ,…, a _­i-1 и входную последовательность a _i ,…, a _­n. На каждом шаге, начиная с i=2 и увеличивая i на единицу, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.

Рисунок 1 – Пример сортировки простыми включениями

Сортировка простым выбором

Этот метод основан на следующем правиле:

1. Выбирается наименьший элемент.

2. Он меняется местами с первым элементом a₁

Эти операции затем повторяются с оставшимися n-1 элементами, затем с n-2 элементами, пока не останется только один элемент – наибольший.

Рисунок 2 – Пример сортировки простым выбором

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

Данный метод сортировки основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы.

Рисунок 3 – Пример сортировки методом пузырька

Список рекомендуемой литературы

1. В.Ю. Пирогов ASSEMBLER. Учебный курс.- М.: Издатель Молгачева С.В., Издательство Нолидж, 2001. - 848 с

2. В.И. Юров Assembler. Учебник для вузов. 2-ое изд. – СПб.: Питер, 2004. – 637 с.

3. В.Ю. Пирогов Ассемблер для Windows. -2-ое изд., перераб. и доп. – СПб.: БХВ – Петербург, 2003.-656 с.

Приложение А

Варианты индивидуальных заданий

	Начало сортировки	Конец сортировки	Элементы сортировки	Порядок	Метод
A	B	C	D	E
	k-й	h-й	все	По возр.	простыми включениями
	k-й отриц.	h-й отриц.	отриц.	По убыв.	простым выбором
	k-й полож.	h-й полож.	полож.		простым обменом
	k-й = 0	h-й = 0	не = 0
	k-й не = 0	h-й не = 0	простой
	k-й простой	h-й простой	четный
	k-й четный	h-й четный	нечетн.
	k-й нечетн.	h-й нечетн.	крат. 3
	k-й крат. 3	h-й крат. 3	крат. 4
	k-й крат. 4	h-й крат. 4	крат. 5
	k-й крат. 5	h-й крат. 5	крат. 6
	k-й крат. 6	h-й крат. 6	крат. 7
	k-й крат. 7	h-й крат. 7	пред. 2n
	k-й пред. 2n	h-й пред. 2n	пред. 3n
	k-й пред. 3n	h-й пред. 3n	пред 22n
	k-й пред 22n	h-й пред 22n	пред. P2
	k-й пред. P2	h-й пред. P2	менш. сосед.
	k-й менш. сосед.	h-й менш. сосед.	болш. cосед.
	k-й болш. сосед.	h-й болш. cосед.	менш. суммы сосед.
	k-й менш. суммы сосед.	h-й менш. суммы сосед.	болш. суммы сосед.
	k-й болш. суммы сосед.	h-й болш. суммы сосед.

Пример:

Задание: A1B1C2D1E1, N=20

Исходный массив:

-2

-4

-1

-6

-6

-1

-7

-1

Алгоритм:

-2

-4

-1

-6

-6

-1

-7

-1

Массив после сортировки:

-2

-7

-6

-6

-4

-1

-1

-1

Приложение B