Сортировка массива

Ввести теоретический материал по данной теме, изучить основные алгоритмы упорядочения  (сортировки) данных.

Научить применять полученные знания при решении задач, видеть в них простые составляющие.

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

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

Развивать познавательный интерес, воспитывать информационную культуру.

Воспитывать взаимопомощь при выполнении групповых заданий.

Сортировкой  называется процесс (операция) перегруппировки объектов в некотором определенном порядке. Различают внутреннюю сортировку и внешнюю.

Алгоритмы внутренней сортировки  упорядочивают данные, хранимые в оперативной памяти, алгоритмы внешней сортировки обрабатывают данные, хранимые во внешней памяти.

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

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

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

Подобными свойствами обладают и те алгоритмы сортировки, которые рассмотрены ниже. Они отобраны из множества алгоритмов, потому что,

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

Алгоритмы разделяются на две группы: 3 прямых (Метод «пузырька», метод прямого выбора, метод прямого включения) и 3 улучшенных (Метод Хоара, метод Шелла, пирамидальная сортировка).

Авторы: Ахметзянова Г.Ф.

Бурнаева А.Ш.

учителя информатики гимназии №155 города Казани РТ

Содержание:

• Используемые учебники
• Тематическое планирование темы
• Цель, задачи
• Методы работы, технологии, формы работы
• Поурочное планирование:

• Сортировка методом «пузырька» Сортировка методом простого выбора Сортировка методом прямого включения
• Сортировка методом «пузырька»
• Сортировка методом простого выбора
• Сортировка методом прямого включения

• Практические задания
• Лабораторная работа
• Дополнительные материалы
• Контрольные вопросы
• Литература

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

Учебники

Информатика в старшей школе

1

Угринович Н. Д.

Информатика и информационные технологии. 10 - 11 кл.

"Практикум по информатике и информационным технологиям".

2

3

2002

Семакин И. Г., Хеннер Е. К.

Информатика. 10 кл.

4

Семакин И. Г., Хеннер Е. К.

Информатика. 11 кл.

2001

БИНОМ

БИНОМ

Соответстует обязательному минимуму содержания образования 1999 г. УМК учебник 10 - 11 кл.; практикум; методическое пособие 7 - 11 кл.; "Исследование информационных моделей"; "Основы программирования на примере Visual Basic .NET"

Бешенков С. А.,

Ракитина Е. А.

Информатика. 10 кл.

2002

5

Соответствует обязательному минимуму содержания образования 1999 г. УМК: учебник 10 кл.; учебник 11 кл.; задачник-практикум 8 - 11 кл. (в 2-х томах); элективный курс "Информационные системы и модели"

БИНОМ

2001

Бешенков С. А., Кузьмина Н. В., Ракитина Е. А.

Информатика. 11 кл.

БИНОМ

2002

Соответствует обязательному минимуму содержания образования 1999 г. УМК: учебник 10 кл.; учебник 11 кл.;

БИНОМ

Тематическое планирование

11 класс

( 2ч х 34 уч.недели = 68ч)

По теме «Сортировка»

№

Тема теоретической части

Тема практической части

Часов

12

Теория.

Сортировка линейного массива

13

методы «пузырька», выборки

Сортировка линейного массива

Лабораторная работа.

2

метод прямого включения,

Решение задач

2

Цели и задачи:

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

Вид: комбинированный

Методы работы :

• частично-поисковый;
• проблемный;
• Объяснительно-иллюстративный

Технологии:

• личностно-ориентированная технология;
• компьютерная технология;
• разноуровневого обучения
• проблемно-исследовательская.

Формы работы:

• беседа;
• индивидуальная
• групповая.

Оборудование: ПК различных модификаций;

мультимедийное оборудование; раздаточный материал.

Программное обеспечение : программа Turbo Pascal , Power Point

1 и 2 уроки темы

“ Мозг хорошо устроенный, стоит больше, чем мозг, хорошо наполненный” М. Моньель

• Сортировкой называется процесс (операция) перегруппировки объектов в некотором определенном порядке. Различают внутреннюю сортировку и внешнюю.
• Алгоритмы внутренней сортировки упорядочивают данные, хранимые в оперативной памяти, алгоритмы внешней сортировки обрабатывают данные, хранимые во внешней памяти.

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

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

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

• Подобными свойствами обладают и те алгоритмы сортировки, которые рассмотрены ниже. Они отобраны из множества алгоритмов, потому что,

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

• Алгоритмы разделяются на две группы: 3 прямых (Метод «пузырька», метод прямого выбора, метод прямого включения) и 3 улучшенных (Метод Хоара, метод Шелла, пирамидальная сортировка)

1 ДА МЕНЯЕМ 8 И 1 1 8 9 6 0 3 4 8 9 НЕТ 1 8 9 6 0 3 4 9 6 ДА МЕНЯЕМ 9 И 6 1 8 6 9 0 3 4 90 ДА МЕНЯЕМ 9 И 0 1 8 6 0 9 3 4 93 ДА МЕНЯЕМ 9 И 3 1 8 6 0 3 9 4 94 ДА МЕНЯЕМ 9 И 4 1 8 6 0 3 4 9 A[i]=A[i+1] P:=A[I] A[I]:=A[I+1] A[I+1]:=P I:=I+1 i" width="640"

I:=1

i= 1 2 3 4 5 6 7

8 1 9 6 0 3 4

81 ДА МЕНЯЕМ 8 И 1

1 8 9 6 0 3 4

8 9 НЕТ

1 8 9 6 0 3 4

9 6 ДА МЕНЯЕМ 9 И 6

1 8 6 9 0 3 4

90 ДА МЕНЯЕМ 9 И 0

1 8 6 0 9 3 4

93 ДА МЕНЯЕМ 9 И 3

1 8 6 0 3 9 4

94 ДА МЕНЯЕМ 9 И 4

1 8 6 0 3 4 9

A[i]=A[i+1]

P:=A[I]

A[I]:=A[I+1]

A[I+1]:=P

I:=I+1

i

=A[I+1] THEN BEGIN P:=A[I]; A[I]:=A[I+1]; A[I+1]:=P ; END; WRITELN('Отсортированный массив :'); { ПЕЧАТЬ ОТСОР. МАС C ИВА } FOR I:=1 TO 7 DO WRITE( A[I ],' ') ; END. " width="640"

PROGRAM MAS;

VAR A :ARRAY[1..7] OF INTEGER;

N :INTEGER; { счетчик циклов }

I :INTEGER; { текущий индекс элемента массива }

P :INTEGER; { доп.переменная для обмена элементов }

BEGIN

WRITELN(' Введите массив'); { ВВОД МАССИВА С КЛАВИАТУРЫ }

FOR I:=1 TO 7 DO READ ( A[I ]);

FOR N:=1 TO 6 DO { СОРТИРОВКА }

FOR I:=1 TO 6 DO

IF A[I]=A[I+1] THEN

BEGIN P:=A[I]; A[I]:=A[I+1]; A[I+1]:=P ; END;

WRITELN('Отсортированный массив :'); { ПЕЧАТЬ ОТСОР. МАС C ИВА }

FOR I:=1 TO 7 DO

WRITE( A[I ],' ') ;

END.

Реализация на ЭВМ

Эта сортировка применяется для массивов, для не содержащих повторяющихся элементов.

Алгоритм:

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

2.Поменять его местами с последним элементом (после этого самый большой элемент массива будет стоять на своем месте).

3.Повторить пункты 1-2 с оставшимися n - 1-элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в ней максимальный элемент и поменять его местами с предпоследним ( n -1) -м элементом, затем с оставшимися n-2 элементами итак далее, пока не останется один (наименьший) элемент, уже стоящий на своем месте.

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

Пусть исходный массив А состоит из 10 элементов и имеет вид

5 13 7 9 1 8 16 4 10 2

После сортировки массив должен выглядеть так:

1 2 4 5 7 8 9 10 13 16

1-й шаг: рассмотрим весь массив и найдем в нем максимальный элемент – 16 (стоит на седьмом месте), поменяем его местами с последним элементом – с 2.

5 13 7 9 1 8 16 4 10 2

Максимальный элемент записан на свое место.

2-й шаг: рассмотрим часть массива – с первого до девятого элемента. Максимальный элемент этой части – 13, стоящий на втором месте. Поменяем его местами с последним элементом этой части – с 10.

5 13 7 9 1 8 2 4 10 16

Отсортированная часть массива состоит теперь уже из двух элементов.

3-ий шаг: снова уменьшим рассматриваемую часть массива на один элемент. Здесь надо поменять местами второй элемент (его значение - 10) и последний элемент этой части – 4.

5 10 7 9 1 8 2 4 13 16

В отсортированной части массива – 3 элемента.

4-ый шаг: аналогично.

5 4 7 9 1 8 2 10 13 16

5-ый шаг: максимальный элемент этой части массива является последним в ней, поэтому его надо оставить на старом месте.

5 4 7 2 1 8 9 10 13 16

Далее действуем аналогично.

6-й шаг:

5 4 7 2 1 8 9 10 13 16

