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 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 thuật toán sắp xếp chèn
Thuật toán sắp xếp chèn thực hiện sắp xếp dãy số theo cách duyệt từng phần tử và chèn từng phần tử đó vào đúng vị trí trong mảng con(dãy số từ đầu đến phần tử phía trước nó) đã sắp xếp sao cho dãy số trong mảng sắp đã xếp đó vẫn đảm bảo tính chất của một dãy số tăng dần.
- Khởi tạo mảng với dãy con đã sắp xếp có k = 1 phần tử(phần tử đầu tiên, phần tử có chỉ số 0)
- Duyệt từng phần tử từ phần tử thứ 2, tại mỗi lần duyệt phần tử ở chỉ số i thì đặt phần tử đó vào một vị trí nào đó trong đoạn từ [0…i] sao cho dãy số từ [0…i] vẫn đảm bảo tính chất dãy số tăng dần. Sau mỗi lần duyệt, số phần tử đã được sắp xếp k trong mảng tăng thêm 1 phần tử.
- Lặp cho tới khi duyệt hết tất cả các phần tử của mảng.
Ví dụ minh họa
Hàng đầu tiên mô phỏng trạng thái ban đầu của mảng(dãy số chưa sắp xếp). Từ hàng thứ 2 trở đi, ta tìm chèn số đang xét vào vị trí thích hợp để đảm bảo dãy số vẫn tăng dần. Và khi lặp hết tất cả các số trong mảng, ta có trạng thái đã sắp xếp ở hàng cuối cùng.
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> #include <math.h> /* Hàm sắp xếp sử dụng thuật toán sắp xếp chèn */ void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i-1; /* Di chuyển các phần tử có giá trị lớn hơn giá trị key về sau một vị trí so với vị trí ban đầu của nó */ while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } /* Hàm xuất mảng */ void printArray(int arr[], int n) { int i; for (i=0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr)/sizeof(arr[0]); insertionSort(arr, n); printf("Sorted array: \n"); printArray(arr, n); return 0; } |
Kết quả chạy thử chương trình:
|
1 2 |
Sorted array: 5 6 11 12 13 |
Đá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)
- 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)
Nếu thấy bài viết hay và bổ ích, hay like và follow fanpage Học lập trình cùng Nguyễn Văn Hiếu để nhận thông báo về những bài viết mới nhất nhé.
