Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán sắp xếp - Nguyễn Mạnh Hiển (P1)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Các thuật toán sắp xếp (P1)" có cấu trúc gồm 3 phần cung cấp cho người học các kiến thức: Sắp xếp chọn (selection sort), sắp xếp nổi bọt (bubble sort), sắp xếp chèn (insertion sort). Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán sắp xếp - Nguyễn Mạnh Hiển (P1)Các thuật toán sắp xếp (p1)(sorting algorithms)Nguyễn Mạnh HiểnKhoa Công nghệ thông tinhiennm@tlu.edu.vnCác thuật toán sắp xếp - phần 1• Sắp xếp chọn (selection sort)• Sắp xếp nổi bọt (bubble sort)• Sắp xếp chèn (insertion sort)Sắp xếp chọn (selection sort)• Cho dãy A gồm N phần tử a0, a1, …, aN-1• Mỗi bước xét một danh sách con chưa sắp xếp (unsorted sublist - USL)• Có N-1 bước: − Bước 1: USL = {a0, a1, …, aN-1} − Bước 2: USL = {a1, …, aN-1} −… − Bước N-1: USL = {aN-2, aN-1}Sắp xếp chọn (tiếp)• Mỗi bước: − Tìm phần tử nhỏ nhất (amin) trong USL − Đổi chỗ amin và phần tử đầu tiên của USL − Dịch chuyển biên của USL sang phải một phần tửSắp xếp chọn: Ví dụ• Ban đầu: 64, 25, 12, 22, 11• Sau bước 1: 11, 25, 12, 22, 64• Sau bước 2: 11, 12, 25, 22, 64• Sau bước 3: 11, 12, 22, 25, 64• Sau bước 4: 11, 12, 22, 25, 64 (danh sách con chưa sắp xếp được gạch chân)Cài đặt và phân tích sắp xếp chọn• Viết hàm selectionSort()• Chứng minh thời gian chạy là O(N2)Sắp xếp nổi bọt (bubble sort)• Mỗi bước: − So sánh hai phần tử kề nhau − Đổi chỗ nếu chúng chưa đúng thứ tự• Sau mỗi bước, phần tử lớn nhất sẽ được đặt (“nổi bọt”) xuống cuối dãy• Thời gian chạy: O(N2)Sắp xếp nổi bọt: Ví dụ• Ban đầu: 2, 3, 1, 15• Sau bước 1: 2, 1, 3, 15• Sau bước 2: 1, 2, 3, 15• Sau bước 3: 1, 2, 3, 15 (danh sách con chưa sắp xếp được gạch chân)Sắp xếp nổi bọt: Cài đặtfor (i = 0; i < N-1; i++){ for (j = 0; j < N-1-i; j++) if (a[j+1] < a[j]) { tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; }}• Trong trường hợp tốt nhất (dãy đã sắp xếp rồi), sắp xếp nổi bọt chỉ nên mất thời gian O(N)  hãy tối ưu hóa cài đặt bên trên!Sắp xếp chèn (insertion sort)• Có N-1 bước ứng với p = 1, 2, …, N-1• Ở bước p: (khi bắt đầu bước p, các vị trí 0, …, p-1 đã được sắp xếp rồi) − Xác định vị trí phù hợp trong các vị trí 0, …, p-1 cho phần tử ở vị trí p (ap) − Chèn ap vào vị trí đã xác định, vì vậy các vị trí từ 0 đến p được sắp xếpSắp xếp chèn: Ví dụSắp xếp chèn: Cài đặtPhân tích sắp xếp chèn• Trường hợp tốt nhất: O(N)• Trường hợp tồi nhất: O(N2)