Sắp xếp
1. Khái niệm
a. Sắp xếp là quá trình tổ chức lại một
dãy các dữ liệu theo một trật tự nhất định.
b. Mục đích của việc sắp xếp là nhằm
giúp cho việc tìm kiếm dữ liệu dễ dàng và nhanh chóng.
Sắp xếp là một việc làm
hết sức cơ bản và được dung rộng rãi trong kĩ thuật lập trình nhằm xử lí một
dãy các dữ liệu.
c. Các giải thuật sắp xếp được phân
thành hai nhóm chính là:
Sắp xếp trong (hay sắp xếp
mảng)
Toàn bộ dữ liệu cần sắp xếp phải được đưa vào bộ nhớ chính của
máy tính, do đó nó thường được sử dụng khi khối lượng dữ liệu không vượt quá dung
lượng bộ nhớ chính.
Nhóm sắp xếp trong bao gồm các phương pháp:
Phương pháp đếm
Phương pháp chèn
Phương pháp chọn
Phương pháp đổi chỗ
Phương pháp trộn.
Sắp xếp ngoài (hay sắp xếp
tập tin)
Áp dụng trong trường hợp
ta phải sắp xếp các tập tin chứa nhiều mẫu tin và mỗi mẫu tin có chiều dài
tương đối lớn, do đó ta không thể nạp toàn bộ tập tin này vào bộ nhớ chính để sắp
thứ tự. Vì vậy ta phải có những phương pháp thích hợp cho việc sắp thứ tự tập
tin.
2. Sắp xếp trong
a. Khái niệm
Cấu trúc dữ liệu thích hợp
cho các phần tử cần sắp thứ tự là record. Mỗi phần tử có hai vùng đặc trưng là:
vùng key để chứa khóa của phần tử và được sử dụng trong các giải thuật tìm kiếm,
vùng info dùng để chứa dữ liệu của phần tử.
Ta khai báo
Type item=record
key: integer;
info: integer;
end;
var a:array[1..n] of item;
Khóa của phần tử có thể
là chữ hoặc là số
b. Phương pháp đếm
Nội dung của phương pháp
này là đếm phần tử có khóa nhỏ hơn hay bằng khóa của phần tử a[i]. Nếu có j phần
tử có khóa nhỏ hơn khóa của phần tử a[i] thì phần tử a[i] sẽ có vị trí thứ
(j+1) trong dãy đã có thứ tự
Trong giải thuật ta dùng
mảng count[i] (i=1, 2, …., n) với count[i] cho biết số phần tử có khóa nhỏ hơn
khóa của phần tử a[i]. Như vậy count[i+1] là vị trí của phần tử a[i] trong dãy
đã có thứ tự.
· Ví dụ: sắp xếp dãy 3 1 5 2 7 6 9 4
i: 1 2 3 4 5 6 7 8
a:
3 1 5 2 7 6 9 4
count: 2 0 4 1 6 5 7 3
Như vậy: phần tử có khóa 9 ở vị trí thứ 8 vì count[9]=7
· Thể hiện bằng Pascal
c.
Phương
pháp chèn
Nội dung của phương pháp này là giả sử
ta có dãy a[1]..a[i-1] đã có thứ tự ta phải xác định vị trí thích hợp của phần
tử a[i] trong dãy a[1]..a[i-1] bằng
phương pháp tìm kiếm tuần tự từ a[i-1] trở về phía a[1] để tìm ra vị trí thích
hợp của a[i]. Ta chèn a[i] vào vị trí này và cho kết quả là dãy a[1]..a[i] có
thứ tự. Ta áp dụng cách làm này với i=2, 3, .., n.
- Ví dụ:
d. Phương pháp chọn
Nội dung của phương pháp này là ở bước
thứ i (i=1, 2, 3, …, n-1) ta lựa chọn phần tử nhỏ nhất trong dãy a[i]..a[n] rồi
đổi chỗ phần tử này với phần tử a[i]. Cuối cùng ta sẽ có dãy a[1]..a[n] có thứ
tự.
- Ví dụ:
Có rất nhiều phương pháp sắp xếp dựa
trên việc đổi chỗ giữa 2 phần tử của dãy. Chẳn hạn: Bubble sort, Bubble sort cải
tiến, Shake sort, Shell sort, Quick sort. Dưới đây chúng ta sẽ xét một vài cách sắp xếp bằng
phương pháp đổi chỗ.
ü
Phương
pháp đổi chỗ Bubble sort
Nội dung của phương pháp này là ta duyệt
dãy a[1].. a[n]. Nếu a[i].key > a[i+1].key (i=1, 2, .., n-1) thì ta đổi chỗ
phần tử a[i] với phần tử a[i+1]. Lặp lại quá trình duyệt dãy này cho đến khi
không có xảy ra việc đổi chỗ của hai phần tử.
Chú ý rằng bất kì lúc nào phần tử nhỏ
nhất cũng gặp trước tiên, nó như những bọt khí nhẹ sẽ nổi lên trên khi ta đun
nước. Sau đó ở phần tử nhỏ thứ hai sẽ được đặt vào đúng vị trí. Vì vậy sắp xếp
nổi bọt thao tác như một kiểu sắp xếp chọn, mặc dù nó không làm nhiều việc hơn
để đưa từng phần tử vào đúng vị trí.
- Ví dụ:
- Thể hiện bằng Pascal
*Cải tiến Bubble sort
Ta nhận thấy rằng, nếu ở một lần
duyệt dãy nào đó mà không có xảy ra sự đổi chỗ giữa 2 phần tử thì dãy đang sắp
xếp đã có thứ tự và giải thuật kết thúc.
*Phương pháp đổi chỗ Shake sort
Phương pháp này là một cải tiến nữa của
phương pháp Bubble sort theo hướng không những phần tử nhẹ nổi lên trên mà cả
phần tử nặng cũng chìm xuống dưới giống như khi ta “rung” một cái nồi và thuật toán sắp xếp phải điều khiển cả 2 quá
trình “nổi lên” và “chìm xuống” này một cách tự giác. Muốn
vậy ta phải ghi nhớ lần đổi chỗ cuối cùng khi duyệt dãy từ dưới lên và khi
duyệt dãy từ trên xuống để quyết định trong chu trình kế tiếp sẽ chỉ duyệt từ
đây đến đâu.
- Ví dụ:
- Ví dụ:
*Phương pháp đổi chỗ Quick sort
Nội dung của phương pháp này là chọn
phần tử x ở giữa của dãy làm chuẩn để so sánh. Ta phân hoạch dãy này thành 3
dãy con liên tiếp nhau:
+ Dãy con thứ nhất gồm các phần tử có khóa nhỏ hơn x.key.
+ Dãy con thứ hai gồm các phần tử có khóa bằng x.key
+ Dãy con thứ ba gồm các phần tử có khóa lớn hơn x.key
Sau đó áp dụng giải thuật phân hoạch này cho dãy con thứ nhất và dãy con thứ ba, nếu các dãy con này có nhiều hơn một phần tử (đệ qui).
+ Dãy con thứ nhất gồm các phần tử có khóa nhỏ hơn x.key.
+ Dãy con thứ hai gồm các phần tử có khóa bằng x.key
+ Dãy con thứ ba gồm các phần tử có khóa lớn hơn x.key
Sau đó áp dụng giải thuật phân hoạch này cho dãy con thứ nhất và dãy con thứ ba, nếu các dãy con này có nhiều hơn một phần tử (đệ qui).
Cụ thể là xét một đoạn của dãy từ thành phần thứ L đến
thành phần thứ R.
- Ví dụ:
Shell sort:
-- Bubble Sort --
Uses Crt;
Const N = 10000;
Type M1 = Array[1..N] of Integer;
Var A : M1;
i,j,x : Integer;
Begin
Clrscr;
Randomize;
For i:=1 to N do A[i] := Random(10);
For i:=1 to N do Write(A[i]:4);
For i:=2 to N do
For j:=N downto i do
If A[j-1] > A[j] then
Begin
x := A[j-1];
A[j-1] := A[j];
A[j] := x;
End;
Writeln;
For i:=1 to N do Write(A[i]:4);
Readln;
End.
-- Shell Sort --
Uses Crt;
Const N = 10000;
Type M1 = Array[1..N] of Integer;
M2 = Array[1..4] of Integer;
Var A : M1;
H : M2;
i,j,m,k,s,x : Integer;
Begin
Clrscr;
Randomize;
For i:=1 to N do A[i] := Random(10);
For i:=1 to N do Write(A[i]:4);
H[1] := 1; H[2] := 3; H[3] := 5; H[4] := 9;
For m := 1 to 4 do
Begin
K := H[m];
S := -k;
For i:=K+1 to N do
Begin
x := A[i];
j := i-k;
If s=0 then s := -k;
Inc(s);
A[s] := x;
While x<A[j] do
Begin
A[j+k] := A[j];
Dec(j,k);
End;
A[j+k] := x;
End;
End;
For i:=1 to N do Write(A[i]:4);
Readln;
End.
-- QuickSort --
Uses Crt;
Const Max= 15000;
Type Chiso = 1..Max;
Mang = Array[Chiso] of Integer;
Var A : Mang;
Procedure QuickSort;
Var s,D,C,i,j : Word;
coc,x : Integer;
dP,cP : Array[Chiso] of Chiso;
Begin
s:=1;
dP[s]:=1;
cP[s]:=Max;
Repeat
D:=dP[s];
C:=cP[s];
Dec(s);
Repeat
i:=D;
j:=C;
x:= A[(D+C) div 2];
Repeat
While A[i] < x do inc(i);
While x < A[j] do dec(j);
If i<=j then
Begin
coc:=A[i]; A[i]:=A[j]; A[j]:=coc;
Inc(i);
Dec(j);
End;
Until i>j;
If i<C then
Begin
Inc(s);
dP[s]:=i;
cP[s]:=C;
End;
C:=j;
Until D>=C;
Until s=0;
End;
Không có nhận xét nào:
Đăng nhận xét