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á tŕ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 tŕ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