BÀI 21. CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN

1. THUẬT TOÁN SẮP XẾP CHÈN

- Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy. Sau mỗi bước lặp phần tử tương ứng sẽ được chèn vào vị trí đúng của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt.

- Thuật toán sắp xếp chèn có thể mô tả bằng hàm InsertSort(A) như sau:

1 deft InsertionSort(A):

2 n = len(A)

3 for i in range(1,n):

4 value = A[i]

5 j = i – 1

6 while j >= 0 and A[j] > value:

7 A[j+1] = A[j]

8 j = j – 1

9 A[j+1] = value

2. THUẬT TOÁN SẮP XẾP

- Thuật toán sắp xếp chọn thực hiện một vòng lặp với chỉ số i chạy từ 0 (phần tử đầu tiên) đến n – 2 (phần tử gần cuối). Tại mỗi bước lặp, chọn phần tử nhỏ nhất nằm trong dãy A[i], A[i+1],…,A[n – 1] và đổi chỗ phần tử này với A[i].

- Thuật toán sắp xếp chọn có thể được mô tả bằng hầm SelectionSort(A) như sau:

1 def SelectionSort(A):

2 n = len(A)

3 for i in range(n-1):

4 iMin = i

5 for j in range(i+1,n):

6 if A[j] < A[iMin]:

7 iMin = j

8 A[i],A[iMin] = A[iMin],A[i]

3. THUẬT TOÁN SẮP XẾP NỔI BỌT

- Thuật toán sắp xếp nổi bọt thực hiện nhiều vòng lặp, kiểm tra hai phần tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ. Có nhiều cách thể hiện thuật toán này, nhưng cách thường sử dụng hai vòng lặp lồng nhau, vòng lặp trong thực hiện thao tác đổi chỗ hai phần tử cạnh nhau cho đến khi dãy được sắp xếp xong.

- Thuật toán sắp xếp nổi bọt được mô tả bằng hàm BubbleSort(A) như sau:

1 def BubbleSort(A):

2 n = len(A)

3 for i in range(n-1):

4 for j in range(n-1-i):

5 if A[j] > A[j+1]:

6 A[j],A[j+1]=A[j+1],A[j]