CácCác
thuậtthuật
toántoán
thôngthông
dụngdụng
GV. GV. NguyễnNguyễn Minh Minh HuyHuy
CácCác
thuậtthuật
toántoán
thôngthông
dụngdụng
1Kỹ thuật lập trình - Nguyễn Minh Huy
NộiNội dungdung
ThuậtThuật toántoán sắpsắp xếpxếp..
ThuậtThuật toántoán quyquy hoạchhoạch độngđộng..
2Kỹ thuật lập trình - Nguyễn Minh Huy
NộiNội dungdung
ThuậtThuật toántoán sắpsắp xếpxếp..
ThuậtThuật toántoán quyquy hoạchhoạch độngđộng..
3Kỹ thuật lập trình - Nguyễn Minh Huy
ThuậtThuật toántoán sắpsắp xếpxếp
KháiKhái niệmniệm sắpsắp xếpxếp::
BàiBài toántoán::
Cho Cho mảngmảng N N phầnphần tửtử..
BốBố trítrí cáccác phầnphần tửtử theotheo thứthứ tựtự..
N! N! cáchcách bốbố trítrí!!
CácCác
thuậtthuật
toántoán
::
CácCác
thuậtthuật
toántoán
::
4Kỹ thuật lập trình - Nguyễn Minh Huy
Thuật toán Độ phức tạp Không gian
bộ nhớ
Tốt Xấu Trung bình
Interchange Sort N2N2N21
Selection Sort N2N2N21
Merge Sort N logN N logN N logN N
Quick Sort N logN N2N logN logN
ThuậtThuật toántoán sắpsắp xếpxếp
SắpSắp xếpxếp đổiđổi chỗchỗ (Interchange Sort):(Interchange Sort):
Ý Ý tưởngtưởng::
MảngMảng cócó thứthứ tựtự khôngkhông cócó nghịchnghịch thếthế!!
DuyệtDuyệt tấttất cảcả cặpcặp phầnphần tửtử..
ĐổiĐổi chỗchỗ nếunếu phátphát hiệnhiện nghịchnghịch thếthế..
CàiCài
đặtđặt
::
CàiCài
đặtđặt
::
interchange_sortinterchange_sort( ( mảngmảng A, A, kíchkích thướcthước N )N )
{{
for ( for ( intint ii = 0; = 0; ii < N < N –– 1; 1; ii++ )++ )
for ( for ( intint j = j = ii + 1; j < N; j++ )+ 1; j < N; j++ )
if ( if ( a[ j ] < a[ a[ j ] < a[ ii ]] ) ) // // PhátPhát hiệnhiện nghịchnghịch thếthế..
swapswap( a[ ( a[ ii ], a[ j ] );], a[ j ] );
}}
5Kỹ thuật lập trình - Nguyễn Minh Huy
