program sort1;
{$APPTYPE CONSOLE}
uses
SysUtils,
windows;
const
n=10;
s=2*n+1;
var
a: array[1..n] of integer;
rez:array[1..s]of integer;
i,l,r,m,x: integer;
ok:boolean;
begin{main}
SetConsoleCp(1251);
SetConsoleOutputCp(1251);
randomize;
for i:=1 to n do
a[i]:=random(11)-5;
for i:=1 to n do
write(a[i]:4);
writeln;
l:=rez[1];
r:=rez[2*n+1];
ok:=false;
rez[n+1]:=a[1];
m:=rez[n+1];
for i:=1 to n do
begin
a[i]:=x;
while (l<=r) and (not ok) do
begin
if rez[m]=x then
begin
ok:=true;
rez[m]:=x;
end
else
if rez[m]<x then l:=rez[m+1]
else r:=rez[m-1];
end;
end;
for i:=1 to 2*n+1 do
write(rez[i]);
readln;
end.
#include <stdlib.h>
#include <alloc.h>
#include <time.h>
#include <stdio.h>
#include <conio.h>
int tinsert (int *a, int n)
{
// возвращает 0, если нет памяти
int *x,i,j, left=n-1, right=n-1,t;
if((x=(int *) malloc((2*n-1)*sizeof(int)))==0) return 0;
x[n-1]=a[0];
for(i=1; i<n; i++)
{
t=a[i];
if(t>=a[0])
{
for(j=right; j>=0&&t<x[j]; j--)
x[j+1]=x[j];
x[j+1]=t;
right++;
}
else
{
for(j=left; j<=2*n-1&&t>x[j]; j++)
x[j-1]=x[j];
x[j-1]=t;
left--;
}
}
for(j=left; j<left+n; j++)
a[j-left]=x[j];
free(x);
return 1;
}
main()
{
int a[10], i;
clrscr ();
printf ("Сортировка методом вставок:\ n ");
randomize();
for(i=0; i<10; i++) a[i]=rand();
printf(" До сортировки :\n");
for(i=0; i<10; i++) printf(" %d ",a[i]);
printf("\n После сортировки :\n");
if(tinsert(a,10))
for(i=0; i<10; i++) printf(" %d ",a[i]);
else
printf("\n ошибка памяти ");
}
program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils,
windows;
const
n=10;
type
mas=array [1..n]of integer;
var
a:mas;
i:integer;
procedure insert (var a:mas);
var
t,i,j,left,right:integer;
x:array[1..2*n-1]of integer;
begin
left:=n-1;
right:=n-1;
for i:=1 to 2*n-1 do
x[i]:=0;
x[n-1]:=a[1];
for i:=1 to n do
begin
t:=a[i];
if t>=a[1] then
begin
j:=right;
while (j<=0) and (t<x[j]) do
j:=j-1;
x[j+1]:=x[j];
x[j]:=t;
right:=right+1;
end
else
begin
j:=left;
while (j<=2*n-1) and (t>x[j]) do
j:=j+1;
x[j-1]:=x[j];
x[j]:=t;
left:=left-1;
end;
end;
j:=left;
while j<left+n do
begin
a[j-left]:=x[j];
j:=j+1;
end;
end;
BEGIN
SetConsoleCp(1251);
SetConsoleOutputCp(1251);
writeln('введите ', n ,' чисел');
for i:=1 to n do
readln(a[i]);
writeln('отсортированные числа');
insert(a);
for i:=1 to n do
writeln(a[i]);
readln;
END.
function tinsert(var a: array of integer; n: integer): boolean;(P.S. Ты уверена, что это именно двухпутевые вставки?)
type
parr = ^arr;
arr = array[0 .. pred(maxint div sizeof(integer))] of integer;
var
X: parr;
i, j, t, left, right: integer;
begin
tinsert := false;
getmem(X, (2 * n - 1) * sizeof(integer));
if X = nil then exit;
left := n - 1; right := n - 1;
x^[n - 1] := a[0];
for i := 1 to pred(n) do begin
t := a[i];
if t >= a[0] then begin
j := right;
while (j >= 0) and (t < x^[j]) do begin
x^[j + 1] := x^[j]; dec(j);
end;
x^[j + 1] := t;
inc(right);
end
else begin
j := left;
while (j <= 2 * n - 1) and (t > x^[j]) do begin
x^[j - 1] := x^[j]; inc(j);
end;
x^[j - 1] := t;
dec(left);
end;
end;
for j := left to pred(left+n) do a[j - left] := x^[j];
freemem(X, (2 * n - 1) * sizeof(integer));
tinsert := true;
end;
var i: integer;
const
size = 10;
a: array[1 .. size] of integer = (
2, 5, 7, 9, 0, 11, 15, 6, 9, 8
);
begin
writeln('Сортировка методом вставок:');
{
randomize;
for i := 1 to size do a[i] := random(100);
}
writeln(' До сортировки :');
for i := 1 to size do write(a[i]:4);
writeln;
writeln(' После сортировки :');
if tinsert(a, size) then begin
for i := 1 to size do write(a[i]:4);
writeln;
end
else writeln('ошибка памяти');
end.
program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils,
windows;
const
n=10;
type
mas=array [1..n]of integer;
var
a:mas;
i:integer;
procedure insert (var a:mas);
var
t,i,j,left,right:integer;
x:array[1..2*n-1]of integer;
begin
left:=n-1;
right:=n-1;
for i:=1 to 2*n-1 do
x[i]:=0;
x[n-1]:=a[1];
for i:=1 to n do
begin
t:=a[i];
if t>=a[1] then
begin
j:=right;
while (j>=0) and (t<x[j]) do
begin
j:=j-1;
x[j+1]:=x[j];
end;
x[j]:=t;
right:=right+1;
end
else
begin
j:=left;
while (j<=2*n-1) and (t>x[j]) do
begin
j:=j+1;
x[j-1]:=x[j];
end;
x[j]:=t;
left:=left-1;
end;
end;
j:=left;
while j<left+n do
begin
a[j-left]:=x[j];
j:=j+1;
end;
end;
BEGIN
SetConsoleCp(1251);
SetConsoleOutputCp(1251);
writeln('введите ', n,' чисел');
for i:=1 to n do
readln(a[i]);
writeln('отсортированные числа');
insert(a);
for i:=1 to n do
writeln(a[i]);
readln;
END.
program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils,
windows;
const
n=10;
type
mas=array [1..n]of integer;
var
a:mas;
i:integer;
procedure insert(var a:mas);
var
t,i,j,left,right:integer;
x:array[1..2*n] of integer;
begin
left:=n;
right:=n;
x[n]:=a[1];
for i:=2 to n do
begin
t:=a[i];
if t>=a[1] then
begin
Inc(right);
j:=right;
while t<x[j-1] do
begin
x[j]:=x[j-1];
Dec(j);
end;
x[j]:=t;
end
else
begin
Dec(left);
j:=left;
while t>x[j+1] do
begin
x[j]:=x[j+1];
Inc(j);
end;
x[j]:=t;
end;
end;
for j:=1 to n do
a[j]:=x[j+left-1];
end;
begin
SetConsoleCp(1251);
SetConsoleOutputCp(1251);
writeln('введите ', n,' чисел');
for i:=1 to n do
readln(a[i]);
writeln('отсортированные числа');
insert(a);
for i:=1 to n do
writeln(a[i]);
readln;
end.