Luyện thi HSG pascal

                                           CHƯƠNG II. MỘT SỐ THUẬT TOÁN SẮP XẾP

                Không mất tính tổng quát ta sẽ trình bày các thuật toán sắp xếp cho bài toán sau. Cho dãy n gồm số nguyên a1, a2, a3, …, an. Yêu cầu sắp xếp thành dãy tăng không ngặt (dãy không giảm).

                Tùy vào từng bài toán chúng ta đánh giá được độ phức tạp của bài toán , để lựa chọn cách sắp xếp hợp lý.

for i:= 2 to n do

    for j:= n dowto I do

          if a[j] < a[j-1] then   doicho(a[j],a[j-1])

độ phức tạp của bài toán là O(n²).

    For i:= 1 to n-1 do

          For j:= i+1 to n do

                  If (a[i] > a[j]) then

                  Doicho(a[i],a[j]);

Ý tưởng của thuật toán là dùng mảng dem để đếm số lần xuất hiện của a[i] trong dãy.

Fillchar(dem, sizeof(dem),0);

For i:= 1 to n do inc(dem[a[i]]);

                                        ///// dem[a[i]]:= dem[a[i]] +1;

for i:= <giá trị nhỏ nhất của a[i]>

                                         to <giá trị lớn nhất của a[i]] >  do

        for j:= 1 to dem[i] do write(I,’ ‘);

3. Thuật toán sắp xếp nhanh (Qick sort)

        Ý tưởng: chọn một phần từ làm chốt( ở đây ta chọn vị trí giữa). Từ trái sang tìm phần từ có vị trí I lớn hơn hoặc bằng phần tử chốt. Nếu i<=j thì đổi chỗ 2 phần tử. Làm cho đến khi i>j. Lúc này sẽ chia ra được 2 nhóm cần sắp xếp. Làm tương tự như vậy với mỗi nhóm cho đến khi đã sắp xếp hết dãy.

Procedure       qicksort(l, r: longint)           ////{l: left: trái,    r: right: phải,       m: mid: giữa}

Var I, j, tg, mid: longint;

Begin

     i:= l; j:= r;

     mid:= a[(l+r) div 2];

     repeat

              while a[i] < mid do inc(i);

              while a[j] > mid do dec(j);

              if i<= j then

                   begin

                           tg:= a[i];

                           a[i]:= a[j];

                           a[j]:= tg;

                            inc(d); dec(j);

                    end;

        until i>j;

if i<r then qicksort(i,r);

if j>l then qicksort(l,j);

Độ phức tạp thuật toán là O(NlogN).
.