Sắp xếp là một công việc rất quan trọng trong việc quản lý dữ liệu vì nó giúp chúng ta tìm kiếm thông tin một cách nhanh chóng. Tuy nhiên với lập trình Web thì chúng ta lại ít đụng đến các thuật toán sắp xếp, và PHP cũng đã có cung cấp một số hàm sắp xếp sẵn rất tiện lợ. Nhưng chúng ta đang học lập trình nên bạn cũng không nên bỏ qua các kiến thức về thuật toán này.
Trong bài này chúng ta sẽ nghiên cứu một thuật toán sắp xếp đơn giản nhất đó là thuật toán sắp xếp nổi bọt(bubble sort). Ý tưởng của thuật toán bắt nguồn từ việc so sánh 2 phần tử cạnh nhau và hoán vị chúng nếu không đúng vị trí. Ta có thể tiến hành từ trái qua phải hoặc từ phải qua trái tùy vào nhu cầu của mình.
1. Sắp xếp nổi bọt tăng dần
Thuật toán sắp xếp nổi bọt tăng dần được xử lý như sau:
Cho vòng lặp $i chạy từ 1 tới ($n-1):
Lần lặp 1: $i = 1, lần lược so sánh với các vị trí khác bắt đầu từ ($i + 1) tức là vị trí 2, nếu phần tử thứ 1 lớn hơn các phần tử đứng sau bắt đầu từ 2 thì hoán vị chúng.
Lần lặp 2: $i = 2, lần lược so sánh với các vị trí khác bắt đầu từ ($i + 1) tức là vị trí 3, nếu phần tử thứ 2 lớn hơn các phần tử đứng sau nó bắt đầu từ 3 thì hoán vụ chúng.
Cứ như vậy cho đến khi ta lặp lần thứ ($n – 1), lúc này biến $i = ($n-1), ta so sánh với phần tử cuối cùng ($n) và hoán vị nếu không thỏa mãn.
Vậy là chúng ta đã được học qua 2 thuật toán sắp xếp chọn và sắp xếp nổi bọt. Vẫn còn một thuật toán sắp xếp nũa chúng ta sẽ được học trong bài hôm nay đó là là thuật toán sắp xếp chèn.
Nôi dung bao gồm:
- Ý tưởng thuật toán
- Cài đặt thuật toán
2. Ý tưởng thuật toán sắp xếp chèn
Ý tưởng thuật toán sắp xếp chèn như sau:
Trước hết ta xem phần tử a[0] là một dãy đã có thứ tự.
Bước 1: Chèn phần tử a[1] vào dãy a[0] theo đúng vị trí sao cho dãy a[0] và a[1] được sắp xếp đúng thứ tự.
Bước 2: Chèn phần tử a[2] vào dãy a[0], a[1] sao cho dãy a[0], a[1], a[2] được sắp xếp đúng thứ tự.
Bước i: Chèn phần tử a[i] vào dãy a[o], a[1], a[2], …, a[i-1] sao cho dãy a[o], a[1], a[2], …, a[i-1], a[i] được sắp xếp đúng thứ tự
Sau N-1 bước thì kết thúc (vì mảng có N-1 phần tử).
3. Ý tưởng thuật toán sắp xếp chọn
Với thuật toán nổi bọt thì ý tưởng là với mỗi phần tử sẽ lặp hết các phần tử phía sau, nếu phần tử nào không đứng đúng vị trí thì hoán vị ngay lập tức. Với thuật toán sắp xếp chọn trong php thì lại khác, ý tưởng như sau: Duyệt từ vị trí thứ 1 đến vị trí cuối cùng, tìm vị trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 1, sau đó loại vị trí số 1 ra khỏi danh sách sắp xếp vì nó đã được đặt đúng vị trí. Tiếp tục thao tác như vậy cho các vị trí tiếp theo.
Sắp xếp chọn tăng dần:
Bước 1: Duyệt từ vị trí thứ 1 đến vị trí cuối cùng, tìm vị trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 1, sau đó loại vị trí số 1 ra khỏi danh sách sắp xếp vì nó đã được đặt đúng vị trí.
Bước 2: Duyệt từ vị trí số 2 đến vị trí cuối cùng, tìm ví trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 2, sau đó loại vị trí số 2 ra khỏi danh sách sắp xếp vì đã đặt đúng vị trí.
Bước n: Cứ như vậy cho đến vị trí phần tử cuối cùng, lúc này chỉ còn 1 phần tử nên coi như nó đã sắp xếp.
