25
25
Khái niệm nghòch thế
• Khái niệm nghòch thế:
– Xét một mảng các số a
0
, a
1
, … a
n
.
– Nếu có i<j và a
i
> a
j
, thì ta gọi đó là một nghòch
thế.
• Mảng chưa sắp xếp sẽ có nghòch thế.
• Mảng đã có thứ tự sẽ không chứa nghòch thế.
a
0
≤
≤≤
≤ a
1
≤
≤≤
≤ … ≤
≤≤
≤ a
n

Ph
Ph
ứ
ứ
c ta
c ta
ï
ï
p hơn
p hơn
Hie
Hie
ä
ä
u qua
u qua
û
û
cao
cao
Lơ
Lơ
ù
ù
p thua
p thua
ä
ä
t toa
t toa

– Xem dãy hiện hành chỉ còn N-1 phần tử của dãy
ban đầu, bắt đầu từ vò trí thứ 2; lặp lại quá trình
trên cho dãy hiện hành... đến khi dãy hiện hành
chỉ còn 1 phần tử.
28
28
Selection sort – Thuật toán
//input: dãy (a, N)
//output: dãy (a, N) đã được sắp xếp
• Bước 1 : i = Vò trí đầu;
• Bước 2 : Tìm phần tử a[min] nhỏ nhất trong dãy
hiện hành từ a[i] đến a[N]
• Bước 3 : Nếu min
≠
≠≠
≠ i: Hoán vò a[min] và a[i]
• Bước 4 : Nếu i chưa là Vò trí cuối
» i = Vò trí kế(i);
» Lặp lại Bước 2
Ngược lại: Dừng. //N phần tử đã nằm
đúng vò trí.
29
29
Selection sort – Ví duï
2 8 5 1 6 4 1512
i
min
2 3 4 5 6 7 81
Find MinPos(1, 8)
Swap(a

32
32
Selection sort – Ví duï
2 4 5 12 6 8 151
i
min
2 3 4 5 6 7 81
Find MinPos(4, 8)
Swap(a
i
, a
min
)
33
33
Selection sort – Ví duï
2 4 5 12 6 8 151
i
min
2 3 4 5 6 7 81
Find MinPos(5, 8)
Swap(a
i
, a
min
)
34
34
Selection sort – Ví duï
2 4 5 6 12 8 151

for (int i=0; i<N-1 ; i++)
{
min = i;
for(int j = i+1; j < N ; j++)
if (a[j] < a[min])
min = j; // ghi nhận vò trí phần tử nhỏ nhất
if (min != i)
Swap(a[min], a[i]);
}
}
37
37
• Số lần hoán vò (một hoán vò bằng 3 phép
gán) phụ thuộc vào tình trạng ban đầu
của dãy số
Selection sort – Đánh giá giải thuật
38
38
Selection sort – Đánh giá giải thuật
• Ởû lượt thứ i, cần (N-i) lần so sánh để xác
đònh phần tử nhỏ nhất hiện hành.
• Số lượng phép so sánh không phụ thuộc vào
tình trạng của dãy số ban đầu.
• Trong mọi trường hợp, số lần so sánh là:
2
1)n(n
i)(n
1n
1i
−

2
,... ,a
i
trở nên có thứ tự.
– Vò trí này chính là pos thỏa a
pos-1
≤ a
i
< a
pos
(1≤
≤≤
≤pos≤
≤≤
≤i).
Chi tiết hơn:
– Dãy ban đầu a
1
, a
2
,..., a
n
, xem như đã có đoạn gồm một
phần tử a
1
đã được sắp.
– Thêm a
2
vào đoạn a
1

2....
a
N
được sắp.
40
40
Insertion Sort – Thuật toán
//input: dãy (a, N)
//output: dãy (a, N) đã được sắp xếp
• Bước 1
: i = 2; // giả sử có đoạn a[1] đã được sắp
• Bước 2
: x = a[i]; Tìm vò trí pos thích hợp trong đoạn
a[1]
đến a[i] để chèn x vào
• Bước 3
: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang
phải 1 vò trí để dành chổ cho x
• Bước 4
: a[pos] = x; // có đoạn a[1]..a[i] đã được sắp
• Bước 5
: i = i+1;
Nếu i ≤
≤≤
≤ n : Lặp lại Bước 2.
Ngược lại : Dừng.
41
41
Insertion Sort – Ví duï
2 8 5 1 6 4 1512

2 3 4 5 6 7 81
pos
Insertion Sort – Ví duï
Insert a
4
into (1, 4)
5
45
45
5 8 12 1 6 4 152
i
x
2 3 4 5 6 7 81
pos
Insertion Sort – Ví duï
Insert a
5
into (1, 5)
1
46
46
2 5 8 12 6 4 151
i
x
2 3 4 5 6 7 81
pos
Insertion Sort – Ví duï
Insert a
6
into (1, 6)

Insertion Sort – Ví dụ
50
50
Insertion Sort – Cài đặt
void InsertionSort(int a[], int N )
{
int pos, i;
int x;
//lưu trữ a[i] tránh bò ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<N ; i++) //đoạn a[0] đã sắp
{
x = a[i];
for(pos=i;(pos>0)&&(a[pos-1]>x);pos--)
a[pos] = a[pos-1];
a[pos] = x;// chèn x vào dãy
}
}
51
51
Insertion Sort – Nhận xét
• Khi tìm vò trí thích hợp để chèn a[i] vào đoạn
a[0] đến a[i-1], do đoạn đã được sắp 

 có thể
sử dụng giải thuật tìm nhò phân để thực hiện
việc tìm vò trí pos 

 giải thuật sắp xếp chèn
nhò phân Binary Insertion Sort
– Lưu ý: Chèn nhò phân chỉ làm giảm số lần so sánh,

không thích hợp 

 dời chỗ phần tử a[pos-1] đến vò trí
pos.
• Giải thuật thực hiện tất cả N-1 vòng lặp tìm pos, do số
lượng phép so sánh và dời chỗ này phụ thuộc vào tình
trạng của dãy số ban đầu, nên chỉ có thể ước lược trong
từng trường hợp như sau:
Phương pháp đổi chỗ trực tiếp
Interchange Sort
55
55
Interchange Sort – Ý tưởng
• Nhận xét: Để sắp xếp một dãy số, ta có
thể xét các nghòch thế có trong dãy và
làm triệt tiêu dần chúng đi.


 Ý tưởng chính:
– Xuất phát từ đầu dãy, tìm tất cả nghòch thế
chứa phần tử này, triệt tiêu chúng bằng
cách đổi chỗ phần tử này với phần tử tương
ứng trong cặp nghòch thế.
– Lặp lại xử lý trên với các phần tử tiếp theo
trong dãy
56
56
Interchange Sort – Thuật toán
//input: dãy (a, N)
//output: dãy (a, N) đã được sắp xếp

59
Interchange Sort – Ví duï
2 12 8 5 6 4 151
2 3 4 5 6 7 81
i
j
4
60
60
Interchange Sort – Ví duï
2 4 12 8 6 5 151
2 3 4 5 6 7 81
i
j
5
61
61
Interchange Sort – Ví dụ
2 4 5 6 8 12 151
2 3 4 5 6 7 81
62
62
Interchange Sort - Cài đặt
void InterchangeSort(int a[], int N)
{
int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =i+1; j < N ; j++)
if(a[j]< a[i]) //nếu có nghòch thế
thì đổi chỗ

• Bước 2 : j = Vò trí cuối;//Duyệt từ cuối dãy ngược
về vò trí i
– Trong khi (j > i) thực hiện:
• Nếu a[j]<a[j-1]: a[j]↔
↔↔
↔a[j-1];//xét cặp phần tử kế cận
• j = Vò trí trước(j);
• Bước 3 : i = Vò trí kế(i); // lần xử lý kế tiếp
– Nếu i = Vò trí cuối: Dừng. // Hết dãy.
– Ngược lại : Lặp lại Bước 2.
67
67
Bubble Sort – Ví duï
2 8 5 1 6 4 1512
2 3 4 5 6 7 81
i
j
1
68
68
Bubble Sort – Ví duï
12 2 8 5 4 6 151
2 3 4 5 6 7 81
i
j
2
69
69
Bubble Sort – Ví duï
2 12 4 8 5 6 151

Bubble Sort Vớ duù
2 4 5 6 8 12 151
2 3 4 5 6 7 81
i
j
15
12
74
74
Bubble sort - Caứi ủaởt
void BubbleSort(int a[], int N)
{
int i, j;
for (i = 0 ; i < N-1 ; i++)
for (j = N-1; j>i ; j --)
if(a[j]< a[j-1])
Swap(a[j], a[j-1]);
}

Trích đoạn Quick sort –Ý tưởng

---