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.
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
style="margin-left: auto; margin-right: auto;"
>
data-original-height="1000"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiNopsdyVMkxNh2dhlaNnl-8sjitPCcslQErQPBUyM3pYmudhEdh85CxlZDh2d0FflH13eNdn7die04s2ioYytoDP9P1AAXlptTHOE42FL8_VZpFLjZsK5xE9vnt4EKhhwge-NvZIYyEGk/s16000/sort-1.png"
/>
Các Thuật Toán Sắp Xếp Phần 1 - Sắp Xếp Cơ Bản
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:
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
style="margin-left: auto; margin-right: auto;"
>
data-original-height="849"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuoakapRzrqwGSNHy8NYb6ne-_TEtQCrF4TzkYCiOkis6Voqo1k12D6UHvREb0VpYJf2G0ad7wN7zfEx2T-wMzb7L1BUBhsGwqEB90A0m8EXfExQnA1dCO0IS48naQXCyVdvzx9C24qpQ/s16000/sort-1.png"
/>
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:
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
style="margin-left: auto; margin-right: auto;"
>
data-original-height="996"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEimk-j0B521KEooeZsoZ1W6LUrDhWUsoZ1CLXQzs-UU58DaGXEP8HqzRImkc9AGtE7oMfq6C5xbcQd41_2zjwqwM84kcbmhFMtRENXmmW6Eqb7lMh22H3TlPfVykV6K_33tbdlkI91ri1I/s16000/sort-2.png"
/>
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:
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
imageanchor="1"
style="margin-left: auto; margin-right: auto;"
>
data-original-height="686"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVm3AeTFyN_RZf4nSmD19cjfBR6cFKtlL00YTQtQgbnXnFB49EzdY9l328IloBRckXjTPnGS0iaGhKVfJiKvO9fQgjIg55y565Vsh71eVtqFMABWMPNRX5NYeS09BAtI3lmweE37LaxPc/s16000/sort-3.png"
/>
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!
Copyright © Phạm Văn Linh