![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Решение. Пусть задан массив чисел (снова, для простоты рассуждений, возьмем массив целых чисел):
Пусть задан массив чисел (снова, для простоты рассуждений, возьмем массив целых чисел):
12 -3 25 -10 6 8 34 -65 44 17 Этот, заданный массив обозначим именем a. В нашем примере он имеет 10 элементов. Заведем еще один массив, также из 10 тех же элементов, но уже упорядоченных по возрастанию. Наша задача будет состоять в построении этого массива. В качестве первого элемента упорядоченного массива b возьмем первый элемент массива a: Итак, массив b:
Теперь берем второй элемент массива a - это -3 и с помощью процедуры быстрого поиска вставляем его в упорядоченный массив b. Поскольку -3 меньше 12, то он вставится перед 12 и упорядоченный массив b уже будет состоять из 2-х элементов: -3 12 Берется третий элемент массива a - 25 и вставляется в массив b, получаем:
-3 12 25
И такой процесс будем продолжать до тех пор, пока все n элементов массив a не будут просмотрены. В результате образуется новый упорядоченный массив b.
Способ Program Problem7; {Сортировка простыми вставками} uses WinCrt; const n = 20; type t = array [1..n] of integer; var a, b: t; i, p: integer; {----------------------------------------------------------------------------------------} Procedure create(n: integer; var a: t); var i: integer; begin randomize; writeln('Заданный массив целых чисел'); for i: = 1 to n do begin a[i]: = random(201) - 100; write(a[i], ' ') end; writeln end; {----------------------------------------------------------------------------------------} Procedure quick_search(m, c: integer; b: t; var p: integer); var q, s: integer; begin p: = 1; q: = m; while p < q do begin s: = (p + q) div 2; if c > b[s] then p: = s + 1 else q: = s end end; {---------------------------------------------------------------------------------------} Procedure movement_end(i, k: integer; var b: t); var j: integer; begin for j: = i downto k + 1 do b[j]: = b[j - 1] end; {---------------------------------------------------------------------------------------} begin create(n, a); b[1]: = a[1]; for i: = 2 to n do begin quick_search(i, a[i], b, p); movement_end(i, p, b); b[p]: = a[i] end; writeln; writeln('Массив упорядоченный по возрастанию.'); for i: = 1 to n do write(b[i], ' '); writeln end. Способ Program Problem7a; {Сортировка простыми вставками} uses WinCrt; const n = 20; type t = array [1..n] of integer; var a: t; i: integer; {----------------------------------------------------------------------------------------} Procedure create(n: integer; var a: t); var i: integer; begin writeln('Заданный массив чисел'); randomize; for i: = 1 to n do begin a[i]: = random(201) - 100; write(a[i], ' ') end; writeln; end; {---------------------------------------------------------------------------------------} Procedure insert(var a: t; n: integer); var p, q, s, k, c: integer; begin for i: = 2 to n do begin p: =1; q: = i; c: = a[i]; while p < q do begin s: = (p + q) div 2; if c > a[s] then p: = s + 1 else q: = s end; for k: = i downto p + 1 do a[k]: = a[k - 1]; a[p]: = c end end; {----------------------------------------------------------------------------------------} begin create(n, a); insert(a, n); writeln; writeln('Массив упорядоченный по возрастанию.'); for i: = 1 to n do write(a[i], ' '); writeln end.
|