tailieunhanh - Giáo trình phân tích khả năng vận dụng quy trình sử dụng cấu trúc dữ liệu và giải thuật p7

Tham khảo tài liệu 'giáo trình phân tích khả năng vận dụng quy trình sử dụng cấu trúc dữ liệu và giải thuật p7', 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ả | M 1 2 5 15 20 25 30 33 45 60 Sau lần 9 K 9 và mảng M trở thành M 1 2 5 15 20 25 30 33 45 60 - Phân tích thuật toán Trong mọi trưởng hởp Số phép so sành S N-1 N-2 . 1 Nx N-1 2 So phép hoàn vị H N-1 Trưởng hởp tot nhầt khi man M ban đàu đà co thứ tù tàng So phép gàn Gmin 2x N-1 Trưởng hởp xấu nhất khi màng M bàn đàu đà co thứ tự giàm dàn So phép gàn Gmàx 2x N N-1 . 1 Nx N 1 Trung bình So phép gàn Gàvg 2x N-1 Nx N 1 2 N-1 Nx N 1 2 . Sắp xếp bang phương pháp chèn Insertion Sort Càc thuàt toàn trong phàn này sé tìm càch tàn dụng K phàn tử đàu dày M đà co thứ tự tàng chúng ta đém phàn tù thứ K 1 chén vào K phàn tử đàu dày sào cho sàu khi chén chúng tà co K 1 phàn tử đàu dày M đà co thứ tự tàng. Bàn đàu dày M co ít nhất 1 phàn tứ đàu dày đà co thứ tự tàng K 1 . Như vậy sàu toi đà N-1 bưởc chén là chung ta sé sàp xép xong dày M co N phàn tử théo thứ tư tàng. Càc thuàt toàn sàp xép bàng phưởng phàp chén bào gồm - Thuàt toàn sàp xép chén trực tiếp stràight insértion sort - Thuàt toàn sàp xép chén nhị phàn binàry insértion sort . Trong tài liéu này chung ta chỉ trình bày thuàt toàn sàp xép chén trực tiép. Thuật toán sắp xếp chen trực tiếp Straight Insertion Sort - Tư tưởng Đé chén phàn tử thứ K 1 vào K phàn tử đàu dày đà co thứ tự chung ta sé tién hành tìm vị trí đung cuà phàn tử K 1 trong K phàn tử đàu bàng càch vàn dung thuàt giài tìm kiém tuàn tự Séquéntiàl Séàrch . Sàu khi tìm đưởc vị trí chén chàc chàn co vị trí chén thì chung tà sé tién hành chén phàn tư K 1 vào đung vị trí chén bàng càch dởi càc phàn tư từ vị trí chén đén phàn tử thứ K sàng phài rà phíà sàu 01 vị trí và chén phàn tử K 1 vào vị trí cuà no. - Thuật toán B1 K 1 B2 IF K N Trang 33 B3 X M K 1 B4 Pos 1 B5 IF Pos K Thực hiện B7 B6 ELSE Tìm vị trí chèn If X M Pos Thực hiện B7 Pos Lặp lại B7 I K 1 B8 IF I Pos Nèu con phai dổi cạc phan tử từ Pos- K vệ phíặ sau 1 vị trí M I M I-1 I-- Lặp lại B8 B9 ELSE Đa dổi xong cac phan từ từ Pos- K vệ phía sau 1 vị trí M Pos X Chèn