Tìm hiểu thuật toán sắp xếp lựa chọn selection sort với ví dụ bằng lập trình c++ Trong bài viết này Stanford sẽ chia sẻ cho các bạn học lập trình về thuật toán sắp xếp lựa chọn và cài đặt thuật toán qua ví dụ minh họa bằng lập trình c++. Thuật toán sắp xếp lựa chọn (selection sort) Thuật toán sắp xếp chọn (Selection Sort) là một thuật toán sắp xếp đơn giản nhưng hiệu quả cho các mảng nhỏ. Thuật toán này hoạt động bằng cách chia mảng thành hai phần: phần đã được sắp xếp và phần chưa được sắp xếp. Nó liên tục chọn phần tử nhỏ nhất từ phần chưa được sắp xếp và hoán đổi với phần tử đầu tiên của phần chưa được sắp xếp. Cách hoạt động của Selection Sort: Tìm phần tử nhỏ nhất trong mảng chưa được sắp xếp. Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của mảng chưa được sắp xếp. Di chuyển ranh giới giữa mảng đã sắp xếp và mảng chưa sắp xếp sang phải một vị trí. Lặp lại quá trình cho đến khi toàn bộ mảng được sắp xếp. Cài đặt thuật toán bằng lập trình c++: #include <iostream> using namespace std; void selectionSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; swap(arr[min_idx], arr[i]); } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } int main() { int arr[] = {20, 12, 10, 15, 2}; int n = sizeof(arr) / sizeof(arr[0]); selectionSort(arr, n); printArray(arr, n); return 0; } Giải thích mã: Hàm selectionSort: Hàm này thực hiện sắp xếp chọn trên mảng arr có độ dài n. - Vòng lặp for bên ngoài di chuyển ranh giới giữa mảng đã sắp xếp và mảng chưa sắp xếp. - min_idx là chỉ số của phần tử nhỏ nhất trong mảng chưa được sắp xếp. - Vòng lặp for bên trong tìm phần tử nhỏ nhất trong mảng chưa được sắp xếp. - Hàm swap hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của mảng chưa được sắp xếp. Hàm printArray: Hàm này in ra mảng đã được sắp xếp. Hình minh họa ví dụ mô tả thuật toán sắp xếp lựa chọn: Phân tích độ phức tạp của sắp xếp lựa chọn Độ phức tạp thời gian: O(n 2 ) , vì có hai vòng lặp lồng nhau: Một vòng lặp để chọn từng phần tử của Mảng một = O(n) Một vòng lặp khác để so sánh phần tử đó với mọi phần tử Mảng khác = O(n) Do đó độ phức tạp tổng thể = O(n) * O(n) = O(n*n) = O(n 2 ) Không gian phụ trợ: O(1) vì bộ nhớ bổ sung duy nhất được sử dụng cho các biến tạm thời. Ưu điểm của sắp xếp lựa chọn Dễ hiểu và dễ thực hiện, lý tưởng cho việc giảng dạy các khái niệm phân loại cơ bản. Chỉ yêu cầu không gian bộ nhớ bổ sung O(1) không đổi. Nó đòi hỏi ít số lần hoán đổi (hoặc ghi bộ nhớ) hơn so với nhiều thuật toán chuẩn khác. Chỉ có sắp xếp theo chu kỳ mới đánh bại được nó về mặt ghi bộ nhớ. Do đó, nó có thể là lựa chọn thuật toán đơn giản khi ghi bộ nhớ tốn kém. Nhược điểm của sắp xếp lựa chọn Thuật toán sắp xếp lựa chọn có độ phức tạp là O(n^2) khiến nó chậm hơn so với các thuật toán như Sắp xếp nhanh hoặc Sắp xếp trộn. Không duy trì được thứ tự tương đối của các phần tử bằng nhau, nghĩa là nó không ổn định. Ứng dụng của sắp xếp lựa chọn Hoàn hảo cho việc giảng dạy các cơ chế sắp xếp cơ bản và thiết kế thuật toán. Phù hợp với các danh sách nhỏ, trong đó chi phí cho các thuật toán phức tạp hơn là không hợp lý và việc ghi bộ nhớ tốn kém vì nó yêu cầu ít thao tác ghi bộ nhớ hơn so với các thuật toán sắp xếp tiêu chuẩn khác. Thuật toán sắp xếp đống dựa trên thuật toán sắp xếp chọn. Như vậy qua bài viết này, Stanford đã giúp các bạn học lập trình hiểu hơn về thuật toán sắp lựa chọn (selection sort) cũng như cài đặt thuật toán bằng lập trình c++. Để hiểu rõ hơn thuật toán này bạn có thể lập trình theo hướng dẫn trong bài viết này nhé. Bạn có thể tìm hiểu các thuật toán sắp xếp trong lập trình ở đây. Chúc các bạn thành công ! Bạn có thể bắt đầu ngay con đường chinh phục của bạn để trở thành lập trình viên chuyên nghiệp trong tương lai bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé. ==========🎬 🎬 🎬========== ☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ Hotline: 0963 723 236 - 0866 586 366 Website: https://stanford.com.vn Facebook: https://www.facebook.com/Stanford.com.vn Youtube: http://bit.ly/2TkKT7I Tags: thuật toán sắp lựa chọn (selection sort)