bangtqh@hotmail.com
K THUT LP TRÌNH C
Chương 7: Các thut toán sp xp
04/2010
Kthut lp trình C - Thut toán sp xp2
bangtqh@hotmail.com
Bài toán sp xp
• Cho tp N phn t, mi phn
tcó mt sthuc tính
• Da vào 1 (hoc vài) thuc tính
ca các phn t ñ sp xp li
chúng theo trt tmi.
04/2010
Kthut lp trình C - Thut toán sp xp3
bangtqh@hotmail.com
Bài toán sp xp
• Gm 2 bài toán con:
– Da theo khoá sp xp đnh vli thtcác
phn t
– Chuyn các phn tcn sp vvtrí mi.
• Hai thao tác cơ bn
– So sánh
– Gán
04/2010
Kthut lp trình C - Thut toán sp xp4
bangtqh@hotmail.com
Các gii thut sp xp
• Sp xp đi chtrc tip - Interchange Sort
• Sp xp chn trc tip – Selection Sort
• Sp xp chèn trc tip – Insertion Sort
• Sp xp ni bt – Buble Sort
• Sp xp ni bt ci tin - Shaker Sort
• Shell sort
• Heap sort
• Quick sort
• Merge sort
04/2010
Kthut lp trình C - Thut toán sp xp5
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
•Khái nim nghch th:
–Xét mt mng các sa
0
, a
1
, . a
n
.
–Nu có i<j và a
i
> a
j
, thì ta gi đó là mt nghch
th.
• Mng chưa sp xp scó nghch th
• Mng đã có thtskhông cha nghch th
04/2010
Kthut lp trình C - Thut toán sp xp6
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
• Tìm tt cnghch th, trit tiêu chúng bng
cách hoán v2 phn t tương ng trong
nghch th
04/2010
Kthut lp trình C - Thut toán sp xp7
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
• Bưc 1 : i = 1;
// bt đu t" ñu dãy
• Bưc 2 : j = i+1;
//tìm các phn ta[j] < a[i], j>i
• Bưc 3 :
Trong khi j < N thc hin
Nu a[j]<a[i]
//xét cp a[i], a[j]
Doicho(a[i],a[j]);
j = j+1;
• Bưc 4 : i = i+1;
Nu i < n: Lp li Bưc 2.
Ngư#c li: D"ng.
04/2010
Kthut lp trình C - Thut toán sp xp8
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
• Cho dãy sa:
12 2 8 5 1 6 4 15
04/2010
Kthut lp trình C - Thut toán sp xp9
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
04/2010
Kthut lp trình C - Thut toán sp xp10
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
04/2010
Kthut lp trình C - Thut toán sp xp11
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
04/2010
Kthut lp trình C - Thut toán sp xp12
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
04/2010
Kthut lp trình C - Thut toán sp xp13
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
04/2010
Kthut lp trình C - Thut toán sp xp14
bangtqh@hotmail.com
Interchange Sort - Kt qu
12 2 8 5 1 6 4 15
2 12 8 5 1 6 4 15
1 12 8 5 2 6 4 15
1 8 12 5 2 6 4 15
1 5 12 8 2 6 4 15
1 2 12 8 5 6 4 15
1 2 8 12 5 6 4 15
1 2 5 12 8 6 4 15
1 2 4 12 8 6 5 15
1 2 4 8 12 6 5 15
1 2 4 6 12 8 5 15
1 2 4 5 12 8 6 15
1 2 4 5 8 12 6 15
1 2 4 5 6 12 8 15
1 2 4 5 6 8 12 15
04/2010
Kthut lp trình C - Thut toán sp xp15
bangtqh@hotmail.com
Đi chtrc tip – Interchange Sort
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])
// nu có ssai vtrí thì ñi ch
Doicho(a[i],a[j]);
}
04/2010
Kthut lp trình C - Thut toán sp xp16
bangtqh@hotmail.com
Các gii thut sp xp
• Sp xp đi chtrc tip - Interchange Sort
• Sp xp chn trc tip – Selection Sort
• Sp xp chèn trc tip – Insertion Sort
• Sp xp ni bt – Buble Sort
• Sp xp ni bt ci tin - Shaker Sort
• Shell sort
• Heap sort
• Quick sort
• Merge sort
04/2010
Kthut lp trình C - Thut toán sp xp17
bangtqh@hotmail.com
Chn trc tip – Selection Sort
• Chn phn tnh$nht trong N phn t ban ñu
•Đưa phn tnày vvtrí ñúng là ñu dãy hin hành
• Xem dãy hin hành ch'còn N-1 phn tca dãy
ban đu
– Bt đu t"vtrí th2;
– Lp li quá trình trên cho dãy hin hành... ñn khi dãy
hin hành ch'còn 1 phn t
04/2010
Kthut lp trình C - Thut toán sp xp18
bangtqh@hotmail.com
Chn trc tip – Selection Sort
•Bưc 1: i = 1;
•Bưc 2: Tìm phn ta[min] nhnht trong dãy hin
hành t a[i] ñn a[N]
•Bưc 3 : Nu min ≠ i thì ði cha[min] và a[i]
•Bưc 4 : Nu i < N-1 thì
i = i+1; Lp li Bưc 2
Ngưc li: Dng.
04/2010
Kthut lp trình C - Thut toán sp xp19
bangtqh@hotmail.com
Chn trc tip – Selection Sort
• Cho dãy sa:
122 8 5 1 6 4 15
04/2010
Kthut lp trình C - Thut toán sp xp20
bangtqh@hotmail.com
Chn trc tip – Selection Sort