thắc mắc Giải thích về Bubble Sort

Em là học sinh lớp 12 đang tự học lập trình, mong anh chị vozer giải thích bài này.
Đề:
Cho một list các số nguyên n phần tử lst được nhập vào từ bàn phím, bạn hãy viết chương trình sắp xếp các phần tử trong list theo thứ tự tăng dần và hiển thị list đó ra màn hình.
VD: Nếu bạn nhập n = = 5, lst = [4, 2, 1, 6, 4] thì chương trình sẽ hiển thị ra [1, 2, 4, 4, 6]

Bài giải:


Em hiểu hết mà không hiểu về 2 dòng này:
for i in range(len(lst)):
for j in range(i)
Em google thì nó gọi là bubble sort, em đã nắm sơ mà vẫn không hiểu, mong anh chị giải đáp

em mới chỉ hiểu là nếu n =5 thì i sẽ chạy từ 0,1,2,3,4.
j thì chạy từ 0 đến i - 1 nghĩa là 0,1,2,3.

vậy dòng if lst < lst[j] là lst[0] < lst[0] à mn

Để dễ hiểu thì b thử viết ra giấy r chạy từng loop trên giấy xem

Ronald W. Reagan said:

em mới chỉ hiểu là nếu n =5 thì i sẽ chạy từ 0,1,2,3,4.
j thì chạy từ 0 đến i - 1 nghĩa là 0,1,2,3.

vậy dòng if lst < lst[j] là lst[0] < lst[0] à mn

Click to expand...

i chạy từ 0 đến n - 1
j chạy từ 0 đến i - 1
Nếu n = 1
i chạy từ 0 đến 0
Thì không có cái trường hợp lst[0] < lst[0] đâu (vì j chạy từ 0 đến i - 1, mà j phải >= 0)

Lớp 12 thì học chương trình trên lớp thôi. Lên đại học thì vào chương trình khoa học máy tính họ train cho.

lên trang visual algo để xem thuật toán chạy sao là hiểu liền

"bubble sort" hay sắp xếp nổi bọt
là 1 dạng của thuật toán sắp xếp, có độ phức tạp là O(n2) chậm hơn quick sort có độ phức tạp là O(n) nhưng ưu điểm là dễ nhớ, code nhanh. nếu bài toán ko yêu cầu về thời gian chạy thì dùng thuật toán kiểu này viết là nhanh nhất
có 2 loại nữa cũng thuộc cùng dạng với sắp xếp nổi bọt là sắp xếp chèn và sắp xếp chọn
Về giải thuật thì cái này khá đơn giản: (giả sử sắp xếp tăng dần với mảng có độ dài n)
theo đúng tên của nó thì sẽ như 1 bọt khí từ từ nổi dần lên trên
lần đầu tiên chạy từ 1 -> n : cứ 2 số liền kề nhau so sánh nếu số trước lớn hơn số sau thì đổi chỗ 2 số ( sau khi thực hiện n lần thì số tại vị trí n là số lớn nhất của dãy)
lần tiếp theo chạy từ 1 -> n-1: làm tương tự như trên thì ta có số tại vị trí n-1 là số lớn thứ nhì của dãy
....
làn tiếp đến 1 -> 2: làm như trên thì số tại vị trí số 1 là số bé nhất và thứ 2 là số bé thứ nhì

lst = [5,2,3,6,2,1];
for i in range(len(lst)):
for j in range(i):

ex:
lst = [5,2,3,6,2,1];
len(lst) = 6
for i in range(len(lst)) => loop i = 0, 1, 2, 3, 4, 5
for j in range(i): => loop j = 0 cho đến i - 1

Ronald W. Reagan said:

Em là học sinh lớp 12 đang tự học lập trình, mong anh chị vozer giải thích bài này.

Em hiểu hết mà không hiểu về 2 dòng này:
for i in range(len(lst)):
for j in range(i)
Em google thì nó gọi là bubble sort, em đã nắm sơ mà vẫn không hiểu, mong anh chị giải đáp

Click to expand...

Có gì không hiểu cứ hỏi ông youtube nhe em

Ý tưởng là trong n số đưa số nhỏ nhất lên vị trí đầu ở vòng lặp đầu tiên.

Sau đó bỏ qua số đầu tiên, còn lại n-1 số, lặp lại y hệt quá trình trước, đưa số nhỏ nhất trong n-1 số này lên vị trí đầu.

Cứ thế n-2, n-3 ... cho đến hết.

Nếu có vấn đề gì đấy chưa hiểu thì cố gắng chi nhỏ bài toán thành những phần nhỏ hơn, đi bước lớn ko được thì đi từng bước nhỏ một.

Ví dụ như bài trên, cố gắng giải bài toán: cho n số, đưa số nhỏ nhất lên vị trí đầu tiên.
Làm được bài này đã rồi đọc cái mình viết

mấy bài này ngồi lấy tay step by step thấy hay với dễ hiểu lắm

Bạn debug đi sẽ rõ, bạn phải hiểu vòng lặp nó chạy i, j thế nào. Debug là dễ hiểu nhất.

Cháu giác ngộ rồi, cảm ơn các cô chú vozer nha