//
you're reading...
01 - Chủ đề thuật toán

Thuật toán Sắp xếp bằng tráo đổi (Exchange Sort)

1.Xác định bài toán


- Input: Dãy A gồm N số nguyên a¬1, a¬2,..., aN.
- Output: Dãy A được sắp xếp lại thành dãy không giảm.

2.Ý tưởng


Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.


3.Thuật toán


a) Cách liệt kê

B­ước 1. Nhập N, các số hạng a¬1, a¬2,…, aN;
B­ước 2. M := N;
B­ước 3. Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
B­ước 4. M := M – 1, i := 0;
B­ước 5. i := i + 1;
B­ước 6. Nếu i > M thì quay lại bước 3;
B­ước 7. Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
B­ước 8. Quay lại bước 5.

Ta thấy rằng, sau mỗi lần đổi chỗ, giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng vị trí là ở cuối dãy. Tương tự, sau lượt thứ hai, giá trị lớn thứ hai được xếp đúng ở vị trí sát cuối,… Có thể hình dung, sau mỗi lượt có ít nhất một số hạng đã xếp đúng vị trí và không còn tham gia vào quá trình đổi chỗ nữa, giống như các bọt nước từ đáy hồ nổi dần và khi đã lên mặt nước rồi thì tan biến. Có thể vì thế mà sắp xếp bằng tráo đổi còn có tên gọi là sắp xếp nổi bọt (Bubble Sort).


Ghi chú


– Qua nhận xét trên, ta thấy quá trình so sánh và đổi chỗ sau mỗi lượt chỉ thực hiện với dãy đã bỏ bớt số hạng cuối dãy. Để thực hiện điều đó trong thuật toán sử dụng biến nguyên M có giá trị khởi tạo là N, sau mỗi lượt M giảm một đơn vị cho đến khi M < 2.
– Trong thuật toán trên, i là biến chỉ số các số hạng của dãy có giá trị nguyên thay đổi lần lượt từ 0 đến M + 1.


b) Sơ đồ khối

luu do trao doi

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Tám 2015
H B T N S B C
« Th1   Th9 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Geese Resort

Toulouse Sunset

Monolith

More Photos

Thống kê

  • 115,743 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: