Sắp xếp mảng danh sách, thuật toán Nổi bọt
Mục tiêu: Máy tạo 6 số ngẫu nhiên trong một danh sách rồi sắp xếp từ nhỏ đến lớn bằng thuật toán nổi bọt.
Em sẽ học gì
- Nội dung trong bài: thuật toán sắp xếp nổi bọt.
- Hoán đổi hai phần tử của danh sách qua một biến tạm.
- Và hai vòng lặp lồng nhau.
Bài làm như sau. Đặt mèo sang bên phải để chừa chỗ cho danh sách: x bằng 120, y bằng âm 40. Chọn nhóm Biến số, bấm Tạo một Danh sách, đặt tên là ds. Bấm Tạo một biến, đặt tên là j: vị trí của cặp đang so sánh. Tạo biến tam: chỗ để tạm một số khi đổi chỗ.
Thuật toán. 1. Tạo 6 số ngẫu nhiên trong danh sách. 2. Nổi bọt: lặp (n − 1) lượt; mỗi lượt: j = 1, lặp (n − 1) lần: nếu phần tử thứ j lớn hơn phần tử thứ j + 1 thì đổi chỗ hai phần tử; j tăng 1.
Sơ đồ khối ở khung bên phải. Đầu tiên, tạo 6 số ngẫu nhiên trong danh sách ds. Vòng lặp ngoài chạy n trừ 1 lượt. Mỗi lượt, j bắt đầu từ 1. Vòng lặp trong: phần tử thứ j lớn hơn phần tử thứ j cộng 1 thì đổi chỗ qua biến tam, rồi j tăng 1. Hết các lượt thì nói: Đã sắp xếp xong!
Chọn nhóm Sự kiện, kéo khối: Khi bấm vào cờ xanh,
Chọn nhóm Biến số, gắn khối xoá hết tất cả trong ds,
khối lặp lại, trong nhóm Điều khiển, đổi thành 6 lần,
bên trong, khối thêm phần tử vào trong ds, trong nhóm Biến số,
thả khối lấy ngẫu nhiên, trong nhóm Các phép toán, vào ô phần tử, đổi số thứ hai thành 99.
Chạy thử: bấm cờ xanh, danh sách có 6 số ngẫu nhiên, chưa theo thứ tự nào. Bấm lần nữa sẽ ra 6 số khác.
Phần hai, sắp xếp nổi bọt. Mỗi lượt, ta đi từ đầu danh sách, so sánh từng cặp đứng cạnh nhau: nếu số trước lớn hơn số sau thì đổi chỗ. Hết một lượt, số lớn nhất nổi về cuối. Lặp lại n trừ 1 lượt thì cả danh sách được sắp xếp.
Vòng lặp ngoài, đếm số lượt: chọn nhóm Điều khiển, gắn khối lặp lại xuống dưới cùng.
Số lượt là số phần tử trừ 1. Lấy khối phép trừ, trong nhóm Các phép toán, đặt ra chỗ trống, ô bên phải gõ 1,
ô bên trái thả khối kích thước của ds, trong nhóm Biến số, rồi kéo vào ô số lần lặp.
Bên trong: mỗi lượt bắt đầu lại từ đầu danh sách. Khối đặt biến thành, chọn j, gõ 1.
Vòng lặp trong, đi qua từng cặp: thêm một khối lặp lại, gắn dưới khối đặt j.
6 phần tử thì có 5 cặp liền kề, nên số lần lặp cũng là kích thước trừ 1: khối phép trừ, gõ 1,
thả khối kích thước của ds, kéo vào ô số lần lặp của vòng lặp trong.
Trong vòng lặp trong, khối điều kiện nếu,
Điều kiện là: phần tử thứ j lớn hơn phần tử thứ j cộng 1, tức là cặp này đang đứng sai thứ tự.
Dựng phần tử đứng sau trước. Lấy khối phép cộng, trong nhóm Các phép toán, đặt ra chỗ trống, ô bên phải gõ 1,
ô bên trái thả biến j, trong nhóm Biến số,
lấy khối phần tử thứ của ds, trong nhóm Biến số, đặt bên dưới, kéo khối j cộng 1 vào ô số thứ tự: phần tử thứ j cộng 1.
Lấy khối so sánh lớn hơn, trong nhóm Các phép toán, kéo phần tử thứ j cộng 1 vào bên phải.
Lấy thêm một khối phần tử thứ của ds,
thả biến j vào ô số thứ tự, kéo vào bên trái của phép so sánh, rồi kéo cả điều kiện vào khối nếu.
Giờ là phần đổi chỗ, gồm ba bước. Bước một: cất phần tử thứ j vào biến tam.
Trong khối nếu, khối đặt biến thành, chọn tam,
lấy khối phần tử thứ của ds,
thả biến j, kéo vào ô giá trị.
Bước hai: ghi phần tử đứng sau vào vị trí j. Lấy khối thay thế phần tử thứ của danh sách ds, trong nhóm Biến số,
khối phép cộng, gõ 1,
thả biến j,
khối phần tử thứ của ds, kéo j cộng 1 vào, kéo phần tử thứ j cộng 1 vào ô cuối cùng, sau chữ bằng,
ô số thứ tự thả biến j.
Bước ba: ghi số đang cất trong tam vào vị trí j cộng 1. Thêm một khối thay thế phần tử nữa,
ô cuối cùng thả biến tam,
khối phép cộng, gõ 1,
thả biến j, kéo j cộng 1 vào ô số thứ tự.
Giải thích: Vì sao cần biến tạm? Khi ghi phần tử sau đè lên vị trí j, giá trị cũ ở vị trí j sẽ mất. Nên phải cất nó vào tam trước, giống như đổi chỗ hai cốc nước thì cần một cốc thứ ba.
Sau khối nếu, vẫn trong vòng lặp trong: khối thay đổi biến một lượng, chọn j, giữ số 1: sang cặp kế tiếp.
Thêm khối đợi, trong nhóm Điều khiển, để kịp nhìn từng bước, gõ 0 chấm 3 giây.
Cuối cùng, dưới vòng lặp ngoài: khối nói, trong nhóm Hiển thị, gõ: Đã sắp xếp xong! Chương trình sắp xếp hoàn chỉnh: n trừ 1 lượt, mỗi lượt so sánh từng cặp liền kề và đổi chỗ nếu đứng sai thứ tự.
Chạy thử: bấm cờ xanh. Nhìn danh sách trên sân khấu: các số lớn lần lượt nổi dần xuống cuối, giống bọt khí nổi lên. Kết quả: danh sách đã được xếp từ nhỏ đến lớn. Chạy lần nữa với 6 số khác. Sau lượt thứ nhất, số lớn nhất đã về đúng vị trí cuối cùng. Sau lượt thứ hai, đến số lớn thứ nhì. Lần thứ ba: dù các số ban đầu thế nào, sau 5 lượt danh sách luôn được sắp xếp.
Các khối mới trong bài
- Khối thay thế phần tử thứ … của danh sách: ghi một giá trị mới đè lên phần tử ở số thứ tự đã cho.
Kỹ thuật lập trình đã học
- Về kỹ thuật lập trình, bài này ta học: sắp xếp nổi bọt: so sánh từng cặp liền kề, đứng sai thứ tự thì đổi chỗ.
- Hoán đổi cần biến tạm: cất một giá trị vào tam, ghi đè, rồi ghi tam vào chỗ kia.
- Vòng lặp lồng nhau: vòng ngoài đếm lượt, vòng trong đi qua từng cặp.
- Và cách quan sát thuật toán: hiện danh sách trên sân khấu, thêm khối đợi để nhìn từng bước.
Bài tập
Bài tập: tạo thêm một biến đếm số lần đổi chỗ. Rồi sửa điều kiện để danh sách được xếp từ lớn đến nhỏ.