Варианты заданий 37 Контрольные вопросы к защите ргр: 39
Вид материала | Контрольные вопросы |
СодержаниеСортировка простым обменом («Пузырьковая сортировка») Шейкерная сортировка Быстрая сортировка Сортировка слиянием |
- А внимательно прочитайте вопросы и варианты ответов, 66.8kb.
- А внимательно прочитайте вопросы и варианты ответов, 85.91kb.
- Контрольная работа и ее краткая характеристика дкр, 446.71kb.
- Варианты задания на ргр (по уровням сложности), 35.75kb.
- Контрольные вопросы, тематика тестовых заданий и экзаменационных билетов, 23.19kb.
- План работы комитета ргр по оценке недвижимости на 2011 2012, 46.4kb.
- Общие рекомендации. Внимательно прочитайте каждое задание и предлагаемые варианты ответа,, 59.07kb.
- Учебное пособие Новочеркасск, 2009 удк 343. 8 (075. 8) Ббк 67. 409, 2241.72kb.
- Александр Леонидович Симанов Содержание История философии. Онтология и гносеология., 225.58kb.
- Особенности бухгалтерского учета, 286.34kb.
Сортировка простым обменом («Пузырьковая сортировка»)
Сортировка обменом основана на многократном обходе массива чисел a1, a2,… an. При каждом обходе сравниваются два соседних элемента ai и ai+1. Если элементы неупорядочены, то они меняются местами. В следствие последовательных перестановок, например, при упорядочивании массива по возрастанию, постепенно продвигается вправо и становится на свое место максимальный элемент массива. При втором обходе – длина массива уменьшается на 1 (исключается последний элемент) и процесс повторяется. Последний обход выполняется для массива из 2 элементов.
Пример 5
Отсортировать массив чисел M={5, 4, 8, 2, 9} по возрастанию.
1-ый просмотр. Рассматривается весь массив.
{i - номер первого элемента проверяемой (сравниваемой) пары}.
i=1 | 5 | > | 4 | | 8 | | 2 | | 9 |
меняем местами | |||||||||
i=2 | 4 | | 5 | < | 8 | | 2 | | 9 |
не меняем | |||||||||
i=3 | 4 | | 5 | | 8 | > | 2 | | 9 |
меняем | |||||||||
i=4 | 4 | | 5 | | 2 | | 8 | < | 9 |
не меняем |
Число 9 встало на свое место и в последующих просмотрах его можно не рассматривать.
2-ой просмотр. Рассматривается весь массив, с первого элемента до предпоследнего.
i=1 | 4 | < | 5 | | 2 | | 8 | | 9 |
не меняем | |||||||||
i=2 | 4 | | 5 | > | 2 | | 8 | | 9 |
меняем | |||||||||
i=3 | 4 | | 2 | | 5 | < | 8 | | 9 |
не меняем |
Число 8 также встало на свое место. Говорят, «всплыл» еще один «пузырек».
3-ий просмотр. Рассматривается часть массива без последних двух элементов.
i=1 | 4 | > | 2 | | 5 | | 8 | | 9 |
меняем | |||||||||
i=2 | 2 | | 4 | < | 5 | | 8 | | 9 |
не меняем |
Число 5 встало на свое место.
4-ый просмотр. Рассматривается последняя пара элементов.
i=1 | 2 | < | 4 | | 5 | | 8 | | 9 |
не меняем |
В итоге имеем отсортированный массив:
2 | | 4 | | 5 | | 8 | | 9 |
Блок-схема сортировки простым обменом:
Процедура сортировки простым обменом:
procedure sort_puz(A:array of integer; n:integer);
var c,i,j:integer;
begin
for i:=n downto 2 do
for j:=1 to i-1 do
if A[j]>A[j+1] then begin
c:=A[j];
A[j]:=A[j+1];
A[j+1]:=c;
end;
end;
При сортировке методом «пузырька» выполняется (N-1) просмотров, на каждом i-ом просмотре производится (N-1) сравнений. Общее количество C=N*(N-1)/2= Θ(N2).
Сортировку простым обменом можно усовершенствовать, если фиксировать перестановки на каждом проходе и, если на очередном проходе не было ни одной перестановки (массив уже отсортирован и последующие проходы со сравнениями будут “холостыми”), сортировку прекратить. Например, массив чисел 6, 5, 1, 14, 3, 7 при сортировке по возрастанию методом простого обмена будет упорядочен уже после 3-го прохода.
Шейкерная сортировка
Шейкерная сортировка является модификацией пузырьковой сортировки. Она заключается в чередовании последовательных просмотров слева направо и наоборот, справа налево, при этом фиксируется количество перестановок. Если количество перестановок на очередном просмотре равно 0, массив упорядочен и, следовательно, процесс сортировки можно закончить.
Пример 6
Сортировка по возрастанию массива чисел М ={13,2,6,66,51,19,3,11,34,20}.
1 проход (прямой, ).
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
13 | 2 | 6 | 66 | 51 | 19 | 3 | 11 | 34 | 20 |
При первом обходе (слева направо) как при обычной «пузырьковой сортировке» встанет на «свое» место максимальный элемент массива.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
2 | 6 | 13 | 51 | 19 | 3 | 11 | 34 | 20 | 66 |
Количество перестановок k=8.
2 проход (обратный, ). Уменьшив длину массива, выполним проход в обратном направлении.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
2 | 6 | 13 | 51 | 19 | 3 | 11 | 34 | 20 |
В результате перестановок «всплывет» еще один «пузырек».
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
2 | 3 | 6 | 13 | 51 | 19 | 11 | 20 | 34 |
Количество перестановок k=5.
3 проход (). Продолжаем обход слева направо без 1–го элемента (он уже стоит на «своем месте»).
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
3 | 6 | 13 | 51 | 19 | 11 | 20 | 34 |
На выходе:
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
3 | 6 | 13 | 19 | 11 | 20 | 34 | 51 |
K=4.
4 проход ( ).
2 | 3 | 4 | 5 | 6 | 7 | 8 |
3 | 6 | 11 | 13 | 19 | 20 | 34 |
К=2
5 проход ().
3 | 4 | 5 | 6 | 7 | 8 |
6 | 11 | 13 | 19 | 20 | 34 |
Количество перестановок k = 0, значит, массив упорядочен и процесс можно прекратить.
Быстрая сортировка
Реализация данного метода сортировки основывается на рекурсивном вызове процедуры упорядочивания. Она была разработана в 1962 году профессором Оксфордского университета К.Хоаром.
Быстрая сортировка основывается на принципе «разделяй и властвуй» и является улучшенной модификацией пузырьковой сортировки. Сначала берется весь массив и частично упорядочивается особенным образом: выбирается серединный элемент, назовем его ключом, а остальные элементы упорядочиваются относительно этого ключа так, чтобы слева располагались элементы меньшие ключа (если массив сортируется по возрастанию), а справа – большие. В итоге ключевой элемент встает на «свое место». Затем к левой и правой частям (относительно ключа) применяется этот же метод, то есть выбирается новый ключ и упорядочивание подмассива относительно его. И так до тех до тех пор, пока каждая из частей не будет содержать ровно один элемент.
Пример 7
Рассмотрим работу данного метода на примере сортировки массива А={6, 23, 17, 8, 14, 25, 6, 3, 30, 7} по возрастанию.
Выбирается серединный элемент массива – key=A[5]=14. Просматривая левую часть массива (слева направо) найдем элемент, больший key, а в правой части ищем элемент (двигаясь справа налево), меньший key. Затем эти элементы меняем местами.
(i,j- индексы левой и правой половины соответственно)
i=2 j=10
6 23 17 8 14 25 6 3 30 7
Продолжаем поиск элементов для перестановки:
i=3 j=8
6 7 17 8 14 25 6 3 30 23
i=5 j=7
6 7 3 8 14 25 6 17 30 23
i=6 j=7
6 7 3 8 6 25 14 17 30 23
i=j=6
6 7 3 8 6 25 17 30 23
В итоге ключевой элемент стоит на «своем месте», т.е. всплыл первый «пузырек». Слева (с 1-го по 5-ый элемент) и справа (с 7-го по 10-ый) от ключа элементы еще не упорядочены, применим к ним тот же метод, вызвав процедуру быстрой сортировки. Это уже будет второй уровень рекурсии.
Блок-схема быстрой сортировки:
Процедура быстрой сортировки:
procedure quick(var A:array of integer; l,r:integer);
var X,i,j, V:integer;
begin
X:=A[(l+r)div 2];
i:=l; j:=r;
while (i
begin
while A[i]
while A[j]>X do dec(j);
If i
V:=A[i];
A[i]:=A[j];
A[j]:=V;
end;
end;
if i>l then quick(A,l,j-1);
if j
end;
Оценим эффективность метода быстрой сортировки. На каждом шаге делим массив на две части, для каждой из этих частей – N/2 сравнений (всего – 2*N/2=N), затем на 2-ом шаге снова делим, получаем N/4 сравнений (4*N/4=N) и т.д. Так как глубина рекурсии (количество разбиений) равна Log2N, а количество сравнений на каждом уровне – N, то сложность алгоритма С = Θ (N*logN).
Сортировка слиянием
Сортировка слиянием основывается на рекурсивном делении массива пополам на два подмассива до тех пор пока каждый подмассив не будет состоять из одного элемента и затем постепенном объединении (слиянии) подмассивов в один упорядоченный.
Для слияния двух (упорядоченных на предыдущих рекурсивных итерациях) подмассивов понадобится новый массив, в который элементы из двух подмассивов будут «сливаться» уже в отсортированном виде. Слияние осуществляется следующим образом. Сравниваются два элемента из «левого» и «правого» подмассивов. Тот элемент, который удовлетворяет признаку упорядочивания (т.е. меньший, если сортируем по возрастанию) записывается в новый упорядоченный массив. Затем снова сравниваются элементы из подмассивов и так до тех пор, пока в одном из подмассивов не останется выбранных элементов. Тогда из другого подмассива оставшиеся элементы переписываем в порядке их следования (они уже упорядочены).
Пример 8
Пример слияния двух упорядоченных по неубыванию массивов А={3, 5,12, 23} и B={2, 6, 9} в один массив.
(i,j- индексы массивов А и В соответственно)
i | | | | | j | | |
3 | 5 | 12 | 23 | | 2 | 6 | 9 |
Сравниваем первые элементы массивов: A[1]>B[1], следовательно в результирующий массив запишем элемент массива В: C[1]=B[1]:
С: | 2 | | | | | | |
Индекс массива В j наращивается и продолжается сравнение элементов двух подмассивов:
i | | | | | | j | |
3 | 5 | 12 | 23 | | 2 | 6 | 9 |
С: | 2 | 3 | | | | | |
Наращивается индекс i:
| i | | | | | j | |
3 | 5 | 12 | 23 | | 2 | 6 | 9 |
С: | 2 | 3 | 5 | | | | |
Продолжая процесс, сравниваем следующие элементы массивов. Элемент 5 идет в новый массив и снова наращивается индекс i.
| | i | | | | j | |
3 | 5 | 12 | 23 | | 2 | 6 | 9 |
С: | 2 | 3 | 5 | 6 | | | |
Следующее сравнение:
| | i | | | | | j |
3 | 5 | 12 | 23 | | 2 | 6 | 9 |
С: | 2 | 3 | 5 | 6 | 9 | | |
Из правого массива выбраны все элементы, значит из левого массива по порядку переписываем оставшиеся элементы. В итоге имеем упорядоченный по возрастанию массив.
С: | 2 | 3 | 5 | 6 | 9 | 12 | 23 |
Процедура сортировки слиянием рекурсивно делит массив на подмассивы до тех пор, пока каждый подмассив не будет содержать только один элемент, а затем вызывается процедура слияния двух подмассивов, в которую передаются левый и правый подмассивы.
Блок-схема процедуры слияния двух подмассивов:
Процедура сортировки слиянием:
procedure sort_slij(var a:array of integer; p,r:integer);
var q:integer;
d:array[1..r]of integer;
{в процедуру слияния передаем начало и конец левого массива, конец правого}
procedure sl(pp,qq,rr:integer);
var t,i,j,k:integer;
begin
i:=pp;j:=qq+1;t:=1; {передача значений индексам массивов }
{i – индекс левого массива}
{j – индекс правого массива}
{t – индекс нового массива}
while (i<=qq)and(j<=rr)do
begin
if a[i]
d[t]:=a[i];
inc(i);
end
else begin
d[t]:=a[j];
inc(j);
end;
inc(t);
end;
{Запись оставшихся элементов в новый массив}
while i<=qq do begin d[t]:=a[i];inc(i);inc(t) end;
while j<=rr do begin d[t]:=a[j];inc(j);inc(t) end;
{копирование элементов массива d в исходный массив а}
for k:=1 to t-1 do a[pp+k-1]:=d[k];
end;
{основная программа сортировки слиянием}
begin
if p
q:=(p+r) div 2;{деление пополам}
sort_slij(A,p,q); {вызов процедуры сортировки }
{для левой половины}
sort_slij(A,q+1,r); {вызов для правой половины}
sl(p,q,r); {вызов процедуры слияния}
end;
end;
В следствие того, что процедура вызывается для каждой половины при каждом рекурсивном вызове, эффективность сортировки, как и в быстрой сортировке имеет сложность порядка С= Θ (N*logN).