7-й шаг:

5 4 7 2 1 8 9 10 13 16

8-й шаг:

2 4 1 5 7 8 9 10 13 16

9-й шаг:

2 1 4 5 7 8 9 10 13 16

Итог:

1 2 4 5 7 8 9 10 13 16

Теперь можем записать алгоритм сортировки:

max then begin imax:=j; max:=a[j]; end; a[imax]:=a[i]; a[i]:=max; end; For i:=1 to n do Write(a[i]:4); { Печать отсортированного массива } Repeat until keypressed; End. " width="640"

Program Sort2;

Uses crt;

Const n=10;

Var a:array[1..n] of integer;

i,j,imax,max : integer;

Begin

clrscr;

Randomize; { Заполнение массива }

For i:=1 to n do

begin

a[i]:=random(100);

Write(a[i]:4); { Печать исходного массива }

end;

Writeln;

For i:=n downto 2 do { Сортировка массива }

begin

imax:=i; max:=a[i];

For j:=2 to i-1 do { Поиск максимального элемента }

if a[j]max then

begin

imax:=j; max:=a[j];

end;

a[imax]:=a[i]; a[i]:=max;

end;

For i:=1 to n do

Write(a[i]:4); { Печать отсортированного массива }

Repeat until keypressed;

End.

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

3 и 4 уроки темы

=A[I+1] THEN BEGIN P:=A[I]; A[I]:=A[I+1]; A[I+1]:=P ; END; WRITELN(Самые высокие ученики в классе :'); FOR I:= KOL-5 TO KOL DO WRITE( A[I ],' ') ; END. " width="640"

PROGRAM KLASS;

VAR A :ARRAY[1.. KOL ] OF REAL ; N,I,P,KOL :INTEGER;

BEGIN

WRITELN(' Введите количество учеников в классе');

READ(KOL);

WRITELN(' Введите рост очередного учащегося');

FOR I:=1 TO KOL DO

READ ( A[I ]);

FOR N:=1 TO KOL -1 DO

FOR I:=1 TO KOL-1 DO

IF A[I]=A[I+1] THEN

BEGIN P:=A[I]; A[I]:=A[I+1]; A[I+1]:=P ; END;

WRITELN(Самые высокие ученики в классе :');

FOR I:= KOL-5 TO KOL DO

WRITE( A[I ],' ') ;

END.

max then begin imax:=j; max:=a[j]; end; a[imax]:=a[i]; a[i]:=max; end; For i:=kol-5 to kol do Write(a[i]); End. " width="640"

Program KLASS;

Var A:array[1..KOL] of real;

i,j,imax,max, : integer;

Begin

Write (' Введите количество учеников в классе ') ;

Read(kol);

Write (' Введите рост очередного учащегося');

For i:=1 to kol do

Read(a[i]);

For i:=kol downto 2 do

begin

imax:=i; max:=a[i];

For j:=2 to i-1 do

if a[j]max then

begin

imax:=j; max:=a[j];

end;

a[imax]:=a[i]; a[i]:=max;

end;

For i:=kol-5 to kol do

Write(a[i]);

End.

• Элементы мысленно делятся на уже “готовую” последовательность а1, … , а i -1 и исходную последовательность.
• При каждом шаге, начиная с I = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i -й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

1, 98, СТАВИМ 9 В КОНЕЦ НА 3 МЕСТО 8 1 9 6 0 3 4 1 8 9 _ _ _ _ 61, 6 6 НА 2 МЕСТО 1 8 6 9 0 3 4 0 1 6 8 9 _ _ 0 0 НА ПЕРВОЕ МЕСТО, СДВИГАЯ ВСЕ ЭЛЕМЕНТЫ ВПРАВО НА ЯЧЕЙКУ 1 8 6 9 0 3 4 0 1 3 6 8 9 _ 3 1, 3 3 НА 3 МЕСТО 1 8 6 9 0 3 4 0 1 3 4 6 8 9 4 3, 4 4 НА 4 МЕСТО " width="640"

8 1 9 6 0 3 4

8 _ _ _ _ _ _

1 1 НА ПЕРВОЕ МЕСТО, СДВИГАЯ ВСЕ ЭЛЕМЕНТЫ ВПРАВО НА ЯЧЕЙКУ

8 1 9 6 0 3 4

1 8 _ _ _ _ _

91, 98, СТАВИМ 9 В КОНЕЦ НА 3 МЕСТО

8 1 9 6 0 3 4

1 8 9 _ _ _ _

61, 6 6 НА 2 МЕСТО

1 8 6 9 0 3 4

0 1 6 8 9 _ _

0 0 НА ПЕРВОЕ МЕСТО, СДВИГАЯ ВСЕ ЭЛЕМЕНТЫ ВПРАВО НА ЯЧЕЙКУ

1 8 6 9 0 3 4

0 1 3 6 8 9 _

3 1, 3 3 НА 3 МЕСТО

1 8 6 9 0 3 4

0 1 3 4 6 8 9

4 3, 4 4 НА 4 МЕСТО

PROGRAM SI ;

VAR

I,J,N,X:INTEGER;

A:ARRAY[0..50] OF INTEGER;

BEGIN

WRITELN (‘Введите длину массива’);

READ ( N );

WRITELN (‘Введите массив’);

FOR I:=1 TO N DO READ(A[I]);

FOR I:=2 TO N DO BEGIN

X:=A[I];

A[0]:=X;

J:=I;

WHILE X

A[J]:=A[J-1];

DEC(J)

END;

A[J]:=X

END;

WRITELN ('Результат:');

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

• Простой вариант сортировки включением – это метод прямого (простого) включения, улучшенный – сортировка методом Шелла.
• Метод можно изучить перейдя по ссылке к дополнительным материалам

S2 Then Swap(S1,S2); If S2S3 Then Swap(S2,S3); If S1S2 Then Swap(S1,S2); Writeln(' Числа в порядке неубывания :V',S1,S2,S3) End. " width="640"

• Еще один классический пример. Задача: "Расположить в порядке неубывания три целых числа".
• Program Pr ; Var S1,S2,S3 :Integer; Procedure Swap(Var A,B: Integer);{Процедура Swap с параметрами-переменными} Var C : Integer; {C - независимая локальная переменная} Begin C:=A; A:=B; B:=C {Меняем местами содержимое A и B} End ; Begin
• Writeln(' Введите три числа '); Readln(S1,S2,S3); If S1S2 Then Swap(S1,S2); If S2S3 Then Swap(S2,S3); If S1S2 Then Swap(S1,S2); Writeln(' Числа в порядке неубывания :V',S1,S2,S3)
• End.

Задачи

* Задача №1

Написать программу для упорядочивания целочисленного массива по убыванию

* Задача №2

Написать программу для упорядочивания целочисленного массива по возрастанию

* Задача №3

Написать программу для упорядочивания по возрастанию элементов каждой строки матрицы размером n x m

* Задача №4

Дан массив A[n]. Написать программу, которая отсортирует по возрастанию исходный массив и заменит отрицательные элементы на ноль.

* Задача №5

Дан массив B[n]. Написать программу, которая отсортирует по возрастанию исходный массив и создаст два массива , в одном из которых находятся четные по номеру элементы , в другом нечетные по номеру элементы исходного массива.

* Задача №6

Написать программу для упорядочивания по убыванию элементов каждой строки матрицы

B(n x m) и создать новый массив В1( N ),элементами которого будут первые элементы каждой строки.

* Задача №7

Написать программу , которая проверяет , представляют ли элементы введенного с клавиатуры массива возрастающую последовательность. Если нет , то пересортировать массив.

* Задача №8

Дан массив A[n]. Написать программу, которая отсортирует по возрастанию только отрицательные элементы.

* Задача №8

Написать программу , которая проверяет , представляют ли элементы введенного с клавиатуры массива возрастающую последовательность. Если нет , то пересортировать массив

* Задача №9

Дан массив A(n). Отсортировать массив по возрастанию до значения Х. Расположить эти элементы в начало массива.

* Задача №10

Дан массив X(n). Отсортировать его по убыванию. Создать два массива: в первый включить чётные элементы массива Х( n ), во второй – нечётные элементы.

* Задача №11

Дан массив В (n). Заполнить его случайными целыми числами в диапазоне от -100 до 100. Отсортировать его до середины по возпастанию, от середины - по убыванию.

* Задача №12

Дан массив А (n). Заполнить его случайными целыми числами в диапазоне от 0 до 100. Нечётные элементы увеличить на 1 и отсортировать его.

* Задача №13

Написать программу для упорядочивания по убыванию элементов каждой строки матрицы B(n x m) и создать новый массив В1( N ),элементами которого будут первые элементы каждой строки.

* Задача №14

Массив А( n ) заполнить случайными целыми числами от 0 до 100. Найти среднее арифметическое значение этих чисел и отсортировать массив по возрастанию до этого значения.

* Задача №15

Дан массив A(n). Отсортировать массив по возрастанию и определить номера элементов, кратных 3.

* Задача №16

Дана квадратная матрица. Отсортировать элементы главной диагонали по возрастанию.

* Задача №17

Дана квадратная матрица. Отсортировать элементы боковой диагонали по убываниюанию .

Решенные задачи

Проводится разбор решенных задач

Подготовка к лабораторной работе.

Разбор задания на дом.

= f ( ak2) = . . . = f ( akn) или какое-то другое отношение порядка (здесь f - упорядочивающая функция). В простом случае f задается явно как компонент элемента таблицы, обычно этот компонент – ключ элемента. В таком случае говорят об упорядочении по ключам. Сравнительная оценка сложности алгоритмов внутренней сортировки осуществляется по следующим параметрам: число сравнений ключей элементов; число перемещений элементов. В эффективных алгоритмах стремятся сократить число сравнений и перестановок элементов, а также экономно использовать память. Поэтому алгоритмы сортировки производят перегруппировку элементов в исходном массиве. Алгоритм сортировки n данных, оперирующий сравнениями, имеет минимальную сложность n или выше (т.к. должно быть выполнено минимально n – 1 сравнений), максимальная сложность алгоритма, оперирующего сравнениями, не меньше n  log n . Основные алгоритмы сортировки базируются на одном из трех способов: 1. Сортировка включением (вставками - by insertion ). Исходное множество элементов делят на две части: уже упорядоченную и неупорядоченную. Вначале упорядоченная часть состоит, как правило, из одного элемента – первого элемента, а все остальные элементы находятся в неупорядоченной части. Из неупорядоченной части берут очередной элемент и включают его в упорядоченную часть, помещая (вставляя) на нужное место (т.е. так, чтобы выполнялось отношение порядка). Так продолжают до тех пор, пока последний элемент из неупорядоченной части не будет включен в упорядоченную часть. Простой вариант сортировки включением – это метод прямого (простого) включения, улучшенный – сортировка методом Шелла. Алгоритм прямого включения – здесь рассматриваются элементы таблицы (ее упорядоченной и неупорядоченной частей), отстоящие друг от друга на шаг равный 1: { for (i = 1; i { x = T.elemi ; c = ключ ( T.elemi ) ; j = i - 1; while ( j = 0 && ключ ( T.elemj ) c ) { T.elemj+1 = T.elemj ; j = j - 1; } T . elemj +1 = x ; } " width="640"

Л А Б О Р А Т О Р Н А Я Р А Б О Т А № 6

УПОРЯДОЧЕНИЕ ДАННЫХ

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

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

Сортировкой называется процесс (операция) перегруппировки объектов в некотором определенном порядке. Различают внутреннюю сортировку и внешнюю.

Алгоритмы внутренней сортировки упорядочивают данные, хранимые в оперативной памяти, алгоритмы внешней сортировки обрабатывают данные, хранимые во внешней памяти. В лабораторной работе № 6 рассматриваются алгоритмы внутренней сортировки данных, хранимых в статических таблицах.

Если таблица представлена множеством элементов a 1 , a 2 , . . . , an , тогда сортировка есть перестановка элементов ak 1 , ak 2 , . . . , akn , в которой над элементами установлено отношение порядка:

f ( ak1)

или

f ( ak1) = f ( ak2) = . . . = f ( akn)

или какое-то другое отношение порядка (здесь f - упорядочивающая функция).

В простом случае f задается явно как компонент элемента таблицы, обычно этот компонент – ключ элемента. В таком случае говорят об упорядочении по ключам.

Сравнительная оценка сложности алгоритмов внутренней сортировки осуществляется по следующим параметрам:

число сравнений ключей элементов;

число перемещений элементов.

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

Основные алгоритмы сортировки базируются на одном из трех способов:

1. Сортировка включением (вставками - by insertion ). Исходное множество элементов делят на две части: уже упорядоченную и неупорядоченную. Вначале упорядоченная часть состоит, как правило, из одного элемента – первого элемента, а все остальные элементы находятся в неупорядоченной части. Из неупорядоченной части берут очередной элемент и включают его в упорядоченную часть, помещая (вставляя) на нужное место (т.е. так, чтобы выполнялось отношение порядка). Так продолжают до тех пор, пока последний элемент из неупорядоченной части не будет включен в упорядоченную часть. Простой вариант сортировки включением – это метод прямого (простого) включения, улучшенный – сортировка методом Шелла.

Алгоритм прямого включения – здесь рассматриваются элементы таблицы (ее упорядоченной и неупорядоченной частей), отстоящие друг от друга на шаг равный 1:

{ for (i = 1; i

{ x = T.elemi ; c = ключ ( T.elemi ) ; j = i - 1;

while ( j = 0 && ключ ( T.elemj ) c )

{ T.elemj+1 = T.elemj ; j = j - 1; }

T . elemj +1 = x ; }

Включаемый элемент сравнивается с элементами упорядоченной части, начиная с ее последнего элемента. Число просмотров (упорядоченной части) равно n – 1.

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

Алгоритм прямого выбора – здесь среди всех элементов неупорядоченной части осуществляется поиск нужного элемента:

{ for (i = 0; i

{ min = T.elemi ; k = i;

for (j = i + 1; j

if ( ключ ( T.elemj )

{min = T.elemj ; k = j; }

T.elemk = T.elemi ; T.elemi = min; }

}

Число просмотров таблицы (неупорядоченной части) равно n – 1.

3. Сортировка обменом ( by exchange ). В исходном множестве элементов рассматриваются пары элементов. Если пара содержит инверсию, то она устраняется выполнением обмена этих элементов (инверсия – это пара индексов, на которой нарушено отношение порядка. Например, пусть отношение порядка – возрастание значений ключей элементов. Если i = ключ ( j ) , то эта пара i и j содержит инверсию). Таким образом, после каждого просмотра хотя бы один элемент окажется на своем месте. Просмотры продолжаются до тех пор, пока в массиве не останется ни одной инверсии. Простой вариант сортировки обменом – метод прямого (простого) обмена («пузырьковая» сортировка), улучшенный вариант – быстрая сортировка.

Алгоритм прямого обмена – здесь сравниваются пары соседних элементов:

вариант 1:

{ for ( i = 0; i

for ( j =0; j

if ( ключ ( T.elemj ) ключ ( T.elemj+1) )

{ x = T.elemj ; T.elemj = T.elemj+1 ;

T . elemj +1 = x ; }

}

В данном варианте всегда выполняется максимальное число сравнений. Число просмотров таблицы (неупорядоченной части) равно n – 1.

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

вариант 2:

{ инверсия = 1; j =0;

while ( инверсия )

{ инверсия = 0;

for ( i = 0; i

if ( ключ (T.elemi ) ключ ( T.elemi+1 )

{ r = Ti ; Ti = Ti+1 ; Ti+1 = r ;

инверсия = 1; j ++ ; }

} }

В данных алгоритмах таблица T определена следующим образом:

struct table

{ type elem [ N ];

int n ; }

table T ;

Здесь поле n определяет фактическое число элементов в таблице.

• Варианты задания

Упорядочить таблицу, построенную в лабораторной работе № 5 варианты 1.1.а, 1.2.а по ключу (ключ для 1.1.а – имя объекта; для 1.2.а – значение константы) методом:

а) прямого включения;

б) прямого выбора;

в) прямого обмена;

г) методом Шелла.

Используя раздел операторов, дополнить элементы таблицы числом раз использования каждого ключа. Для поиска элементов в таблице использовать:

а) последовательный поиск;

б) бинарный поиск.

Упорядочить таблицу, построенную в лабораторной работе № 5 варианты 1.1.а, 1.2.а по ключу (ключ для 1.1.а – имя объекта; для 1.2.а – значение константы) методом:

а) прямого включения;

б) прямого выбора;

в) прямого обмена;

г) методом Шелла.

Используя раздел операторов, напечатать в порядке возрастания ключей элементы таблицы, описанные, но не используемые в программе. Для поиска элементов в таблице использовать:

а) последовательный поиск;

б) бинарный поиск.

Упорядочить таблицу, построенную в лабораторной работе № 5 варианты 1.1.б, 1.1.в, 1.2.б, 1.2.в по новому ключу - по не возрастанию частоты использования элемента методом:

а) прямого включения;

б) прямого выбора;

в) прямого обмена;

г) методом Шелла.

Используя раздел операторов, дополнить элементы таблицы числом раз использования каждого ключа. Для поиска элементов в таблице использовать:

а) последовательный поиск;

б) бинарный поиск.

Упорядочить таблицу, построенную в лабораторной работе № 5 вариант 2.а по не убыванию значений ключа методом:

а) быстрой сортировки;

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

в) методом Шелла.

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

а) последовательный поиск;

б) бинарный поиск.

Дополнить таблицу, построенную в лабораторной работе № 5 варианты 2.б, 2.в информацией о цене изделия. Цену изделия брать из таблицы – прейскурант, элемент которой содержит: шифр изделия, цена ( за штуку ). Эта таблица упорядочена по возрастанию шифров изделий. Упорядочить преобразованную таблицу по новому ключу – количество изделий методом:

а) прямого включения;

б) прямого обмена;

в) методом Шелла;

г) сортировки с использованием структуры дерево.

Для поиска элементов в таблице использовать:

а) последовательный поиск;

б) бинарный поиск.

Упорядочить таблицу, построенную в лабораторной работе № 5 вариант 3.а по убыванию процентов голосов, отданных командам – претендентам:

а) на первое место;

б) на последнее место;

в) на первую тройку.

Для упорядочения использовать метод:

а) быстрой сортировки;

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

в) методом Шелла.

Упорядочить таблицу, построенную в лабораторной работе № 5 варианты 3.б, 3.в по новому ключу – по возрастанию номеров команд, не вошедших в претенденты ни на первое, ни на последнее место.

Для упорядочения использовать метод:

а) быстрой сортировки;

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

в) методом Шелла.

Дополнительные материалы

• Метод Хoаpа
• Этот метод, называемый также быстрой сортировкой. Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.
• Метод Шелла
• Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми). 
• Сортировка выбором
• На этот раз при просмотре мaccива мы будем искать наименьший элемент, Сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив. 

Метод с двоичным включением ( binary insertion )

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

ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ.

PROGRAM BI;

VAR I,J,M,L,R,X,N:INTEGER;

A:ARRAY[0..50] OF INTEGER;

BEGIN

WRITELN ('Введи длину массива');

READ(N);

WRITELN(' Введи массив ');

FOR I:=1 TO N DO READ(A[I]);

FOR I:=2 TO N DO BEGIN

X:=A[I];L:=1;R:=I;

WHILE L

M:=(L+R) DIV 2;

IF A[M]

END;

FOR J:=I DOWNTO R+1 DO A[J]:=A[J-1];

A[R]:=X

