Thuật toán sắp xếp

Hiểu bài

Sắp xếp đưa một dãy phần tử về thứ tự yêu cầu. Thao tác cơ bản là hoán đổi hai giá trị; ví dụ đổi chất lỏng giữa hai cốc cần một cốc thứ ba làm nơi trung gian.

Với sắp xếp nổi bọt theo thứ tự tăng dần, ở mỗi vòng lặp ta so sánh hai phần tử cạnh nhau từ cuối dãy lên vị trí đang xét. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ. Cuối vòng lặp, phần tử nhỏ nhất “nổi” lên vị trí đầu tiên chưa được cố định. Các vòng sau lặp lại với phần còn lại; nếu không còn hoán đổi thì dãy đã được sắp xếp.

Sắp xếp chọn xét từng vị trí, so sánh phần tử tại vị trí đó với các phần tử phía sau; khi gặp phần tử nhỏ hơn thì hoán đổi. Với dãy 3, 4, 1, 5, 2, vòng đầu đưa 1 về đầu; các vòng tiếp theo tạo kết quả 1, 2, 3, 4, 5.

Sơ đồ sắp xếp dãy số 3, 4, 1, 5, 2 theo từng vòng lặp, cuối cùng thành 1, 2, 3, 4, 5. SGK trang 81