BÀI GIẢNG CÔNG NGHỆ THÔNG TIN:Interchange Sort

Chia sẻ: Trần Ngọc Mai | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

133
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'bài giảng công nghệ thông tin:interchange sort', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: BÀI GIẢNG CÔNG NGHỆ THÔNG TIN:Interchange Sort

2.2.2. Gi i Thu t ð i Ch Tr c Ti p-Interchange Sort Ý tư ng: 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. 21 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
Minh H a 2 8 5 1 6 4 12 2 8 5 1 6 4 12 i=1 j=2 i=2 j=3 i=3 j=4 i=4 j=5 i=5 j=6 i=6 j=7 i=7 22 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
12 2 8 5 1 6 4 Ban ñ u 1 12 8 5 2 6 4 L n1 1 2 12 8 5 6 4 L n2 L n3 2 4 12 8 6 5 1 2 4 5 12 8 6 1 L n4 2 4 5 6 12 8 1 L n5 2 4 5 6 8 12 L n6 1 23 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
Gi i thu t: Bư c 1 : i = 1; // b t ñ u t ñ u dãy Bư c 2 : j = i+1;//tìm các ph n t a[j] < a[i], j>i Bư c 3 : Trong khi j < N th c hi n N u a[j]
Cài ð t void InterchangeSort(int a[], int N ) { int i, j,tam; for (i = 0 ; i
ðánh giá gi i thu t: Ð i v i gi i thu t ñ i ch tr c ti p, s lư ng các phép so sánh x y ra không ph thu c vào tình tr ng c a dãy s ban ñ u Nhưng s lư ng phép hoán v th c hi n tùy thu c vào k t q a so sánh 26 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
2.2.3 Gi i Thu t Ch n Tr c Ti p –Selection Sort Ý Tư ng: ð u tiên dãy có N ph n t , ta ch n ph n t nh nh t trong dãy ñ i ch cho ph n t ñ u tiên. Ti p theo, tìm ph n t nh nh t c a dãy n-1 ph n t còn l i trong dãy ñ i ch cho ph n t th 2 c a dãy. Quá trình trên th c hiên ñ n khi nào trong m ng ch còn 1 ph n t thi d ng l i. K t qu ñư c m ng ñã s p x p tăng. 27 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
Minh H a Cho dãy có 8 ph n t S p x p theo vi trí tăng d n 16 11 45 28 73 61 7 23 Min 16 11 45 28 73 61 7 23 I=1 28 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
Minh H a Cho dãy có 8 ph n t S p x p theo vi trí tăng d n 16 11 45 28 73 61 7 23 Min 7 11 45 28 73 61 16 23 I=2 29 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
Minh H a Cho dãy có 8 ph n t S p x p theo vi trí tăng d n 16 11 45 28 73 61 7 23 Min 7 11 45 28 73 61 16 23 I=3 30 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com