SẮP XẾP VÀ TÌM KIẾM

Gv: PHAN THỊ NGA
NỘI DUNG
I. SẮP XẾP
1/ SẮP XẾP BẰNG PHƯƠNG PHÁP LỰA CHỌN
2/ SẮP XẾP BẰNG PHƯƠNG PHÁP TRAO ĐỔI
II. TÌM KIẾM
1/ TÌM KIẾM TUẦN TỰ
2/ TÌM KIẾM NHỊ PHÂN
BÀI TOÁN MỞ ĐẦU
Cho 1 dãy hình sau hãy cho biết có bao nhiêu cách sắp xếp ?
8
4
10
1
5
5
2
Sắp xếp là gì ?
8
4
10
1
5
5
2
I/ SẮP XẾP
VD: Cho dãy {a1 ,a2,. . . an) bất kì, cần sắp xếp lại vị trí của các phần tử trong dãy sao cho sau khi sắp xếp sẽ được dãy tăng hoặc giảm dần . Điều kiện (ai<=ai+1 hoặc ai>=ai+1).Thỏa mãn với mọi i (1<=i<=n-1)
Cho dãy A={3,6,5,8,1,9}, B={d,e,a,b,g,c}
Sau khi sắp xếp A={1,3,5,6,8,9,}; B={a,b,c,d,e,g}
hoặc A={9,8,6,5,3,1}, B={g,e,d,c,b,a}
* Vậy sắp xếp là tổ chức lại dữ liệu theo một trật tự nhất định, mục đích của sắp xếp là giúp cho việc tìm kiếm dữ liệu trên một dãy được dễ dàng hơn.
NỘI DUNG
SẮP XẾP
SẮP XẾP BẰNG PHƯƠNG PHÁP LỰA CHỌN
SẮP XẾP BẰNG PHƯƠNG PHÁP TRAO ĐỔI
NỘI DUNG
SẮP XẾP
SẮP XẾP BẰNG PHƯƠNG PHÁP LỰA CHỌN
SẮP XẾP BẰNG PHƯƠNG PHÁP TRAO ĐỔI
1/ Sắp xếp bằng phương pháp lựa chọn (selection sort)
Mảng A được khai báo : A: array[1..n] of integer;
Thuật toán sắp xếp mảng theo thứ tự tăng dần
* Ý tưởng thuật toán
- Chọn ra thành phần nhỏ nhất, hoán vị cho thành phần đầu tiên trong dãy,chọn ra thành phần nhỏ thứ 2, hoán vị cho thành phần thứ 2 trong dãy , tiếp tục thực hiện cho đến khi gặp thàh phần cuối cùng vì sau thành phần cuối sẽ không còn thành phần nào để so sánh nữa .
- Phương pháp này hình thành 2 vòng lặp:
+ Vòng lặp thứ nhất là lấy thành phần thứ i đi từ 1 đến n-1
+ So sánh và hoán vị với các thành phần thứ J, với J đi từ i+1 đến n là vòng lặp thứ 2.
NỘI DUNG
SẮP XẾP
SẮP XẾP BẰNG PHƯƠNG PHÁP LỰA CHỌN
SẮP XẾP BẰNG PHƯƠNG PHÁP TRAO ĐỔI
1/ Sắp xếp bằng phương pháp lựa chọn (selection sort)
Gọi i là chỉ số thành phần lúc đầu thực hiện vòng lặp , j:=i+1 để so sánh với thành phần thứ i, Min là số thành phần nhỏ nhất sau mỗi lần sắp xếp, tạm là giá trị trung gian khi đổi chổ.
* Giải thuật trình bày:
+ Cho i từ 1 đến n-1 thực hiện
+ Cho j từ i+1 đến n thực hiện
+ Nếu thành phần thứ j nhỏ hơn thành phần thứ i thì hoán vị .



Procedure sapseptangdanday;
Var I,j,tam,min: integer;
Begin
For i:=1 to n-1 do
Begin
Min:=i;
For j:=i+1 to n do
If a[min]>a[j] then Min:=j;
Tam:=a[i];
a[i]:=a[min];
a[min]:=tam;
End;
End;

Minh họa
1/Sắp xếp bằng phương pháp lựa chọn
Hãy nêu cách sắp xếp dãy theo thứ tự giảm dần?
Trong mảng có 2 giá trị trùng nhau thì thực hiện như thế nào?
TL: Giá trị đứng trước lấy ra trước, giá trị đứng sau lấy ra sau theo thứ tự trong dãy.
TL: Chỉ cần thay đổi phép so sánh
{1,2,4,5,8,12,10}
8
5
5
{1,2,4,5,8,12,10}
5
6
4
{1,2,4,12,8,5,10}
4
3
3
{1,2,4,12,8,5,10}
2
6
2
{1,5,4,12,8,2,10}
1
2
1
A={5,1,4,12,8,2,10}
A[min]
min
i
{1,2,4,5,8,10,12}
10
7
6
7
8
6
4
3
3
1
7
7
6
7
8
6
4
3
3
1
6
5
5
7
8
4
6
3
3
1
4
5
4
7
8
4
3
6
3
1
3
4
3
7
8
4
3
3
6
1
3
3
2
7
8
4
3
1
6
3
1
3
1
7}
8
4
3
1
6
{3
A[min]
min
i
back
a[i]
a[j]
<
a[i]
a[j]
<
a[i]
a[j]
<
a[i]
a[j]
<
a[i]
a[j]
=
a[i]
a[j]
<
NỘI DUNG
SẮP XẾP
SẮP XẾP BẰNG PHƯƠNG PHÁP LỰA CHỌN
SẮP XẾP BẰNG PHƯƠNG PHÁP TRAO ĐỔI
2/ Sắp xếp bằng phương pháp trao đổi (exchange sort)
Thuật toán sắp xếp mảng theo thứ tự tăng dần
Ý tưởng thuật toán
Duyệt qua toàn bộ dãy nhiều lần, việc so sánh hoán vị được thực hiện theo từng cặp giữa thành phần thứ i với thành phần thứ i+1
Lần đầu tiên i đi từ 1 đến n-1,sau mỗi lần duyệt qua dãy các phần tử nhỏ nổi lên vị trí đầu các phần tử lớn chìm xuống gần vị trí cuối, (phần thứ n chứa giá trị lớn), tiếp tục thực hiện duyệt dãy lần hai so sánh và hoán vị giữa thành phần thứ i với i+1 (i=1..n-1) vì n không cần so sánh nữa, tương tự lần duyệt k sẽ so sánh đến thành phần thứ N-k+1.
* Giải thuật trình bày:
+ Cho J giảm từ n đến 2 thực hiện
+ Cho i tăng từ 1 đến j-1 thực hiện
+ Nếu thành phần thứ i+1 nhỏ hơn thành phần thứ i thì hoán vị
2/ Sắp xếp bằng phương pháp trao đổi (exchange sort)
NỘI DUNG
SẮP XẾP
SẮP XẾP BẰNG PHƯƠNG PHÁP LỰA CHỌN
SẮP XẾP BẰNG PHƯƠNG PHÁP TRAO ĐỔI
Gọi j là chỉ số thành phần cuối cùng được so sánh ,với j giảm từ n đến 2 sau mỗi lần duyệt chúng ta so sánh cặp thành phần thứ i với i+1 ( i:={1. . J-1}).

Procedure sapseptangdan;
Var I,j,tam: integer;
Begin
For j:=n downto 2 do
For i:=1 to j-1 do
If a[i]>a[i+1] then
Begin
Tam:=a[i];
a[i]:=a[i+1];
a[i+1]:=Tam;
End;
End;

Minh họa


{1,2,4,5,8,10,12}
-
5
{1,2,4,5,8,10,12}
2
4
{1,4,2,5,8,10,12}
3
3
{1,4,5,2,8,10,12}
4
2
{1,4,5,8,2,10,12}
1,2,4,5,6,7
1
A={5,1,4,12,8,2,10}
Đổi chổ
Lần lặp
2/ Sắp xếp bằng phương pháp trao đổi
Nếu dãy là số thực hay kí tự thì khai báo có gì thay đổi không?
TL: Thay kiểu dữ liệu cho biến tạm và cho mảng.
back
}
12
5
2
4
1
{
2
3
}
12
2
5
4
1
{
3
2
}
2
12
4
1
5
{
1,2,4,5
1
}
2
12,
4,
1,
5,
A={
Đổi chổ
Lần lặp
a[i+1]
a[i]
>
a[i+1]
a[i]
>
a[i+1]
a[i]
>
a[i+1]
a[i]
>
a[i+1]
a[i]
>
}
12
5
4
2
1
{
-
4
5

Củng cố

Hãy so sánh giữa hai thủ tục?
Duyệt dãy i từ 1 đến n-1
Hoán vị cho nhau theo từng cặp giữa phần tử thứ i và i+1 với i từ 1 đến j-1.
(J giảm dần từ n tới 2 sau mỗi lần duyệt).
Duyệt qua dãy j từ i+1 đến n Lần lượt so sánh với thành phần thứ I để chọn ra thành phần nhỏ(lớn) nhất.
Hoán vị cho các vị trí từ i={1..n-1} của dãy.
Sắp xếp trao đổi
Sắp xếp lựa chọn

Bài 1: Viết chương trình sắp xếp dãy số thực, dãy kí tự được nhập từ bàn phím theo thứ tự tăng (giảm) dần?

Bài 2: Hãy cho biết có khoảng bao nhiêu phép so sánh đối với mỗi phương pháp sắp xếp đã học biết rằng dãy cần sắp xếp có n số nguyên?


bài tập về nhà