Tìm hiểu thuật toán sắp xếp chèn trong lập trình với ví dụ bằng lập trình c++ Bạn đang học lập trình c++ và mong muốn tìm hiểu các giải thuật hay sử dụng trong lập trình. Tìm hiểu ngay bài viết này để hiểu rõ hơn về thuật toán sắp xếp chèn (insertion sort) trong lập trình. Thuật toán sắp xếp chèn (insertion sort) Thuật toán sắp xếp chèn (Insertion Sort) là một trong những thuật toán sắp xếp đơn giản và dễ hiểu. Nó hoạt động bằng cách xây dựng dần dần một mảng đã được sắp xếp. Thuật toán này lấy từng phần tử từ mảng chưa được sắp xếp và chèn vào vị trí đúng trong mảng đã được sắp xếp. Nó giống như việc sắp xếp các lá bài trong tay bạn. Bạn chia các lá bài thành hai nhóm: các lá bài đã được sắp xếp và các lá bài chưa được sắp xếp. Sau đó, bạn chọn một lá bài từ nhóm chưa được sắp xếp và đặt nó vào đúng vị trí trong nhóm đã được sắp xếp. Cách hoạt động của Insertion Sort: Bắt đầu từ phần tử thứ hai của mảng (vì phần tử đầu tiên được coi là đã sắp xếp). So sánh phần tử hiện tại với các phần tử trong mảng đã sắp xếp và chèn nó vào vị trí thích hợp. 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++: Sau đây là lập trình mô tả sử dụng thuật toán sắp xếp chèn được lập trình c++ như sau: #include <iostream> using namespace std; void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout <<arr[i]<< endl; } int main() { int arr[] = {15, 9, 30, 10, 1}; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); printArray(arr, n); return 0; } Giải thích mã: Hàm insertionSort: 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ắt đầu từ phần tử thứ hai và tiếp tục đến cuối mảng. - key là phần tử hiện tại cần chèn vào vị trí đúng. - Vòng lặp while di chuyển các phần tử lớn hơn key sang phải để tạo chỗ trống cho key. Hàm printArray: Hàm này in ra mảng đã được sắp xếp. Đầu ra của thuật toán sẽ được dãy sắp xếp tăng dần như sau: 1 9 10 15 30 Minh họa thuật toán qua hình sau: Mô tả hoạt động: Lần 1: 15 lớn hơn 9 nên thực hiện hoán đổi vị trí di chuyển 15 sang bên phải Lần 2: So sánh 30 với 9 và 15 do dãy đã sắp xếp nên vị trí không thay đổi Lần 3: So sánh 10 với 9, 15, 30. Do 10 lớn hơn 9 và nhỏ hơn 15 nên chèn 10 vào giữa 9 và 15 Lần 4: Do 30 lớn hơn 1 nên di chuyển 30 sang bên phải. Ta được dãy đã sắp xếp Phân tích độ phức tạp của sắp xếp chèn: Độ phức tạp thời gian của sắp xếp chèn Trường hợp tốt nhất: O(n) , nếu danh sách đã được sắp xếp, trong đó n là số phần tử trong danh sách. Trường hợp trung bình: O(n 2 ) , Nếu danh sách được sắp xếp ngẫu nhiên Trường hợp xấu nhất: O(n 2 ) , nếu danh sách theo thứ tự ngược lại Độ phức tạp không gian của sắp xếp chèn Không gian phụ trợ: O(1), Sắp xếp chèn yêu cầu O(1) không gian bổ sung, khiến nó trở thành thuật toán sắp xếp tiết kiệm không gian. Ưu điểm của sắp xếp chèn: Đơn giản và dễ thực hiện. Thuật toán sắp xếp ổn định . Hiệu quả đối với các danh sách nhỏ và danh sách gần như được sắp xếp. Tiết kiệm không gian vì đây là thuật toán tại chỗ. Số lượng đảo ngược tỷ lệ thuận với số lượng hoán đổi. Ví dụ, không có hoán đổi nào xảy ra đối với một mảng được sắp xếp và chỉ mất thời gian O(n). Nhược điểm của sắp xếp chèn: Không hiệu quả đối với danh sách lớn. Không hiệu quả bằng các thuật toán sắp xếp khác (ví dụ: sắp xếp trộn, sắp xếp nhanh) trong hầu hết các trường hợp. Ứng dụng của sắp xếp chèn: Sắp xếp chèn thường được sử dụng trong các trường hợp sau: Danh sách này nhỏ hoặc gần như đã được sắp xếp. Sự đơn giản và ổn định là quan trọng. Có thể hữu ích khi mảng đã gần được sắp xếp (rất ít đảo ngược ) Vì sắp xếp chèn phù hợp với các mảng có kích thước nhỏ nên nó được sử dụng trong các thuật toán sắp xếp lai cùng với các thuật toán hiệu quả khác như sắp xếp nhanh và sắp xếp trộn. Khi kích thước mảng con trở nên nhỏ, chúng ta chuyển sang sắp xếp chèn trong các thuật toán đệ quy này. 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 xếp chèn (insertion 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 xếp chèn (insertion sort), insertion sort in c++