Thuật Toán Sắp Xếp
Hế lô các bạn. Tiếp tục series thuật toán chúng ta sẽ tìm hiểu tiếp về thuật toán sắp xếp. Hôm nay mình sẽ chia sẻ tiếp cho các bạn thêm 2 cách sắp xếp nữa đó là sắp xếp trộn và sắp xếp nhanh.
 |
| Các Thuật Toán Sắp Xếp Phần 2 |
Tìm Hiểu Thuật Toán
Không luyên thuyên nữa dưới đây sẽ là 2 thuật toán sắp xếp của hôm nay.
Sắp Xếp Trộn (Merge Sort):
Mô Tả Sắp Xếp Trộn:
- Giải thuật dựa vào thuật toán chia để trị.
- Đầu tiên ta sẽ chia đôi dãy ra thành 2 dãy nhỏ có độ dài bằng nhau.
- Sau đó ta dùng đệ quy để tiếp tục chia các dãy nhỏ cho đến khi không chia được nữa.
- Sau khi không chia được nữa ta sẽ trộn các dãy đã chia lại theo thứ tự yêu cầu của đề bài.
- Đến khi thực hiện xong thuật toán đệ quy ta thu được dãy đã được sắp xếp.
Mã Nguồn Sắp Xếp Trộn:
Các bạn xem mã nguồn, đọc phần chú thích và làm lại để hiểu hơn nhé!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void merge(int arr[], int L, int M, int R) { | |
| int i = L; | |
| int j = M + 1; | |
| int ta[128]; | |
| for (int k = L; k <= R; k++) { | |
| // Trường hợp đã duyệt hết phần tử bên trái | |
| if (i > M) ta[k] = arr[j]; | |
| // Trường hợp đã duyệt hết phần tử bên phải | |
| else if (j > R) ta[k] = arr[i]; | |
| // So sánh và sắp xếp | |
| else { | |
| if (arr[i] < arr[j]) { | |
| ta[k] = arr[i]; | |
| i++; | |
| } else { | |
| ta[k] = arr[j]; | |
| j++; | |
| } | |
| } | |
| } | |
| // Sắp xếp lại mảng arr[] từ mảng ta[] | |
| for (int k = L; k <= R; k++) { | |
| arr[k] = ta[k]; | |
| } | |
| } | |
| void mergeSort(int arr[], int L, int R) { | |
| // Đệ quy chia nhỏ mảng arr[] đến khi không chia được nữa | |
| if (L < R) { | |
| int M = (L + R)/2; | |
| mergeSort(arr, L, M); | |
| mergeSort(arr, M + 1, R); | |
| merge(arr, L, M, R); | |
| } | |
| } |
Ví Dụ Sắp Xếp Trộn:
 |
| Sắp Xếp Trộn (Merge Sort) |
Sắp Xếp Nhanh(Quick Sort)
Mô Tả Sắp Xếp Nhanh:
- Chọn một phần tử bất kì làm trụ.
- Sắp xếp các phần tử còn lại sao cho:
- Các phần tử nhỏ hơn trụ nằm ở bên trái của trụ.
- Các phần tử lớn hơn trụ nằm ở bên phải của trụ.
- Tiếp tục dùng sắp xếp nhanh để sắp xếp các dãy con bên trái và phải trụ.
Mã Nguồn Sắp Xếp Nhanh:
Để không mất tính tổng quát mình chọn phần tử đầu tiên làm trụ.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| int partition(int arr[], int L, int R) { | |
| int pivot = arr[L]; // Lấy phần tử đầu tiên làm pivot | |
| int i = L; | |
| int j = R + 1; | |
| while(i < j) { | |
| // Tìm phần tử lớn hơn pivot | |
| i++; | |
| while(i <= R && arr[i] < pivot) { | |
| i++; | |
| } | |
| // Tìm phần tử nhỏ hơn pivot | |
| j--; | |
| while(j >= L && arr[j] > pivot) { | |
| j--; | |
| } | |
| // Hoán đổi 2 phần tử tìm được | |
| swap(arr[i], arr[j]); | |
| } | |
| swap(arr[i], arr[j]); | |
| swap(arr[L], arr[j]); // Đưa pivot vào giữa | |
| return j; // return vị trí pivot | |
| } | |
| void quickSort(int arr[], int L, int R) { | |
| if (L < R) { | |
| int M = partition(arr, L, R); | |
| // quickSort nửa nhỏ | |
| if (L < M) { | |
| quickSort(arr, L, M - 1); | |
| } | |
| // quickSort nửa lớn | |
| if (M < R) { | |
| quickSort(arr, M + 1, R); | |
| } | |
| } | |
| } |
Ví Dụ Sắp Xếp Nhanh:
 |
| Sắp Xếp Nhanh(Quick Sort) |
Lời Kết
Vậy là bài viết hôm nay mình đã chia sẻ cho các bạn thêm 2 thuật toán sắp xếp nữa đó là sắp xếp trộn và sắp xếp nhanh. Nếu có bất kì thắc mắc nào hãy comment ở bên dưới. Chúc các bạn giữa tuần vui vẻ và có một ngày làm việc hiệu quả!
Đánh Giá Bài Viết:
