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

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ả
Nội dung trích xuất từ tài liệu:
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=722 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 123 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ánh26 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=128 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=229 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=330 This is trial version Khoa CNTT Trư ng C ...