Задача на сортировку Опции

[Iriska]

Друзья!!! Объяните пожалуйста ЧТО ТУТ НАДО СДЕЛАТЬ!!

Имеется колода карт. Пусть на каждой карте зафиксировано одно натуральное число (ради простоты будем считать, что все числа попарно различны). Требуется отсортировать, т. е. упорядочить колоду карт так, чтобы зафиксированные на картах числа образовывали монотонную (возрастающую или убывающую) последовательность.
Сортировка путем предсортировки и слияния
Заданная колода х сортируется с помощью следующего предписания:

(1) если х пуста или содержит одну карту, то х отсортирована;
(2) если х содержит более одной карты, то х разделить на две непустые колоды; отсортировать каждую из них и затем слить (объединить) эти колоды в одну отсортированную колоду.

Заметим, что слияние двух колод карт с получением одной отсортированной колоды снова соответствует постановке задачи, так что оно может быть сделано обычным образом с помощью алгоритма.

Зачем делить колоду?!

М

Как не крути а задание у тебя на сортировки. Заголовок темы изменен. klem4

[Altair]

задание - сортировка массива.
методы сортировок
Просто автор задачи счел формулировку "реализовать сортировку такми-то методом" слишком банальной и решил добавить брутальности

по ссылке найдешь

3. Сортировка слияниями

Зачем делить колоду?!

явной цели нет

[klem4]

Это имхо не та сортировка которая нужна Уж как минимум два массива надо передавать в процедуру (чтобы было что слиять ) ) а там только один ... сейчас напишу то что мне кажется нужным.

[Altair]

чтобы было что слиять

это все навсего 2 процедура
а 2 части исходного массива сортируются обычным слиянием

[Iriska]

А вот еще вопрос: как должна делиться колода??

[klem4]

А вот еще вопрос: как должна делиться колода??

Хе-хе)) Ну естественно нацело!) допустим у тебя массив из n=7 элементов, тогда ты делишь его на два массивы по 3 и 4 элемента соответственно, то есть 1 массив : n div 2 (получится 3) и второй : n-n div 2 = 7-3 = 4 элемента.

Сообщение отредактировано: klem4 - 20.11.2005 22:28

[klem4]

Вобщем вот такая штука получилась :

program _koloda;

uses crt;

type

   TArray = array[1..50] of integer;
var
   a : TArray; // колода;
   b,c : TArray;

   (* b,c - две части на которые мы ее подилм, а результат
      запишем в a
   *)

   n : byte; // размерность колоды

procedure InputArray(var x : TArray; size : byte);
var
   i : byte;
begin
   for i := 1 to size do begin
      write('a[',i,']=');
      readln(a[i]);
   end;
end;

procedure PrintArray(x : TArray; size : byte);
var
   i : byte;
begin
   for i := 1 to size do writeln(x[i]);
end;

procedure Sort(var x : TArray; size : byte); // сортировка
var
   i, temp : byte;
   flag : boolean;
begin
   repeat
      flag := true;
      for i := 1 to size-1 do
       if not(x[i]<=x[i+1]) then begin
          flag := false;
          temp := x[i];
          x[i] := x[i+1];
          x[i+1] := temp;
       end;
   until flag;
end;

procedure ConCatArray(x : TArray; size : byte; var y,z : TArray);
var
   i, j : byte;
begin
   for i := 1 to n div 2 do y[i] := x[i]; // размер первого : n div 2
   j := 0;
   for i := n div 2 + 1 to n do begin
      inc(j);
      z[j] := x[i];
   end;
// размер второго : n - n div 2
end;

procedure Additional(x1, x2 : TArray; size1,size2 : byte; var result : TArray);
var
  i1, i2, count : byte;
  i : byte; // можно и без нее 
begin
   i1 := 1;
   i2 := 1;
   count := 0;
   while (i1<=size1) and (i2<=size2) do begin
      inc(count);
      if x1[i1]<=x2[i2] then begin
         result[count] := x1[i1];
         inc(i1);
      end
       else begin
          result[count] := x2[i2];
          inc(i2);
       end;
   end;

   if i1<= size1 then
    for i := i1 to size1 do begin
       inc(count);
       result[count] := x1[i];
    end
     else
      for i := i2 to size2 do begin
         inc(count);
         result[count] := x2[i];
      end;
end;



begin

   clrscr;

   write('Введите количество элементов в колоде : ');

   readln(n);

   writeln('Введите элементы колоды : ');

   InputArray(a, n);

   writeln;

   ConCatArray(a, n, b, c);

   Sort(b, n div 2);

   Sort(c, n - n div 2);

   Additional(b, c, n div 2, n - n div 2, a);

   PrintArray(a, n);

   readln;
end.

[Iriska]

Гениально!! Спасибо, кажется я поняла этот метод.....