END;

WRITELN ('Результат:');

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

• ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ. PROGRAM BI; VAR I,J,M,L,R,X,N:INTEGER; A:ARRAY[0..50] OF INTEGER; BEGIN WRITELN ('Введи длину массива'); READ(N); WRITELN(' Введи массив '); FOR I:=1 TO N DO READ(A[I]); FOR I:=2 TO N DO BEGIN X:=A[I];L:=1;R:=I; WHILE L M:=(L+R) DIV 2; IF A[M] END; FOR J:=I DOWNTO R+1 DO A[J]:=A[J-1]; A[R]:=X END; WRITELN ('Результат:'); FOR I:=1 TO N DO WRITE(A[I],' ') END.
• ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ. PROGRAM BI; VAR I,J,M,L,R,X,N:INTEGER; A:ARRAY[0..50] OF INTEGER; BEGIN WRITELN ('Введи длину массива'); READ(N); WRITELN(' Введи массив '); FOR I:=1 TO N DO READ(A[I]); FOR I:=2 TO N DO BEGIN X:=A[I];L:=1;R:=I; WHILE L M:=(L+R) DIV 2; IF A[M] END; FOR J:=I DOWNTO R+1 DO A[J]:=A[J-1]; A[R]:=X END; WRITELN ('Результат:'); FOR I:=1 TO N DO WRITE(A[I],' ') END.
• ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ. PROGRAM BI; VAR I,J,M,L,R,X,N:INTEGER; A:ARRAY[0..50] OF INTEGER; BEGIN WRITELN ('Введи длину массива'); READ(N); WRITELN(' Введи массив '); FOR I:=1 TO N DO READ(A[I]); FOR I:=2 TO N DO BEGIN X:=A[I];L:=1;R:=I; WHILE L M:=(L+R) DIV 2; IF A[M] END; FOR J:=I DOWNTO R+1 DO A[J]:=A[J-1]; A[R]:=X END; WRITELN ('Результат:'); FOR I:=1 TO N DO WRITE(A[I],' ') END.

Анализ двоичного включения . Место включения обнаружено, если L = R . Таким образом, в конце поиска интервал должен быть единичной длины; значит, деление его пополам происходит I * log I раз. Таким образом:

C = Si : 1 i n : [ log I ] (2.7.)

Аппроксимируем эту сумму интегралом

Integral (1:n) log x dx = n*(log n – C) + C (2.8.)

Где C = log e = 1/ ln 2 = 1.4426… . (2.9.)

назад

Метод Шелла

• В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сам метод представлен на нашем стандартном примере в таблице 2.5. Сначала отдельно сортируются и группируются элементы, отстоящие друг от друга на расстояние 4. Такой процесс называется четверной сортировкой. В нашем примере восемь элементов и каждая группа состоит из двух элементов. После первого прохода элементы перегруппировываются – теперь каждый элемент группы отстоит от другого на две позиции – и вновь сортируются. Это называется двойной сортировкой.
• На третьем подходе идет обычная или одинарная сортировка. На каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок.

