Размещение путем сравнения и обмена

 

 

Методические рекомендации к выполнению практических работ

по дисциплинам «Метрология, стандартизация и сертификация» и «Метрология и сертификация» для студентов технических вузов различных направлений подготовки и всех форм обучения

 

Заведующий кафедрой

Н. Сапожников

“ ” 2012 г.

Методические указания

На САМОСТОЯТЕЛЬНОЕ занятие № 1

по Программированию

Класс ________ Дата и время

Место проведения: класс ПК

Тема: Изучение методов сортировки массивов. Сортировка вставкой.

Цели:

Закрепление и углубление теоретических знаний.

Выработка навыков организации обработки массивов в программах.

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

 

План проведения

самостоятельнгого занятия № 1

по дисциплине «Программирование»

 

Вводная часть

Ознакомление с принципами и алгоритмами сортировки массивов методом вставки.

Основная часть

Разработка программ сортировки массива.

Заключительная часть

В результате проведения практического занятия студенты должны

ЗНАТЬ:

- формат объявления одномерного и двухмерного массивов;

- инициализация массива;

- организация ввода и вывода массива;

- метод сортировки вставкой.

УМЕТЬ:

- правильно организовывать в программах обработку массива

 

организационно-методические указания

По проведению

САМОСТОЯТЕЛЬНОГО занятия № 1

Вводная теоретическая часть

Формально процессом сортировки называют операцию упорядочения некоторого множества по ключу или ключам.

Алгоритмы сортировки имеют большое прикладное значение. Эта достаточно глубоко исследованная область информатики используется в информационно-поисковых системах, в военном и банковском деле.

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

Чем меньше элементарных шагов требуется для сортировки одного и того же множества, тем лучше алгоритм.

Сортировка вставками. Общая характеристика метода

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

Сортировку вставками рассмотрим на примере следующей неупорядоченной последовательности элементов: {38, 12, 80, 15, 36, 23, 74, 62}.

Методику сортировки иллюстрирует рис. 1, где (для каждого этапа) справа указан очередной элемент, а стрелкой сверху отмечено место перемещения (при необходимости) этого элемента.

 

↓

1-й этап 38 12 80 15 36 23 74 62

 

2-й этап 12 38 80 15 36 23 74 62

↓

3-й этап 12 3880 15 36 23 74 62

↓

4-й этап 12 15 3880 36 23 74 62

↓

5-й этап 12 15 363880 23 74 62

↓

6-й этап 12 15 23 36 38 80 74 62

↓

7-й этап 12 15 23 36 38 7480 62

 

12 15 23 36 38 62 74 80

 

Рис. 1. Сортировка массива методом вставок

 

Вначале упорядоченная последовательность состоит из первого элемента 38. Рассматриваем элемент 12 – первый из неупорядоченной последовательности. Он меньше 38, поэтому ставится на его место, а 38 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 12, 38. Рассматриваем первый элемент неупорядоченной последовательности – 80. Он больше всех элементов упорядоченной последовательности и остается на своем месте. На третьем этапе упорядоченная последовательность состоит из 12, 38, 80, рассматриваемый элемент 15. Место, куда перемещается рассматриваемый элемент, указано стрелкой (↓), элементы упорядоченной последовательности, смещаемые вправо, подчеркнуты. Подобным образом последовательность меняется до тех пор, пока не станет упорядоченной (это достигается на седьмом этапе). Иными словами, алгоритм сортировки массива а методом вставок выглядит следующим образом:

 

нцдля i от 2 до n

Разместить элемент a[i] на соответствующем ему

месте в предшествующей последовательности

кц

 

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

1. Можно последовательно сравнивать рассматриваемый элемент с элементом, расположенным слева от него, и обменивать их местами до тех пор, пока слева от перемещаемого элемента не окажется элемент, меньший или равный ему. Такой способ будем называть «сравнение и обмен» (в [3] он называется «просеивание»).
2. Можно также сначала определить место, соответствующее рассматриваемому элементу в упорядоченной последовательности, а затем разместить его в этой ячейке, сместив соответствующие элементы на одну позицию вправо, как это показано на рис. 1. Эту разновидность размещения назовем «поиск места и вставка». Рассмотрим процедуры, соответствующие этим вариантам.

 

Размещение путем сравнения и обмена

Действия по размещению некоторого элемента, соответствующие этому варианту, могут быть оформлены в виде следующих команд (i – начальный индекс перемещаемого элемента, j – индекс, который этот элемент имеет в ходе перемещения):

 

если а [i]<a[i-1] |Если нужно перемещать i-й элемент

то

j:=i

нц

| Swap(a[j],a[j-1]) |Смещаем его влево путем обмена

| j:=j-1 |Новый индекс перемещаемого элемента

кцпри j=1 или a[j]>=a[j-1]

все

 

где Swap – процедура, обеспечивающая обмен значениями двух величин:

 

алг Swap (агррезцел a,b)

начцел с

|c:=a; a:=b; b:=c

кон