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

B́a trước

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

 

Nội dung mọi người đang nói đến - Viết bài đánh giá

Chúng tôi không t́m thấy bài đánh giá nào ở các vị trí thông thường.

Các trang được chọn

Nội dung

Đổi chỗ 2 phần tử trong cặp nghịch thế trong lượt chạy đầu tiên i0j1
1
2 T́m amin trong dăy hiện hành từ chỉ số 1 đến 7 đổi chỗ amin cho a1
7
4 Xuất hiện cặp nghịch thế j2j11 cần phải đổi chỗ trong lần xử lư đầu tiên
11
Thuật toán sắp xếp Shaker Sort
15
Tài liệu tham khảo
22

Thuật ngữ và cụm từ thông dụng

Thông tin thư mục