Bài 48. Thuật toán sắp xếp chọn (Selection sort)
Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++. Bài viết đầu tiên này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp chọn. Nội dung bài viết bao gồm các phần sau:
- Ý tưởng của thuật toán
- Ví dụ minh họa
- Minh họa thuật toán sử dụng ngôn ngữ C++
- Đánh giá thuật toán
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu
NỘI DUNG BÀI VIẾT
Ý tưởng của thuật toán sắp xếp chọn
Thuật toán sắp xếp chọn sẽ sắp xếp một mảng bằng cách đi tìm phần tử có giá trị nhỏ nhất(giả sử với sắp xếp mảng tăng dần) trong đoạn đoạn chưa được sắp xếp và đổi cho phần tử nhỏ nhất đó với phần tử ở đầu đoạn chưa được sắp xếp(không phải đầu mảng). Thuật toán sẽ chia mảng làm 2 mảng con
- Một mảng con đã được sắp xếp
- Một mảng con chưa được sắp xếp
Tại mỗi bước lặp của thuật toán, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp.
Ví dụ minh họa
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
arr[] = 62 24 15 22 1 // Tìm phần tử nhỏ nhất trong trong arr[0...4] // và đổi chỗ nó với phần tử đầu tiên [1] 24 15 22 62 // Tìm phần tử nhỏ nhất trong trong arr[1...4] // và đổi chỗ nó với phần tử đầu tiên của arr[1...4] 1 [15] 24 22 62 // Tìm phần tử nhỏ nhất trong trong arr[2...4] // và đổi chỗ nó với phần tử đầu tiên của arr[2...4] 1 15 [22] 24 62 // Tìm phần tử nhỏ nhất trong trong arr[3...4] // và đổi chỗ nó với phần tử đầu tiên của arr[3...4] 11 12 22 [24] 62 |
Minh họa thuật toán sử dụng ngôn ngữ C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
// Code from https://blog.luyencode.net #include <stdio.h> // Hàm đổi chỗ 2 số nguyên void swap(int &xp, int &yp) { int temp = xp; xp = yp; yp = temp; } // Hàm selection sort void selectionSort(int arr[], int n) { int i, j, min_idx; // Di chuyển ranh giới của mảng đã sắp xếp và chưa sắp xếp for (i = 0; i < n-1; i++) { // Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên swap(arr[min_idx], arr[i]); } } /* Hàm xuất mảng */ void printArray(int arr[], int size) { int i; for (i=0; i < size; i++) printf("%d ", arr[i]); printf("n"); } int main() { int arr[] = {64, 25, 12, 22, 11}; int n = sizeof(arr)/sizeof(arr[0]); selectionSort(arr, n); printf("Sorted array: n"); printArray(arr, n); return 0; } |
Kết quả chạy kiểm tra
|
1 2 |
Sorted array: 11 12 22 25 64 |
Đánh giá thuật toán sắp xếp chọn
Độ phức tạp thuật toán
- Trường hợp tốt: O(n^2)
- Trung bình: O(n^2)
- Trường hợp xấu: O(n^2)
Không gian bộ nhớ sử dụng: O(1)
Theo dõi lập trình không khó tại:
