tailieunhanh - Bài giảng Phân tích thiết kế giải thuật và cấu trúc dữ liệu: Phần 2 - ĐH CNTT&TT

Phần 2 của bài giảng Phân tích thiết kế giải thuật và cấu trúc dữ liệu đi sâu tìm hiểu các cách tổ chức dữ liệu và thuật toán trên kiểu dữ liệu đó. Với mục đích cung cấp cho các bạn sinh viên một cái nhìn toàn thể và cơ bản. Tác giả kỳ vọng kết thúc môn học người học sẽ nắm được những cách tổ chức và cấu trúc dữ liệu. Từ đó áp dụng một phần kiến thức ấy vào nghiên cứu những mảng khác hiệu quả, tối ưu hơn. | Chương 4 CÁC THUẬT TOÁN SẮP XẾP . Các thuật toán sắp xếp cơ bản . Sắp xếp chọn Selection Sort Giải thuật Đây là phương pháp sắp xếp đơn giản nhất được tiến hành như sau Đầu tiên chọn phần tử có khóa nhỏ nhất trong n phần tử từ a 1 đến a n và hoán vị nó với phần tử a 1 . Chọn phần tử có khóa nhỏ nhất trong n-1phần tử từ a 2 đến a n và hoán vị nó với a 2 . Tổng quát ở bước thứ i chọn phần tử có khoá nhỏ nhất trong n-i 1 phần tử từ a i đến a n và hoán vị nó với a i . Sau n-1 bước này thì mảng đã được sắp xếp. Phương pháp này được gọi là phương pháp chọn bởi vì nó lặp lại quá trình chọn phần tử nhỏ nhất trong số các phần tử chưa được sắp. Ví dụ 2-1 Sắp xếp mảng gồm 10 mẩu tin có khóa là các số nguyên 5 6 2 2 10 12 9 10 9 và 3 Bước 1 Ta chọn được phần tử có khoá nhỏ nhất bằng 2 trong các phần tử từ a 1 đến a 10 là a 3 hoán đổi a 1 và a 3 cho nhau. Sau bước này thì a 1 có khoá nhỏ nhất là 2. Bước 2 Ta chọn được phần tử có khoá nhỏ nhất bằng 2 trong các phần tử từ a 2 đến a 10 là a 4 hoán đổi a 2 và a 4 cho nhau. Tiếp tục quá trình này và sau 9 bước thì kết thúc. 57 Bảng sau ghi lại các giá trị khoá tương ứng với từng bước. Kh0a B1IỠC l 42 43J 44 45 4 5 47 4M 49 410 Ban dan 5 6 2 2 LO 12 9 10 9 3 B1IŨC J 2 6 5 2 10 12 9 lữ 9 3 Biufcl 2 5 6 LO 12 9 lũ 9 3 Bum 3 3 6 LO 12 9 lũ 9 5 BwcJ 5 10 12 9 10 9 0 Birâc 5 6 12 9 10 9 10 Bum 6 9 12 10 9 10 Bum 7 9 10 12 10 BirôcS 10 12 10 BiiúcS 10 12 KỄt quà 2 2 3 5 Ế 9 9 10 10 12 Bảng Các bước thực hiện sắp xếp chọn Chương trình PROCEDURE SelectionSort VAR i j LowIndex integer LowKey KeyType BEGIN 1 FOR i 1 TO n-1 DO BEGIN 2 LowIndex i 3 LowKey a i .key 4 FOR j i 1 TO n DO 5 IF a j .key LowKey THEN BEGIN 6 LowKey a j .key 7 LowIndex j END 8 Swap a i a LowIndex END 58 END Đánh giá Phương pháp sắp xếp chọn lấy O n để sắp xếp n phần tử. Trước hết ta có thủ tục Swap lấy một hằng thời gian như đã nói ở mục . Các lệnh 2 3 đều lấy O 1 thời gian. Vòng lặp for 4 - 7 thực hiện n-i lần vì j chạy từ i 1 đến n mỗi lần lấy O 1 nên