сортировка двухпутевой вставкой Опции

[Гость]

Мальчики, пожалуйста, дайте код сортировки двухпутевой вставкой. Пожалуйста!!!!Оень нужно!!!!!!!!

[klem4]

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

[volvo]

Андрей, двухпутевые вставки описаны в 3-ем томе Кнута, раздел 5.2.1

[Гость]

Ребята, помогите, ну просто очень нужно!!!
Впервые метод двухпутевых вставок был предложен в начале 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

[Гость]

Люди, Отзовитесь!!!! Помогите блондинке!!!! Пожалуйста............

[Гость]

Это и есть метод двухпутевой вставки?
[/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]

[Айра]

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

[offtop] Какой знакомый код)) [/offtop]

[Гость]

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

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.

[volvo]

Любой конвертер 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. Ты уверена, что это именно двухпутевые вставки?)

[Гость]

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

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.

[Гость]

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

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.