Các thuật toán sắp xếp (p1) (sorting algorithms)

Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn

Cá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)

USL = {a0, a1, …, aN-1} USL = {a1, …, aN-1}

• Có N-1 bước: − Bước 1: − Bước 2: − … − 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: • Sau bước 1: • Sau bước 2: • Sau bước 3: • Sau bước 4: 64, 25, 12, 22, 11 11, 25, 12, 22, 64 11, 12, 25, 22, 64 11, 12, 22, 25, 64 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: • Sau bước 1: • Sau bước 2: • Sau bước 3: 2, 3, 1, 15 2, 1, 3, 15 1, 2, 3, 15 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 đặt

for (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ếp

Sắp xếp chèn: Ví dụ

Sắp xếp chèn: Cài đặt

Phâ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)