Các Thuật Toán Sắp Xếp Phần 1 - Sắp Xếp Cơ Bản

Thuật Toán Sắp Xếp Cơ Bản

Hế lô các bạn, như tiêu đề thuật toán sắp xếp cũng là một thuật toán rất quan trọng trong việc học lập trình mà mỗi lập trình viên đều phải biết. Nhận ra được tầm quan trọng đó nên hôm nay, mình đăng bài để chia sẻ cho các bạn cũng như ôn lại một chút về sắp xếp.

Tìm Hiểu Thuật Toán Sắp Xếp

Có rất nhiều thuật toán được dùng trong việc sắp xếp, bài viết này sẽ gửi đến 3 thuật toán sắp xếp cơ bản nhất còn những thuật toán khác mình sẽ đăng ở các bài sau.

Giới Thiệu Chung:

Thuật Toán Sắp Xếp:

Sắp xếp là việc đưa các phần tử của một dãy theo đúng thứ tự (không giảm hoặc không tăng) dựa vào 1 giá trị khoá
Thiết kế thuật toán sắp xếp hiệu quả là một việc đặc biệt quan trọng do việc sắp xếp xuất hiện trong rất nhiều tình huống tính toán
Hai thao tác cơ bản trong một thuật toán sắp xếp:
Compare(a, b): so sánh khoá của 2 phần tử a và b
Swap(a, b): đổi chỗ 2 phần tử a và b cho nhau

Phân Loại Sắp Xếp:

Sắp xếp tại chỗ: sử dụng bộ nhớ trung gian là hằng số, không phụ thuộc độ dài dãy đầu vào
Sắp xếp ổn định: duy trì thứ tự tương đối giữa 2 phần tử có cùng giá trị khoá (vị trí tương đối giữa 2 phần tử có cùng khoá không đổi trước và sau khi sắp xếp)
Thuật toán sắp xếp dựa trên so sánh: sử dụng phép so sánh để quyết định thứ tự phần tử (counting sort không phải là thuật toán sắp xếp dựa trên so sánh)

Thuật Toán Sắp Xếp Chèn (Insertion Sort)

Mô Tả Sắp Xếp Chèn:

Đầu vào: mảng một chiều arr[n] có n phần tử.
Đầu ra: mảng đã được sắp xếp, để không mất tính tổng quát giả sử sắp xếp theo thứ tự không giảm.
Thuật toán bắt đầu bằng các bước lặp từ i = 1 (vị trí thứ 2 trong mảng) và kết thúc tại i = n - 1
Tại mỗi bước lặp i = k, kiểm tra các phần tử từ arr[0] đến arr[k - 1] và xếp phần tử a[k] vào đúng vị trí theo thứ tự.

Mã Nguồn Sắp Xếp Chèn:

Ví Dụ Sắp Xếp Chèn:

Thuật Toán Sắp Xếp Chèn (Insertion Sort)

Thuật Toán Sắp Xếp Lựa Chọn (Selection Sort)

Mô Tả Sắp Xếp Lựa Chọn:

Thuật toán sử dụng vòng lặp duyệt từ arr[0] đến arr[n - 1]
Tại vòng lặp thứ k sẽ duyệt từ arr[k] đến arr[n - 1] để tìm ra vị trí min sau đó hoán đổi vị trí của arr[k] và arr[min].

Mã Nguồn Sắp Xếp Lựa Chọn:

Ví Dụ Sắp Xếp Lựa Chọn:

Sắp Xếp Lựa Chọn (Selection Sort)

Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort)

Mô Tả Sắp Xếp Nổi Bọt:

Thuật toán duyệt từ trái qua phải
Nếu phát hiện phần tử arr[i] > arr[i + 1] thì đổi chỗ 2 phần tử này với nhau
Vòng lặp thực hiện đến khi không còn cặp phần tử nào thỏa mãn điều kiện trên nữa

Mã Nguồn Sắp Xếp Nổi Bọt:

Ví Dụ Sắp Xếp Nổi Bọt:

Sắp Xếp Nổi Bọt (Bubble Sort)

Lời Kết

Trên đây là 3 thuật toán sắp xếp đơn giản, các thuật toán sắp xếp khác mình sẽ đăng trong các bài viết sau. Chúc các bạn một ngày làm việc và học tập hiệu quả và hẹn gặp lại các bạn ở các bài viết sau!