Sắp mảng rồi ghi tệp

Sắp mảng rồi ghi tệp- gia sư tin học

               Sinh ngẫu nhiên n phần tử cho mảng nguyên a. Sắp a theo trật tự tăng dần rồi ghi vào một tệp văn bản có tên tuỳ đặt.

Gợi ý

Chương trình giới thiệu hai thủ tục sắp mảng là MinSort và QuickSort. Theo phương pháp MinSort với mỗi i ta tìm phần tử nhỏ nhất a[j] trong đoạn a[i..n] sau đó ta đổi chỗ phần tử này với phần tử a[i]. Như vậy mảng được chia thành hai đoạn: đoạn trái, a[1..i] được sắp tăng, còn đoạn phải a[i + 1..n] chưa xử lí. Mỗi bước ta thu hẹp đoạn phải cho đến khi còn một phần tử là xong.

Theo phương pháp QuickSort ta lấy một phần tử x nằm giữa đoạn mảng cần sắp làm mẫu rồi chia mảng thành hai đoạn. Đoạn trái a[1..i] bao gồm các giá trị không lớn hơn x và đoạn phải a[j..n] bao gồm các giá trị không nhỏ thua x. Tiếp đến ta lặp lại thủ tục này với hai đoạn thu được nếu chúng chứa nhiều hơn một phần tử.

(*  Pascal  *)

(*---------------------------------------

      SAPTANG: Sap mang, ghi tep

----------------------------------------*)

program SapTang;

{$B-}

uses crt;

const

MN = 5000;

fn = 'saptang.out';

var

f: text;

a: array[1..MN] of integer;

n: integer;

(*------------------------------

sinh ngau nhien m phan tu

        cho mang nguyen a

--------------------------------*)

procedure Init(m: integer);

var i: integer;

begin

if (m < 0) or (m > MN) then exit;

n:= m;

randomize;

for i:= 1 to n do a[i]:= random(MN);

end;

(*-------------------------------------

            Sap nhanh doan a[d..c]

---------------------------------------*)

procedure QuickSort(d, c: integer);

var i, j, x, y: integer;

begin

i:= d; j:= c;

x:= a[(i+j) div 2];{lay tri mau x}

while i <= j do

begin

while a[i] < x do inc(i); {to chuc doan trai}

while a[j] > x do dec(j); {to chuc doan phai}

if (i <= j) then {doi cho neu can}

    begin

y:= a[i];

a[i]:= a[j];

a[j]:= y;

inc(i); dec(j);

    end;

end;

if (d < j) then QuickSort(d,j); {sap tiep doan trai}

if (i < c) then QuickSort(i,c); {sap tiep doan phai}

end;

(*------------------------------------

Tim chi dan m trong khoang d..c

            thoa a[m] = min(a[d..c])

--------------------------------------*)

function Min(d, c: integer): integer;

var i: integer;

begin

for i:= d+1 to c do

    if a[i] < a[d] then d:= i;

Min:= d;

end;

procedure MinSort;

var i, j, y: integer;

begin

for i:= 1 to n-1 do

begin

j:= Min(i,n);

{doi cho a[i] va a[j]}

y:= a[i];

a[i]:= a[j];

a[j]:= y;

end;

end;

(*----------------------------------

      Ghi tep, moi dong khong qua 20 so

-----------------------------------*)

procedure Ghi;

var i: integer;

begin

assign(f,fn); rewrite(f);

writeln(f,n);

for i:= 1 to n do

begin

write(f,a[i]:5);

if i mod 20 = 0 then writeln(f);

end;

close(f);

end;

procedure TestQuickSort;

begin

Init(MN);

QuickSort(1,n);

Ghi;

write('Fini Quick Sort'); readln;

end;

procedure TestMinSort;

begin

Init(MN);

MinSort;

Ghi;

write('Fini Min Sort'); readln;

end;

BEGIN

TestQuickSort;

{TestMinSort;}

END.