Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции - Высокоуровневые методы информатики и программирования (ВМИП) - файл 1.doc


Лекции - Высокоуровневые методы информатики и программирования (ВМИП)
скачать (2205.5 kb.)

Доступные файлы (1):

1.doc2206kb.04.12.2011 09:12скачать

содержание
Загрузка...

1.doc

1   2   3   4   5   6   7   8   9   10   11
Реклама MarketGid:
Загрузка...










шаг 1 шаг 4 шаг 5 шаг 7 шаг 9 шаг 10 шаг 12

1<3 5<8 7<8 9<11 12<16 13<16






1

5

7

9

12

13

18

20

... часть b

Сейчас можем описать процедуру слияния двух упорядоченных массивов размерностей m-k и n-m соответственно в третий упорядоченный массив, размерности n-k.
Procedure sorting4(k,m,n:integer);

var i,j:integer;

begin

i:=k+1;

j:=m+1;

k:=1;

while (i<=m) and (j<=n) do

{пока не закончилась хотя бы одна часть}

begin

if a[i]<=b[j] then

begin c[k]:=a[i]; inc(i); end

else begin c[k]:=b[j]; inc(j); end;

inc(k);

end;

{один из массивов - частей обработан полностью}

{осталось перенести в с остаток другого массива - части}

while i<=m do

begin c[k]:=a[i]; inc(i); inc(k); end;

while j<=n do

begin c[k]:=b[j]; inc(j); inc(k); end;

end;
Приведем пример программы, использующий эту процедуру в некоторой переработке ( вместо a[k+1], ..., a[m] используем a[1..k], а вместо a[m+1], ..., a[n] используем b[1..m], где k+m = n ). Эта программа делит исходный массив на две части, затем каждая часть сортируется методом “пузырьковой” сортировки, после чего части соединяются с помощью данной процедуры в искомый массив. Очевидно, скорость такого метода выше, чем просто использование “пузырьковой ” сортировки.
program n4;

const n=5;

type ar=array[1..n] of integer;

var k,m,i:integer;

a,b,c:ar;
Procedure sorting4;

var s,i,j:integer;

begin

i:=1;

j:=1;

s:=1;

while (i<=k) and (j<=m) do

{пока не закончилась хотя бы одна часть}

begin

if a[i]<=b[i] then

begin c[s]:=a[i]; inc(i); end

else begin c[s]:=b[j]; inc(j); end;

inc(s);

end;

{один из массивов - частей обработан полностью}

{осталость перенести в с остаток другого массива - части}

while i<=k do

begin c[s]:=a[i]; inc(i); inc(s); end;

while j<=m do

begin c[s]:=b[j]; inc(j); inc(s); end;

end;


procedure sorting2(var p:ar;len:integer);

var f,i,t:integer;

{f - номер просмотра (изменяется от 1 до n-1)

i - номер рассматриваемой пары

t - промежуточная переменная для перестановки местами элементов}

begin

for f:=1 to len-1 do

{цикл по номеру просмотра}

for i:=1 to len-f do

if p[i]>p[i+1] then

{перестановка элементов}

begin

t:=p[i];

p[i]:=p[i+1];

p[i+1]:=t;

end;

end;


begin

k:=n div 2;

m:=n-k;

writeln('Введите исходный массив:');

for i:=1 to n do read(c[i]);

for i:=1 to k do a[i]:=c[i];

for i:=1 to m do b[i]:=c[k+i];

sorting2(a,k);

sorting2(b,m);

sorting4;

writeln('Отсортированный массив:');

for i:=1 to n do write(c[i],' ');

writeln;

end.
^

Обменная сортировка с разделением ( сортировка Хоара )



Сортировка методом простого обмена ( методом “пузырька” ) является в среднем самой неэффективной. Это обусловлено самой идеей метода, который требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы. Можно существенно улучшить метод сортировки, основанный на обмене. Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением. Он основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. Предложил этот метод Ч. А. Р. Хоар в 1962 году. Поскольку производительность этого метода впечатляюща, автор назвал его “быстрой сортировкой”.
^ Идея метода


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

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

Пусть при этом элемент x попадет в позицию k, тогда массив будет иметь вид: ( a[1], a[2], ... , a[k-1] ), a[k], ( a[k+1], ... , a[n] ).

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

Для дальнейшей сортировки необходимо применить пункты 1 и 2 для каждой из этих частей. И так до тех пор, пока не останутся подмассивы, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.

Рассмотрим применение метода “быстрой сортировки” на примере.

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

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
Массив отсортирован полностью.

Алгоритм “быстрой сортировки” можно определить как рекурсивную процедуру, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива:
program n5;var a: array[1..10] of integer;procedure Init;

{формирование массива из фала}

var f: text;

i: integer;

begin

Assign(f,'g:\s.dat');

Reset(f);

for i:=1 to 10 do read(f,a[i]);

close(f);

end;
procedure Print; {печать массива}

var i: integer;

begin

for i:=1 to 10 do write(a[i]:5);

writeln;

end;
procedure Quik_sorting(m,l: integer);

var i,j,x,w: integer;

begin

i:=m;

j:=l;

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

repeat

while a[i]<x do inc(i);

while a[j]>x do dec(j);

if i<=j then

begin

w:=a[i]; a[i]:=a[j]; a[j]:=w;

inc(i);

dec(j);

end;

until i>j;

if m<j then Quik_sorting(m,j);

if i<l then Quik_sorting(i,l);

end;

begin {основная программа}

writeln('Массив:');

init;

print;

Quik_sorting(1,10);

writeln('отсортированный массив');

print;

end.

1   2   3   4   5   6   7   8   9   10   11



Скачать файл (2205.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru