Nội dung buổi offline 04, ngày 18/12/2016

Phần 1: Lịch học

Theo biểu quyết của lớp thì chủ nhật tuần sau ngày 25/12/2016 chúng ta vẫn học bình thường. Nếu lịch có thay đổi sẽ thông báo sau.

Phần 2: Bài học

1. Bài tập 1: thuật toán sắp xếp

Nội dung: Tìm hiểu thuật toán sắp xếp, cụ thể là thuật toán sắp xếp chèn (insertion-sort).

Mô tả thuật toán:

  1. Phỏng theo cách làm của người chơi bài, mỗi khi có một quân bài mới người chơi sẽ tìm vị trí thích hợp trong bộ bài đang cầm trên tay để chèn lá bài mới này vào sao cho giá trị quân bài tăng dần đều.
  2. Ta thực hiện đưa lần lượt các phần tử của mảng vào đúng vị trí cần sắp xếp.
  3. Tại bước thứ k=1,2,3,…,n đưa phần tử thứ k trong mảng A đã cho vào đúng vị trí trong dãy gồm k phần tử.
  4. Kết quả sau mỗi bước kk phần tử đầu tiên được sắp xếp đúng thứ tự.
  5. Miêu tả bằng hình ảnh cho dễ hiểu: 

Code:

Bài tập 2: Sắp xếp theo cặp số

Input: Chúng ta có 2 mảng a[n] và b[n] lấy dữ liệu từ file input.txt:

Yêu cầu: Sắp xếp các phần tử mảng a[ ], mở rộng ra mảng b[ ] tương ứng.

  1. Trước khi sắp xếp:
    a 1 6 2 7 0
    b 7 8 4 3 2
  2. Sau khi sắp xếp:
a 0 1 2 6 7
b 2 7 4 8 3


Output: Lưu kết quả ra output.txt

Đây là bài tập về nhà.

Hạn nộp: 24/12/2016.

Gửi bài tập đến địa chỉ: [email protected]

Tiêu đề email: [DSA-W04] Nộp bài tập sắp xếp theo cặp số

The following two tabs change content below.