Sorting · Sắp xếp
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Trang này cần trình duyệt gần đây (hỗ trợ SharedArrayBuffer). Vui lòng cập nhật Chrome, Edge, Firefox hoặc Safari lên phiên bản mới nhất.
English
Putting items in order
- Sorting arranges a list into order, usually smallest first.
- The key move is a swap: exchange two items.
- In Python:
a[i], a[j] = a[j], a[i]swaps two list items in one line.
Tiếng Việt
Sắp xếp các phần tử
- Sắp xếp sắp xếp một danh sách theo thứ tự, thường là từ nhỏ đến lớn.
- Hành động chính là một lần hoán đổi: trao đổi hai phần tử.
- Trong Python:
a[i], a[j] = a[j], a[i]hoán đổi hai phần tử của danh sách trong một dòng mã.
English
Bubble sort
- Compare each pair of neighbours; swap them if they are out of order.
- After one full pass, the largest item has "bubbled" to the end.
- Repeat the passes until no swaps are needed.
Tiếng Việt
Sắp xếp nổi bọt
- So sánh từng cặp kẻ cạnh; hoán đổi chúng nếu chúng không đúng thứ tự.
- Sau một lượt duyệt hoàn chỉnh, phần tử lớn nhất đã "nổi" lên cuối cùng.
- Lặp lại các lượt duyệt cho đến khi không còn cần hoán đổi nữa.
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
English
Insertion sort
- Treat the left part of the list as already sorted.
- Take the next item and slide it left until it sits in the right place.
- Like sorting playing cards in your hand, one at a time.
Tiếng Việt
Sắp xếp chèn
- Coi phần bên trái của danh sách là đã được sắp xếp rồi.
- Lấy phần tử tiếp theo và trượt nó sang trái cho đến khi nó vào đúng vị trí.
- Giống như việc sắp xếp các lá bài trong tay, từng lá một.
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
English
Compare them
- Both check roughly
n × npairs, so both are slow on big lists. - Insertion sort is fast when the list is almost sorted already.
- Faster methods exist, but bubble and insertion are easy to understand.
Tiếng Việt
So sánh chúng
- Cả hai đều kiểm tra khoảng
n × ncặp, nên cả hai đều chậm trên danh sách lớn. - Sắp xếp chèn nhanh khi danh sách gần như đã được sắp xếp sẵn.
- Có các phương pháp nhanh hơn, nhưng sắp xếp nổi bọt và sắp xếp chèn dễ hiểu hơn.
English
In Cambridge pseudocode
- Bubble sort with a
tempvariable for the swap.
Tiếng Việt
Trong pseudocode Cambridge
- Sắp xếp nổi bọt với một biến
tempdùng để hoán đổi.
FOR i ← 0 TO LENGTH(list) - 2
FOR j ← 0 TO LENGTH(list) - 2 - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
English
Common mistakes
- Bubble and insertion sort are both O(n²).
- Trace a small list by hand to check your sort works.
Tiếng Việt
Lỗi thường gặp
- Cả sắp xếp nổi bọt và sắp xếp chèn đều có độ phức tạp O(n²).
- Vẽ thử một danh sách nhỏ bằng tay để kiểm tra thuật toán sắp xếp của bạn có hoạt động không.
English
Now you try
- Each task changes the list in place — no need to return it.
- Press Check answer to test your code.
Tiếng Việt
Bây giờ bạn thử
- Mỗi nhiệm vụ thay đổi danh sách ngay tại chỗ — không cần trả về nó.
- Nhấn Check answer (Kiểm tra câu trả lời) để thử mã của bạn.
Explore · Khám phá
Watch a sort run · Xem quá trình sắp xếp chạy
Sorting repeatedly compares and swaps until everything is in order. · Sắp xếp liên tục so sánh và hoán đổi cho đến khi mọi thứ đều đúng thứ tự.
Write swap(items, i, j) that exchanges the items at index i and index j in the list. Change the list in place (no return). · Viết swap(items, i, j) hoán đổi các phần tử tại chỉ số i và chỉ số j trong danh sách. Thay đổi danh sách ngay tại chỗ (không return).
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write bubble_sort(items) that sorts the list into ascending order using bubble sort. Change the list in place. · Viết bubble_sort(items) sắp xếp danh sách theo thứ tự tăng dần dùng bubble sort. Thay đổi danh sách ngay tại chỗ.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write insertion_sort(items) that sorts the list into ascending order using insertion sort. Change the list in place. · Viết insertion_sort(items) sắp xếp danh sách theo thứ tự tăng dần dùng insertion sort. Thay đổi danh sách ngay tại chỗ.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.