8. Тексты программ

QuickSort.cpp

Точки измерения только в главной программе #include <stdlib.h> #include <stdio.h> #include "sampler.h" ypedef double TArray[21]; void swap(double &p, double &q) { double tmp = p; p = q; q = tmp; } void qsort(TArray x, int n) { int left [21]; int right [21]; left [1] = 1; right [1] = n; int sp = 1; int i = 0; int j = 0; int mid = 0; double pivot; while (sp) { if ( left [sp] >= right[sp]) { sp−−; } else { i = left [sp ]; j = right [sp ]; pivot = x[j ]; mid = ((i+j) / 2); if (( j − i) > 5) { if ( (( x[mid] < pivot) && (x[mid] > x[i])) || (( x[mid] > pivot) && (x[mid] < x[i])) ) { swap(x[mid], x[j ]) ; } else { if ( (( x[ i ] < x[mid]) && (x[i] > pivot)) || (( x[ i ] > x[mid]) && (x[i] < pivot)) ) { swap(x[i ], x[ j ]) ; } } } pivot = x[j ]; while (i < j) { while (x[ i ] < pivot) { i++; } j−−; while ((i < j) && (pivot < x[j])) { j−−; } if ( i < j) { swap(x[i ], x[ j ]) ; } } j = right [sp ]; swap(x[i ], x[ j ]) ; if ( i − left [sp] >= right[sp] − i ) { left [sp+1] = left[sp ]; right [sp+1] = i − 1; left [sp] = i + 1; } else { left [sp+1] = i + 1; right [sp+1] = right[sp]; right [sp] = i − 1; } sp++; } } } int verify (TArray &x, int dim) { int i = 1; while ((x[ i] <= x[i+1]) && (i+1 <= dim)) { i++; } if ( i == dim) { return 0; } else { return 1; } } void init(TArray &x, int dim) { for ( int i = 0; i <= dim; i++) { x[ i ] = random(100); } } void main() { SAMPLE; TArray a; int m = 20; randomize(); SAMPLE; init (a, m); SAMPLE; qsort(a, m); SAMPLE; verify (a, m); SAMPLE; }

Точки измерения только в процедуре сортировки #include <stdlib.h> #include <stdio.h> #include "sampler.h" ypedef double TArray[21]; void swap(double &p, double &q) { double tmp = p; p = q; q = tmp; } void qsort(TArray x, int n) { SAMPLE; int left [21]; int right [21]; left [1] = 1; right [1] = n; int sp = 1; int i = 0; int j = 0; int mid = 0; double pivot; SAMPLE; while (sp) { SAMPLE; if ( left [sp] >= right[sp]) { sp−−; } else { i = left [sp ]; j = right [sp ]; pivot = x[j ]; mid = ((i+j) / 2); SAMPLE; if (( j − i) > 5) { if ( (( x[mid] < pivot) && (x[mid] > x[i])) || (( x[mid] > pivot) && (x[mid] < x[i])) ) { SAMPLE; swap(x[mid], x[j ]) ; } else { if ( (( x[ i ] < x[mid]) && (x[i] > pivot)) || (( x[ i ] > x[mid]) && (x[i] < pivot)) ) { SAMPLE; swap(x[i ], x[ j ]) ; } } } SAMPLE; pivot = x[j ]; while (i < j) { while (x[ i ] < pivot) { i++; } SAMPLE; j−−; while ((i < j) && (pivot < x[j])) { j−−; } SAMPLE; if ( i < j) { swap(x[i ], x[ j ]) ; } SAMPLE; } SAMPLE; j = right [sp ]; swap(x[i ], x[ j ]) ; if ( i − left [sp] >= right[sp] − i ) { left [sp+1] = left[sp ]; right [sp+1] = i − 1; left [sp] = i + 1; } else { left [sp+1] = i + 1; right [sp+1] = right[sp]; right [sp] = i − 1; } sp++; SAMPLE; } } SAMPLE; } int verify (TArray &x, int dim) { int i = 1; while ((x[ i] <= x[i+1]) && (i+1 <= dim)) { i++; } if ( i == dim) { return 0; } else { return 1; } } void init(TArray &x, int dim) { for ( int i = 0; i <= dim; i++) { x[ i ] = random(100); } } void main() { TArray a; int m = 20; randomize(); init (a, m); qsort(a, m); verify (a, m); }

QuickSort.pas

