IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> сортировка двухпутевой вставкой
сообщение
Сообщение #1


Гость






Мальчики, пожалуйста, дайте код сортировки двухпутевой вставкой. Пожалуйста!!!!Оень нужно!!!!!!!!
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Андрей, двухпутевые вставки описаны в 3-ем томе Кнута, раздел 5.2.1 yes2.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Ребята, помогите, ну просто очень нужно!!!
Впервые метод двухпутевых вставок был предложен в начале 50-х годов как метод, позволяющий сократить число необходимых перемещений (по сравнению с простыми вставками). Число пересылок можно сократить примерно в 2 раза до N/8, если допустить сдвиги элементов не только вправо, но и влево. Для выходного файла резервируется место в памяти, равное 2N+1 ,где N – число элементов в исходном файле. Первый элемент пересылается в середину выходного файла. В дальнейшем элементы выходного файла сдвигаются вправо или влево в зависимости от того, в какую сторону нужно сдвигать меньше элементов, то есть туда, где удобнее. Таким образом, удается сократить примерно половину времени работы за счет некоторого усложнения программы. Но этот метод можно применять, используя памяти не больше, чем требуется для N записей
№ 0 1 2 3 4 5 6 7 8 9 503 087 512 061 908 170 897 275 653 426 Процесс сортировки выглядит следующим образом:
Во входном массиве определяем элемент, который больше всего подходит, для помещения его в середину области вывода (№0 503)
Определяем количество элементов в выходном массиве, превышающих и не превышающих 503
503
Устанавливаем положение следующего элемента (№1 087) Сравниваем запись №1 с левой границей (087<503) 087 - левая граница в выходном массиве
087 503
Сравниваем запись №2 с правой границей Запись №2 - новая правая граница
0 1 2 3 4 5 6 7 8 9
503 087 512 061 908 170 897 275 653 426 087 503 512
Сравниваем запись №3 с левой границей 61 - левая граница в выходном массиве
061 087 503 512
Сравниваем запись №4 с правой границей Запись №4 - новая правая граница

0 1 2 3 4 5 6 7 8 9
503 087 512 061 908 170 897 275 653 426 061 087 503 512 908
Сравниваем запись №5 с левой границей. Сравниваем запись №5 с правой границей Находим место для записи №5 - позиция 5. Производим сдвиг.

061 087 503 512 908
Сравниваем запись №5 с левой границей. Сравниваем запись №5 с правой границей Находим место для записи №5 - позиция 5. Производим сдвиг.

061 087 503 512 908
Вставляем запись №5 в позицию 5
061 087 170 503 512 908
Дальше продолжаем аналогично
И так сортируем до конца ряда. В результате должна получиться последовательность:
061 087 170 275 426 503 512 653 897 908

 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Люди, Отзовитесь!!!! Помогите блондинке!!!! Пожалуйста............
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Это и есть метод двухпутевой вставки?
[/code]
program sort;
const
n=10;
var
a: array[1..n] of integer;
i,j,t,l: integer;
begin
randomize;
for i:=1 to n do
a[i]:=random(11)-5;
for i:=1 to n do
write(a[i]:4);
writeln;
while l<>2 do
begin
l:=l+1;
j:=j+1;
i:=2-(j mod 2);
while i<n-1+(j mod 2) do
begin
if a[i]>a[i+1] then
begin
l:=0;
t:=a[i];
a[i]:=a[i+1];
a[i+1]:=t;
end;
inc(i,2);
end;
end;
for i:=1 to n do
write(a[i]:4);
end.[code=pas]
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Профи
****

Группа: Пользователи
Сообщений: 731
Пол: Женский

Репутация: -  25  +


Это - метод парных сравнений..

[offtop] Какой знакомый код)) [/offtop]
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Посмотрите, пожалуйста. Я что-то написала, но это не работает, а как по-нормальному сделать...мозгов не хватает sad.gif

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.

 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Люди добрые! помогите, пожалуйста!!! На днях курсовую сдавать, а кода нет sad.gif У самой написать никак не получается...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Нашла код программы на С.

#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 ошибка памяти ");
}



с помошью наполовину разбирающегося человека перевела на Паскаль. Но не работает программка sad.gif Помогите, пожалуйста!!!

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.

 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Любой конвертер C->Pas на ура справляется с этой задачей:

function tinsert(var a: array of integer; n: integer): boolean;
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.
(P.S. Ты уверена, что это именно двухпутевые вставки?)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Большое спасибо, ВАМ!!! Да, я думаю это и есть двухутевые вставки. У меня к ВАМ еще один вопрос, а нельзя это как то сделать, исправив то что я навояла. А то я половины операторов не знаю, в том что ВЫ написали. Ужасный программист из меня похоже...

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.

 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






Cпасибо всем за помощь!!! Задачка решенаsmile.gif

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.

 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.10.2020 12:43
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name