Các thuật toán sắp xếp cơ bản

Trong công nghệ thông tin cũng như trong đời sống xã hội, bài toán sắp xếp thường xuyên được diễn ra. Đối với công nghệ thông tin, để cho đơn giản chúng ta có thể phát biểu bài toán như sau:

Cho danh sách có n phần tử a0, a1, a2…, an-1.

Sắp xếp là quá trình xử lý các phần tử trong danh sách để đặt chúng theo một thứ tự thỏa mãn một số tiêu chuẩn nào đó dựa trên thông tin lưu tại mỗi phần tử, như:

·       Sắp xếp danh sách lớp học tăng theo điểm trung bình.

·       Sắp xếp danh sách sinh viên tăng theo tên.

Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách trên trong bộ nhớ chính.

Trong đó:

a: là dãy các phần tử dữ liệu

Để sắp xếp dãy a theo thứ tự (không làm mất tính tổng quát, ta sắp xếp giá trị của dãy theo thứ tự tăng), ta tiến hành triệt tiêu tất cả các nghịch thế trong a.

Nghịch thế được định nghĩa như sau:

·       Cho dãy có n phần tử a0, a1,…,an-1

·       Nếu i<j và ai >aj