Bỏ qua đến nội dung chính
Mục lục

Trộn hai list đã sắp xếp bằng Python (merge sorted lists)

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 5/10 · Chương 25

Bài tập phỏng vấn Python

  • 7 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

Trộn hai list đã sắp xếp bằng Python là ghép hai list đã xếp tăng dần thành một list cũng tăng dần, như gộp bảng điểm của hai lớp. Bài này là lõi của merge sort và là câu phỏng vấn quen thuộc vì người hỏi thường cấm gọi sorted(). Trang này so cách gọi sorted() với cách hai con trỏ, chỉ ra hai lỗi hay gặp, rồi cho bạn một bài tập được chấm ngay trên trang.

Cần biết trước: vòng lặp while, extend() và merge sort.

Đề bài

Hai lớp gửi điểm thi, mỗi lớp một list đã xếp tăng dần: lớp A [6.5, 7.0, 8.5, 9.0], lớp B [5.0, 7.0, 9.5]. Viết hàm tron(a, b) trả về một list mới gồm mọi điểm của cả hai lớp, xếp tăng dần.

Ví dụ vào ra: tron([6.5, 7.0, 8.5, 9.0], [5.0, 7.0, 9.5]) trả về [5.0, 6.5, 7.0, 7.0, 8.5, 9.0, 9.5].

Câu hỏi làm rõ trước khi viết code:

  • Điểm trùng nhau giữa hai lớp có giữ cả hai không? Có, 7.0 xuất hiện hai lần.

  • Một lớp có thể chưa gửi điểm, tức list rỗng không? Có.

  • Hàm có được sửa hai list đưa vào không? Không, trả về list mới.

  • Có được gọi sorted() hay sort() không? Không, người phỏng vấn muốn bạn tận dụng việc hai list đã xếp sẵn.

Cách 1: nối hai list rồi gọi sorted()

Cách ngắn nhất là nối hai list bằng + rồi để Python xếp lại:

python
def tron(a, b):
    return sorted(a + b)

print(tron([6.5, 7.0, 8.5, 9.0], [5.0, 7.0, 9.5]))

KẾT QUẢ

[5.0, 6.5, 7.0, 7.0, 8.5, 9.0, 9.5]

Kết quả đúng, và trong code thật đây thường là dòng nên viết. Nhưng nó vi phạm điều kiện của đề, và sorted() (xem sắp xếp list) không biết hai list đã xếp sẵn: nó phải tự dò ra điều đó.

Vì sao sorted() tốn nhiều phép so hơn cần thiết

Muốn đếm số phép so của sorted(), bạn bọc mỗi số trong một object tự đếm: lớp So kế thừa int nên vẫn so như số, và định nghĩa __lt__, phép so < mà sắp xếp gọi (xem so sánh và sắp xếp object). Hai list nghìn số, một list số chẵn, một list số lẻ:

python
class So(int):
    dem = 0
    def __lt__(self, khac):
        So.dem += 1
        return int(self) < int(khac)

lop_a, lop_b = [], []
for i in range(1000):
    lop_a.append(So(2 * i))
    lop_b.append(So(2 * i + 1))
ket_qua = sorted(lop_a + lop_b)
print(ket_qua[:4], round(So.dem, -2))

KẾT QUẢ

[0, 1, 2, 3] 4000

sorted() làm khoảng 4.000 phép so cho 2.000 số: gần 2.000 lần để dò ra hai đoạn đã xếp trong list nối, rồi gần 2.000 lần nữa để trộn chúng. Con số đúng lệch một hai lần giữa các bản Python, nên dòng print làm tròn tới hàng trăm. Cách hai con trỏ dưới đây so tối đa 1.999 lần, vì mỗi phép so lấy ra một phần tử và phần tử cuối không cần so. Nối a + b cũng tạo thêm một list 2.000 phần tử chỉ để xếp lại.

Cách 2: hai con trỏ đi song song

Hai chỉ số i và j trỏ vào phần tử nhỏ nhất chưa lấy của mỗi list. Mỗi lượt lấy phần tử nhỏ hơn và đẩy con trỏ của nó lên một bước. Vòng while dừng khi một list hết, rồi extend() nối phần còn lại của list kia:

python
def tron(a, b):
    ket_qua = []
    i, j = 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            ket_qua.append(a[i])
            i += 1
        else:
            ket_qua.append(b[j])
            j += 1
    ket_qua.extend(a[i:])
    ket_qua.extend(b[j:])
    return ket_qua

print(tron([6.5, 7.0, 8.5, 9.0], [5.0, 7.0, 9.5]), tron([], [7.0]))

KẾT QUẢ

