Помощь - Поиск - Пользователи - Календарь
Полная версия: Сортировки
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Anatolik174
Ребят у меня такая проблема нам учитель задал написать 3 сортировки, дал книгу(которую я почитал) но реализацию не объяснил (да собственно говоря он никогда ничего не объяснял толком). У меня трудности заключаются в написании самих сортировок. Помогите Please написать сортировки(Пирамидальная сортировка, Быстрая сортировка, Сортировка за линейное время ).
Я написал массив и его генерацию.
Код
const
N = 10;
type
arr = array [0..N - 1] of integer;

var
a: arr;
///Генерирование массива
function rand: arr;
var
i: integer;
begin
randomize;
for i := 0 to (N - 1) do result[i] := random(100);
end;
///Вывод массива
procedure print(a: arr);
var
i: integer;
begin
for i := 0 to (N - 1) do write(a[i], ' ');
end;
Client
и да поможет тебе поиск smile.gif
Anatolik174
Спасибо поиск оказался полезным узнал много нового но и появились 2 проблемы. Вот например есть у меня сортировка простым выбором
Код

const
  N = 10;

type
  arr = array [0..N - 1] of integer;

var
  a: arr;
///Генерирование массива
function rand: arr;
var
  i: integer;
begin
  randomize;
  for i := 0 to (N - 1) do result[i] := random(100);
end;
///Вывод массива
procedure print(a: arr);
var
  i: integer;
begin
  for i := 0 to (N - 1) do write(a[i], ' ');
end;
/// сортировка массива
procedure sorting (a: arr);
    var
      min, i, k, j: integer;
    begin
    for i := 0 to N - 1 do
  begin
    min := a[i];
    k := i;
    for j := i + 1 to N - 1 do
      if a[j] < min then
      begin
        k := j;
        min := a[j];
      end;
    a[k] := a[i];
    a[i] := min;
    writeln;
    print(a);
  end;
    end;

begin
  a := rand;
  print(a);
  sorting(a);
end.

И когда её запускаешь то она пишет в решении массив и сортировку этого массива.
Например
83 30 13 85 8 58 0 30 64 36
0 30 13 85 8 58 83 30 64 36
0 8 13 85 30 58 83 30 64 36
0 8 13 85 30 58 83 30 64 36
0 8 13 30 85 58 83 30 64 36
0 8 13 30 30 58 83 85 64 36
0 8 13 30 30 36 83 85 64 58
0 8 13 30 30 36 58 85 64 83
0 8 13 30 30 36 58 64 85 83
0 8 13 30 30 36 58 64 83 85
0 8 13 30 30 36 58 64 83 85
И вот я написал точнее скопировал и подредактировал две сортировки
Пирамидальная сортировка
Код
const
  N = 10;

type
  arr = Array[0 .. N-1] Of Integer;

var
  a: arr;
///Генерирование массива
function rand: arr;
var
  i: integer;
begin
  randomize;
  for i := 0 to (N - 1) do result[i] := random(100);
end;
///Вывод массива
procedure print(a: arr);
var
  i: integer;
begin
  for i := 0 to (N - 1) do write(a[i], ' ');
end;
/// сортировка массива
Procedure HeapSort(Var ar: arr; n: Integer);
Var
   Left, Right: integer;
  x: Integer;

  Procedure sift;
  Var i, j: Integer;
  Begin
    i := Left; j := 2*i; x := ar[i];
    While j <= Right Do Begin
      If j < Right Then
        If ar[j] < ar[Succ(j)] Then Inc(j);

      If x >= ar[j] Then Break;
      ar[i] := ar[j];
      i := j; j := 2 * i
    End;

    ar[i] := x
  End;

Var T: Integer;
Begin
  Left := Succ(n div 2); Right := n;
  While Left > 1 Do Begin
    Dec(Left); sift
  End;

  While Right > 1 Do Begin
    T := ar[ Left ]; ar[ Left ] := ar[ Right ]; ar[ Right ] := T;
    Dec(Right); sift
end
End;


begin
  a := rand;
  print(a);
  
end.

Быстрая сортировка
Код
const
  N = 10;
  
Type
  arr = Array[0 .. N-1] Of Integer;
  
  var
  a: arr;
///Генерирование массива
function rand: arr;
var
  i: integer;
begin
  randomize;
  for i := 0 to (N - 1) do result[i] := random(100);
end;
///Вывод массива
procedure print(a: arr);
var
  i: integer;
begin
  for i := 0 to (N - 1) do write(a[i], ' ');
end;
/// сортировка массива

Procedure merge(Var ar: arr; n: Integer);

  Procedure Slit( k, q: Integer );
  Var
    m: Integer;
    i, j, T: Integer;
    d: arr;
  Begin
    m := k + (q-k) div 2;
    i := k; j := Succ(m); t := 1;
    While (i <= m) and (j <= q) Do Begin
      If ar[i] <= ar[j] Then Begin
        d[T] := ar[i]; Inc(i)
      End
      Else Begin
        d[T] := ar[j]; Inc(j)
      End;
      Inc(T)
    End;

    While i <= m Do Begin
      d[T] := ar[i]; Inc(i); Inc(T)
    End;
    While j <= q Do Begin
      d[T] := ar[j]; Inc(j); Inc(T)
    End;

    For i := 1 to Pred(T) Do
      ar[Pred(k+i)] := d[i]
  End;

  Procedure Sort(i, j: Integer);

  Begin
    If i >= j Then End;
    var j,i,T:integer;
   Begin
    If j-i = 1 Then Begin
      If ar[j] < ar[i] Then Begin
        T := ar[i]; ar[i] := ar[j]; ar[j] := T
      End
    End
    Else Begin
      Sort(i, i + (j-i) div 2);
      Sort(i + (j-i) div 2 + 1, j);
      Slit(i, j)
    End;
  End;

begin
  a := rand;
  print(a);
  
end.


Но не одна из этих сортировок не сортирует массивы. Помогите найти ошибочки.
Client
Цитата
И когда её запускаешь то она пишет в решении массив и сортировку этого массива.
А какой компилятор? случайно не PascalABC?
function rand: arr;
var
i: integer;
begin
randomize;
for i := 0 to (N - 1) do result[i] := random(100);
end;
Это что такое? (я про result[i] )
Anatolik174
Да компилятор как раз ABC. А вот на счет Result[i] я вас не понял
1) Это ошибка и вы мне пытаетесь намекнуть
2) Вы не знаете что это (Sorry конечно)
Ну а так то это результат [i] присвоенного к random(100)
volvo
Цитата
Но не одна из этих сортировок не сортирует массивы.
А ты хоть у одной просил сортировать? Берем "пирамиду":
begin
a := rand;
print(a);
end.
Ну, и что? Вывел массив, который был сгенерирован. Где вызов heapsort(a, n) ?

Это во-первых. Во вторых: все приведенные в FAQ-е процедуры (и там ясно видно это, между прочим) работают с массивом, индексация в котором начинается с 1, а не с 0. Правь везде индексы, если хочешь делать с zero-based массивом...
TarasBer
> А какой компилятор? случайно не PascalABC?

По-моему, эта фича запрещена только в турбопасе.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.