Ребят у меня такая проблема нам учитель задал написать 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 14.12.2010 16:18
и да поможет тебе поиск
Автор: Anatolik174 14.12.2010 17:24
Спасибо поиск оказался полезным узнал много нового но и появились 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 14.12.2010 18:39
Цитата
И когда её запускаешь то она пишет в решении массив и сортировку этого массива.
А какой компилятор? случайно не PascalABC?
function rand: arr; var i: integer; begin randomize; for i := 0 to (N - 1) do result[i] := random(100); end;
Это что такое? (я про result[i] )
Автор: Anatolik174 14.12.2010 18:44
Да компилятор как раз ABC. А вот на счет Result[i] я вас не понял 1) Это ошибка и вы мне пытаетесь намекнуть 2) Вы не знаете что это (Sorry конечно) Ну а так то это результат [i] присвоенного к random(100)
Автор: volvo 14.12.2010 19:49
Цитата
Но не одна из этих сортировок не сортирует массивы.
А ты хоть у одной просил сортировать? Берем "пирамиду":
begin a := rand; print(a); end.
Ну, и что? Вывел массив, который был сгенерирован. Где вызов heapsort(a, n) ?
Это во-первых. Во вторых: все приведенные в FAQ-е процедуры (и там ясно видно это, между прочим) работают с массивом, индексация в котором начинается с 1, а не с 0. Правь везде индексы, если хочешь делать с zero-based массивом...