[5.0, 6.5, 7.0, 7.0, 8.5, 9.0, 9.5] [7.0]

Đây là hàm tron của bài merge sort, bài đó đã giải thích vì sao phần còn lại nối thẳng được mà không cần so thêm. Dấu <= lấy phần tử của a trước khi hai điểm bằng nhau, nên 7.0 của lớp A đứng trước 7.0 của lớp B. Hàm chỉ đọc a và b, list kết quả là list mới. Đổi tron([], [7.0]) thành tron([8.0], []) rồi chạy lại: phần sau in [8.0].

Lỗi thứ hai không báo gì, vì kết quả trông đúng.

Nói gì với người phỏng vấn

Hỏi trước các câu của mục Đề bài, nhất là có giữ phần tử trùng không và có được sửa list đầu vào không. Rồi trình bày:

  • "Cách nhanh để viết là sorted(a + b), nhưng nó không tận dụng việc hai list đã xếp."

  • "Tôi dùng hai con trỏ, mỗi lượt so hai phần tử đầu chưa lấy và lấy phần tử nhỏ hơn. Một list hết thì nối phần còn lại của list kia."

  • "Mỗi phần tử được lấy đúng một lần, nên thời gian là O(n + m), bộ nhớ thêm O(n + m) cho list kết quả. Hai list đầu vào không bị sửa."

  • "Đây chính là bước trộn của merge sort."

  • "Tôi đã xét một list rỗng, cả hai list rỗng, phần còn lại ở cả hai phía và phần tử trùng nhau."

Kiểm tra nhanh

  1. Hàm tron của cách 2 làm ____ phép so a[i] <= b[j] khi gọi tron([1, 4], [2, 3, 5]).

  2. Trong cách 2, vì sao điều kiện vòng lặp là i < len(a) and j < len(b) thay cho or?

    • Vì với or, vòng lặp vẫn chạy khi một list đã hết và a[i] hay b[j] báo IndexError
    • Vì and làm vòng lặp so ít hơn một lần
    • Vì với or, các điểm bằng nhau bị đảo thứ tự
  3. Hàm trộn lấy phần tử bằng a.pop(0) và b.pop(0) ở khung bẫy thứ hai: những điều nào đúng?

    • List trả về vẫn trộn đúng
    • Python báo IndexError khi một list hết
    • Sau lời gọi, lop_a là list rỗng
    • Mỗi lần pop(0) dời các phần tử còn lại lên một ô
Đúng hết lần đầu +15 XP

Bài tập

Gộp mã khách của hai ca, bỏ trùng

Quán cà phê ghi mã khách của ca sáng và ca chiều, mỗi ca một list đã xếp tăng dần, có thể lặp lại khi một khách mua hai lần. Viết hàm tron_khong_trung(a, b) trả về list mới gồm mọi mã khách, xếp tăng dần, mỗi mã một lần. Không sửa a hay b. Không gọi sorted(), .sort() hay module heapq: trình chấm đưa vào hai ca 300 khách và đếm số phép so trên các mã, đi qua mỗi list một lượt như cách 2 thì qua.

Ví dụ: tron_khong_trung([101, 103, 103, 106], [102, 103, 105]) trả về [101, 102, 103, 105, 106].

Trả về: các mã khách, một list.

Ôn lại: merge sort.

python
def tron_khong_trung(a, b):
    pass  # Viết thân hàm thay cho dòng này

Câu hỏi thường gặp

Tự trộn hai list có nhanh hơn sorted() trong Python không?

Thường là không. Trên máy rảnh với Python 3.14, sorted(a + b) cho hai list 100.000 số chạy nhanh hơn hàm tron của cách 2 vài lần, vì sorted() viết bằng C. Hàm tự viết làm ít phép so hơn, nên nó có lợi khi mỗi phép so tốn nhiều công. Ở buổi phỏng vấn, người hỏi muốn thấy bạn trộn được.

Thư viện chuẩn Python có hàm trộn sẵn không?

Có: heapq.merge(a, b) của module heapq trộn các list đã xếp mà không xếp lại từ đầu. Nó trả về một đối tượng duyệt được bằng for, bọc trong list() để có list: list(heapq.merge([6.5, 9.0], [7.0])) cho [6.5, 7.0, 9.0].

Trộn ba list đã sắp xếp trở lên thì làm thế nào?

Gọi tron hai lần: tron(tron(a, b), c). Với nhiều list, trộn theo từng cặp như các tầng của merge sort thì mỗi phần tử được chép ít lần hơn so với trộn dồn từng list vào một list kết quả ngày càng dài.

Chủ đề

trộn hai list đã sắp xếp python

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập