Помощь - Поиск - Пользователи - Календарь
Полная версия: Сортировка вставками...
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Jill
сама тестовая (на числах) прога:

uses Crt,Dos;
const ARRAYSIZE=10; 
type arrayType=array[1..ARRAYSIZE] of integer;
var
  A:arrayType;
  i:integer;
  c:integer;
  n:integer;
 
procedure InsertionSort(Size:integer;var theArray:arrayType);
var
  B:array[1..2*ArraySize]of integer;
  mn,mx,c,d:word;
begin
B[Arraysize]:=A[1];
mn:=arraysize;
mx:=arraysize;
for i:=2 to ArraySize do
begin
  if A[i]<B[ArraySize] then
    begin
       for d:=mn to ArraySize do
          begin
            if (B[d]<=A[i])and(mn<>Arraysize) then
               B[d-1]:=B[d]
            else begin
                  B[d-1]:=A[i];
                  break;
                  end;
          end;
     mn:=mn-1;
    end
    else
    begin
       for d:=mx downto ArraySize do
         begin
           if (B[d]>=A[i])and(mx<>ArraySize)then
              B[d+1]:=B[d]
           else begin
                  B[d+1]:=A[i];
                  break;
                end;
         end;
        mx:=mx+1;
    end;
end;
c:=0;
for i:=mn to mx do
begin
 c:=c+1;
 A[c]:=B[i];
end;
end;{InsertionSort}

procedure Vector(SIZE,MAX:integer;var theArray:arrayType);
var i:integer;
begin
  randomize;
  for i:=1 to SIZE do
   theArray[i]:=random(MAX);
end;{Vector}

procedure PrintVector(SIZE,MAX:integer;var theArray:arrayType);
var i:integer;
begin
  for i:=1 to SIZE do
   Write(theArray[i],' ');
end;{Vector}


begin
ClrScr;
       Write('N=');
       Readln(n);
       Vector(n,ARRAYSIZE,a);
       PrintVector(n,ARRAYSIZE,a);
       Writeln;
       InsertionSort(n,a);
       PrintVector(n,ARRAYSIZE,a);   readln;

end.


работает при n=10 (по условию надо n<=50) и цифрах от 1 до 10...
если я правильно понимаю:
- при сортировке символов сортируются их коды - символы выводятся только на экран
- коды - от 0 до 127 (???)

почему же ее глючит при попытке вывести на экран символы (пробелы выдает, системник пищать начинает) или при изменении количества элементов (n)???

подскажите, ПЛЗ!
volvo
Jill, секунду...
Цитата
почему же ее глючит при попытке вывести на экран символы (пробелы выдает, системник пищать начинает) или при изменении количества элементов (n)???
Покажи, как именно ты меняешь количество элементов (или как сортируешь символы и выводишь их на экран)...

Подозреваю следующее: ты наверное делаешь вот так
       Write('N=');
       Readln(n); { вводишь, например, 40 }
       Vector(n,ARRAYSIZE,a); { <-- Здесь будет ошибка... }
       PrintVector(n,ARRAYSIZE,a);
       Writeln;
       InsertionSort(n,a);

... потому, что ты попытаешься заполнить массив A (содержащий ArraySize элементов) бОльшим количеством данных...
Jill
с количеством так и делаю... unsure.gif

а сортировка... только так додумалась:

.............
procedure PrintVector(SIZE,MAX:integer;var theArray:arrayType);
var i:integer;
begin
  for i:=1 to SIZE do
   Write(Chr(theArray[i]),' ');
end;{Vector}
................


глупо, наверное... sad.gif
volvo
Цитата(Jill @ 19.09.2005 22:12)
с количеством так и делаю... unsure.gif

Я так и думал smile.gif ... У тебя в программе есть небольшой недочет... Ты передаешь для сортировки TheArray, а работаешь почему-то с массивом A, и size тоже не используется. Вот я тут подправил немного:

uses Crt,Dos;
type
  TType = Integer;
  { TType = Char; }

const
  maxSize = 50;
type
  arrayType=array[1 .. maxSize] of TType;

var
  i:integer;
  c:integer;
  n:integer;

procedure InsertionSort(Size:integer;var A:arrayType);
var
  B:array[1 .. 2*maxSize]of ttype;
  mn,mx,c,d:word;
begin
  B[size]:=A[1]; mn:=size; mx:=size;

  for i:=2 to Size do begin
    if A[i]<B[Size] then begin

      for d:=mn to Size do begin
        if (B[d]<=A[i])and(mn<>size) then B[d-1]:=B[d]
        else begin
          B[d-1]:=A[i]; break;
        end;
      end;

      mn:=mn-1;
    end { if }
    else begin

       for d:=mx downto Size do begin
         if (B[d]>=A[i])and(mx<>Size) then B[d+1]:=B[d]
         else begin
           B[d+1]:=A[i]; break;
         end;
       end;

       mx:=mx+1;
    end; { else }
  end; { for }

  c:=0;
  for i:=mn to mx do begin
    c:=c+1;
    A[c]:=B[i];
  end;
end; { InsertionSort }

procedure Vector(size, min, max: integer;
  var theArray: arrayType);
var i:integer;
begin
  randomize;
  for i:=1 to size do
    theArray[i]:=random(max);
end; { Vector }

procedure PrintVector(SIZE:integer;var theArray:arrayType);
var i:integer;
begin
  for i:=1 to SIZE do
    Write(theArray[i],' ');
end;


const
  minValue = 0;
  maxValue = 100;
var
  a: arrayType;

begin
  ClrScr;
  Write('N='); Readln(n);
  Vector(n,minvalue,maxvalue,a);
  PrintVector(n,a);
  Writeln;
  InsertionSort(n,a);
  PrintVector(n,a);
  readln;
end.


Это для типа Integer (при N <= maxSize). Чтобы нормально сортировался Char, нужно сделать минимум изменений:
1. TType = Char вместо Integer
2. Изменить Vector чтобы генерировались символы, а не числа:
procedure Vector(size, min, max: integer;
  var theArray: arrayType);
var i:integer;
begin
  randomize;
  for i:=1 to size do
    theArray[i] := chr(random(max-min)+min);
end;

3. Сама основная программа:
const
  minValue = 65; { A }
  maxValue = 90; { Z }
var
  a: arrayType;
begin
  ClrScr;
  Write('N='); Readln(n);
  Vector(n,minvalue,maxvalue,a);
  PrintVector(n,a);
  Writeln;
  InsertionSort(n,a);
  PrintVector(n,a);
  readln;
end.
Jill
здорово :D ПАСИБА!!!

отдельное спасибо за

begin
  randomize;
  for i:=1 to size do
    theArray[i] := chr(random(max-min)+min); {<--- вот это}
end;


не знала, как именно большие буквы латиницы использовать (куда именно эти 65-90 припхнуть ;)) а то со значочками как-то сложновато проверять сортировку ;)

volvo, последний вопросик по теме: для тестового просмотра перестановок (это чисто для себя - разобраться окончательно в алгоритме сортировки)правильно ли я делаю:
1) переставляю PrintVector перед InsertionSort
2) в InsertionSort вставляю PrintVector в самом конце:

 ....................
c:=0;
  for i:=mn to mx do begin
    c:=c+1;
    A[c]:=B[i]; 
   PrintVector(n,a);  {<--- вот тут}
  end;
end; { InsertionSort }
.......................


ну еще writeln для читабельности...
выводит ли оно реальные перестановки?
volvo
Цитата(Jill @ 19.09.2005 23:42)
выводит ли оно реальные перестановки?

:no: Реальные перестановки делаются перед этим, и происходят в массиве B. То, что выводится у тебя - это просто поэлементное волшебное превращение еще не отсортированного массива A в уже отсортированный. smile.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.