Thuật toán sắp xếp các phần tử trong mảng

Trong khoa học máy tính và trong toán học, thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hoặc một mảng) theo thứ tự (tăng hoặc giảm). Người ta thường xét trường hợp các phần tử cần sắp xếp là các số.

Bài toán sắp xếp đã được nhiều nhà khoa học quan tâm. Sau đây mình xin trình bày với các bạn một số thuật toán sắp xếp tổng hợp từ trên internet.

1. Sắp xếp nổi bọt:

Sắp xếp nổi bọt (tiếng Anh: bubble sort) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap). Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang). Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.

Giả sử ta có mãng A[1..n] với số lượng phần tử là n, các bước thực hiện sắp xếp tăng dần như sau:

- Bước 1: i = n

- Bước 2: xét từ đầu mãng đến i, với mỗi 2 phần tử kề nhau, nếu số đứng sau nhỏ hơn số đứng trước thì hoán vị.

Tức là:

o A[1] với A[2]

o A[2] với A[3]

o …

o A[i-1] với A[i]

Sau khi thực hiện bước này, phần tử lớn nhất sẽ bị đẩy từ từ ra cuối mãng, chính vì vậy thuật toán này có tên là “nổi bọt”

- Bước 3: i = i – 1

- Bước 4: Nếu i > 1 thì quay lại bước 2 (đến khi mãng còn lại 1 phần tử thì không cần phải sắp xếp nữa)

Và như vậy, qua mỗi lần thực hiện bước 2 thì có một phần tử được đẩy lùi về cuối mãng, đó là phần tử lớn nhất, lớn nhì, lớn kế, … và nó giảm dần sau mỗi lần lặp. Chính vì vậy sau khi hoàn tất vòng lặp thì các phần tử đã theo thứ tự tăng dần. Hình ảnh minh họa cho thuật toán: 

---

---

2. Sắp xếp chọn:

Đây là thuật toán tự nhiên nhất, rất dễ hiểu và dễ thực hiện. Tư tưởng của thuật toán như sau:

Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử còn lại, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

Các bước thực hiện:

- Bước 1: i = 1

- Bước 2: Tìm phần tử nhỏ nhất A[min] trong dãy hiện hành từ A[i] đến A[n]

- Bước 3: Hoán vị A[min] và A[i]

- Bước 4: i = i + 1

- Bước 5: Nếu i < n thì quay lại bước 2 (i = n tức là mãng chỉ còn 1 phần tử)

---

3. Sắp xếp chèn:

Tư tưởng của thuật toán sắp xếp chèn rất đơn giản như sau: 

Giả sử ta có trước một dãy số đã theo thứ tự tăng dần, sau đó ta muốn chèn thêm một phần tử vào dãy thì việc cần làm là tìm một vị trí thích hợp cho phần tử đó để dãy vẫn giữ đúng thứ tự ban đầu.

Do dãy số đang tăng dần, nên để tìm được vị trí đó ta chỉ cần duyệt qua các phần tử trong dãy từ cuối đến đầu, nếu gặp một phần tử A[i] nào nhỏ hơn hoặc bằng phần tử x cần chèn thì chèn x vào ngay sau A[i], thì dãy số A vẫn giữ đúng thứ tự tăng dần.

Vậy với dãy số đầu vào A[1..n] không theo thứ tự, ta có thể xem A[1] là một dãy có thứ tự (do chỉ có 1 phần tử), kế tiếp ta tìm vị trí để chèn A[2] vào, sau đó ta đã được dãy A[1..2] có thứ tự. Lặp lại các bước tương tự cho đến khi A[1..n] có thứ tự

Các bước thực hiện:

- Bước 1: i = 2 (xem A[1] là dãy số có thứ tự vì nó chỉ có 1 phần tử)

- Bước 2: temp = A[i] (phải lưu A[i] ra biến tạm vì trong lúc hoán đổi vị trí sẽ làm mất giá trị của A[i])

- Bước 3: j = i – 1

- Bước 4: Xét từ j về 1, tìm vị trí thích hợp để chèn temp vào mãng A

o Nếu A[j] > temp thì A[j+i] = A[j]

Nếu j > 1 thì j = j – 1; Lặp lại bước 4

Ngược lại, A[j] = temp;

o Ngược lại: A[j+1] = temp;

- Bước 5: Nếu i < n thì i = i + 1; Quay lại bước 2;

Ngược lại thì ta đã có mảng A[1..n] theo thứ tự tăng dần.