PROGRAM SHELLS;

CONST T=4;

H: ARRAY[1..4] OF INTEGER = (15,7,3,1);

VAR

I,J,K,S,X,N,M:INTEGER;

A:ARRAY[-16..50] OF INTEGER;

BEGIN

WRITELN ('Введи длину массива');

READ(N);

WRITELN(' Введи массив ');

FOR I:=1 TO N DO READ(A[I]);

FOR M:=1 TO T DO BEGIN

K:=H[M];

S:=-K;

FOR I:=K+1 TO N DO BEGIN

X:=A[I];

J:=I-K;

IF S=0 THEN S:=-K;

INC(S);

A[S]:=X;

WHILE X

A[J+K]:=A[J];

J:=J-K

END;

A[J+K]:=X

END;

END;

WRITELN(' Результат :');

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

назад

Метод Хоара (быстрая сортировка).

Идея метода:

1.В исходном массиве выбрать некоторый элемент x=a(k) ( барьерный элемент ) .

2.Переставить элементы массива таким образом, чтобы слева от x оказались элементы массива меньше или равные х , элементы массива, большие х .

Пусть при этом элемент х попадает в позицию под номером k , тогда массив будет иметь вид

(a[1], a[2], …, a[k-1], a[k-2], …, a[n] ).

Каждый из элементов a[1], a[2], …, a[k-1], меньше либо равен a [k], каждый из элементов a[k+1], …, a[n] больше a[k] . Отсюда можно сделать вывод, что элемент a[k] стоит на своем месте. А исходный массив при этом разделится на две неотсортированные части, барьером между которыми является элемент a[k] .

Пусть исходный массив состоит из 8 элементов:

• 12 3 7 19 11 4 16

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

(4 3) 7 (12 19 11 8 16)

Число 7 стоит на своём месте. Далее сортируем подмассивыБэлементы которых заключены в скобки. Этот процесс будем повторять до тех пор, пока не получим полностью отсортированный массив.

Левый подмассив:

(3) 4 7 (12 19 11 8 16)

3 4 7 (12 19 11 8 16)

Правый подмассив:

3 4 7 (8) 11 (19 12 16)

3 4 7 8 11 (19 12 16)

3 4 7 8 11 12 (19 16)

3 4 7 8 11 12 (16) 19

3 4 7 8 11 12 16 19

Алгоритм «быстрой» сортировки можно определить как рекурсивную процедуру, параметрами которой являются нижняя и верхняя границы изменения индексов.

x do dec(j); if i Begin w:=a[i]; a[i]:=a[j]; a[j]:=w; Inc(i); dec(j); end; Until ij; if mj Then Qsort(m,j); if iEnd; " width="640"

Program Sort3;

Uses Crt;

Const n=10;

Var a:array[1..n] of integer;

i:integer;

Procedure Qsort(m,l:integer); { Процедура сортировки }

Var I,j,x,w:integer;

Begin

i:=m; j:=l; x:=a[(m+l) div 2];

Repeat

While a[i]

While a[j]x do dec(j);

if i

Begin

w:=a[i]; a[i]:=a[j]; a[j]:=w; Inc(i); dec(j);

end;

Until ij;

if mj Then Qsort(m,j);

if i

End;

Begin

clrscr;

Randomize; { Заполнение массива }

For i:=1 to n do

begin

a[i]:=random(100);

Write(a[i]:4); { Печать исходного массива }

end;

Writeln;

Qsort(1,n);

For i:=1 to n do

Write(a[i]:4); { Печать отсортированного массива }

Repeat until keypressed;

End.

назад

Контрольные вопросы

• Понятие упорядочения.
• Характеристика прямых методов сортировки: включения, выбора, обмена.
• Сравнительная оценка сложности прямых методов сортировки по числу сравнений и числу перемещений элементов.
• Характеристика улучшенных методов сортировки, оценки их сложности.

Литература

• Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.
• Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы. – М.: Мир, 1976.
• Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. – М.: Мир, 1978.
• Подбельский В.В., Фомин С.С. Программирование на языке Си. – М.: Финансы и статистика, 2001.
• Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981.
• Мейер Б., Бодуэн К. Методы программирования.

В 2 т. – М.: Мир, 1982.

• Пильщиков В.Н. Сборник упражнений по языку Паскаль. – М.: Наука, 1989.
• Абрамов В.Г. , Трифонов Г.Н. Введение в язык Паскаль. - М.: Наука , 1988.