Точки измерения только в главной программе program prog_pas; uses sampler; const N = 100; name = "prog_pas.pas"; type TArray = array [1..N] of real; procedure swap(var p,q: real); var hold : real ; begin hold:=p; p:=q; q:=hold end; procedure qsort(var x: TArray; n: integer); var left , right : array[1..20] of integer ; i , j ,sp,mid : integer ; pivot : real ; begin left [1]:=1; right [1]:=n; sp:=1; while sp>0 do begin if left [sp]>=right[sp] then begin sp:=sp−1 end else begin i:=left [sp ]; j:=right[sp ]; pivot:=x[j ]; mid:=(i+j)div 2; if ( j−i)>5 then begin if ((x[mid]<pivot)and(x[mid]>x[i])) or ((x[mid]>pivot)and(x[mid]<x[i])) then begin swap(x[mid],x[j ]) end else begin if ((x[ i]<x[mid])and(x[i]>pivot)) or ((x[i]>x[mid])and(x[i]<pivot)) then begin swap(x[i ], x[ j ]) ; end; end; end; pivot:=x[j ]; while i<j do begin while x[i]<pivot do begin i:=i+1; end; j:=j−1; while (i<j)and(pivot<x[j]) do begin j:=j−1; end; if i<j then swap(x[i],x[j ]) ; end; j:=right[sp ]; { pivot to i } swap(x[i ], x[ j ]) ; if i−left [sp]>=right[sp]−i then begin left [sp+1]:=left[sp ]; right [sp+1]:=i−1; left [sp]:=i+1 end else begin left [sp+1]:=i+1; right [sp+1]:=right[sp]; right [sp]:=i−1 end; sp:=sp+1; end; end; end; function verify(var x: TArray; dim: integer) : boolean; var i : integer ; begin i := 1; while (x[i] <= x[i+1]) and (i+1 <= dim) do begin i := i+1; end; if ( i = dim) then verify := true else verify := false ; end; procedure init(var x: TArray; dim: integer); var i : integer ; begin for i := 1 to dim do begin x[ i ] := random(100); end; end; var a: TArray; t : integer ; begin sample(name, 1); randomize; sample(name, 2); init (a, n); sample(name, 3); qsort(a, n); sample(name, 4); verify (a, n); sample(name, 5); end.

Точки измерения только в процедуре сортировки program prog_pas; uses sampler; const N = 100; name = "prog_pas.pas"; type TArray = array [1..N] of real; procedure swap(var p,q: real); var hold : real ; begin hold:=p; p:=q; q:=hold end; procedure qsort(var x: TArray; n: integer); var left , right : array[1..20] of integer ; i , j ,sp,mid : integer ; pivot : real ; begin sample(name, 11); left [1]:=1; right [1]:=n; sp:=1; sample(name, 12); while sp>0 do begin sample(name, 13); if left [sp]>=right[sp] then begin sp:=sp−1 end else begin i:=left [sp ]; j:=right[sp ]; pivot:=x[j ]; mid:=(i+j)div 2; sample(name, 14); if ( j−i)>5 then begin if ((x[mid]<pivot)and(x[mid]>x[i])) or ((x[mid]>pivot)and(x[mid]<x[i])) then begin sample(name, 15); swap(x[mid],x[j ]) end else begin if ((x[ i]<x[mid])and(x[i]>pivot)) or ((x[i]>x[mid])and(x[i]<pivot)) then begin sample(name, 16); swap(x[i ], x[ j ]) ; end; end; end; sample(name, 17); pivot:=x[j ]; while i<j do begin while x[i]<pivot do begin i:=i+1; end; sample(name, 19); j:=j−1; while (i<j)and(pivot<x[j]) do begin j:=j−1; end; sample(name, 20); if i<j then swap(x[i],x[j ]) ; sample(name, 21); end; sample(name, 22); j:=right[sp ]; { pivot to i } swap(x[i ], x[ j ]) ; if i−left [sp]>=right[sp]−i then begin left [sp+1]:=left[sp ]; right [sp+1]:=i−1; left [sp]:=i+1 end else begin left [sp+1]:=i+1; right [sp+1]:=right[sp]; right [sp]:=i−1 end; sp:=sp+1; sample(name, 23); end; end; sample(name, 24); end; function verify(var x: TArray; dim: integer) : boolean; var i : integer ; begin i := 1; while (x[i] <= x[i+1]) and (i+1 <= dim) do begin i := i+1; end; if ( i = dim) then verify := true else verify := false ; end; procedure init(var x: TArray; dim: integer); var i : integer ; begin for i := 1 to dim do begin x[ i ] := random(100); end; end; var a: TArray; t : integer ; begin randomize; init (a, n); qsort(a, n); verify (a, n); end.

10