Chào mừng các bạn quay trở lại với code từ tâm. Đâ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 chúng ta sẽ cùng tìm hiểu về thuật toán sắp xếp insertion sort. Nội dung bài viết bao gồm các phần sau:
- Ý tưởng của thuật toán
- Các bước mô phỏng
- Code thuật toán bằng C++
- Đánh giá thuật toán
- Một vài ứng dụng của thuật toán
Ý tưởng của thuật toán Insertion sort
- Sắp xếp chèn là một thuật toán sắp xếp đặt một phần tử chưa được sắp xếp vào vị trí thích hợp của nó trong mỗi lần lặp.
- Theo tôi hiểu thì các phần tử được so sánh và swap liên tục giữa các phần tử sao cho đúng vị trí của nó.
- Sắp xếp chèn hoạt động tương tự như chúng ta sắp xếp các quân bài trên tay trong một trò chơi bài.
- Mặc định là thẻ đầu tiên đã được sắp xếp sau đó, chọn một thẻ chưa được sắp xếp. Nếu thẻ chưa được sắp xếp lớn hơn thẻ ban đầu, thì ta giữ nguyên vị trí còn không thì ta đổi vị cho chúng cho số nhỏ hơn lên trước. Theo cách tương tự, các thẻ chưa được sắp xếp khác được lấy và đặt vào đúng vị trí của chúng.
Các bước mô phỏng thuật toán sắp xếp
- 1. Chọn vị trí đầu tiên trong mảng được giả định là đã được sắp xếp.Đặt phần tử thứ hai là khóa. So sánh phần tử thứ hai phần tử đầu tiên. Nếu phần tử đầu tiên lớn phần tử khóa, thì khóa sẽ được đặt trước phần tử đầu tiên(Đổi vị trí phần tử thứ hai đứng trước phần tử đầu tiên).
- 2. Hai phần tử đầu tiên đã được sắp xếp. Lấy phần tử thứ ba và so sánh nó với các phần tử bên trái của nó. Đặt nó ngay sau phần tử nhỏ hơn nó. Nếu không có phần tử nào nhỏ hơn nó, thì hãy đặt nó ở đầu mảng.
- 3. Tương tự, hãy đặt mọi phần tử chưa được sắp xếp vào đúng vị trí của nó
Thực hiện thuật toán Insertion Sort
một cách viết code đơn giản của tôi.
#include <iostream>
using namespace std;
void printAray(int* arr, int n) {
cout << "Giá tri của mảng sau khi sắp xếp là" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
void inserSortArray(int* arr, int n){
for (int i = 1; i < n; i++){
int min = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > min){
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = min;
}
printAray(arr,n);
}
int main()
{
int arr[100];
int n;
cout << "Nhap vao so phan tu cua mang" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "nhap phan tu arr[" << i << "]" << endl;
cin >> arr[i];
}
bubleSortArray(arr, n);
}Đánh giá thuật toán Insertion Sort – Sắp xếp chèn
Độ phức tạp
- 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)
Ứng dụng của thuật toán sắp xếp chèn
Insertion sort được sử dụng khi:
- Số lượng phần tử của mảng nhỏ
- Mảng chỉ còn một vài phần tử cần sắp xếp lại.
Các thuật toán liên quan
Tổng kết
Hy vọng qua bài viết về giải thuật sắp xếp Selection Sort này sẽ giúp các bạn hiểu và vận dụng tốt vòng lặp for cũng như hiểu được ý tưởng của giải thuật này. Cũng khá thú vị đấy chứ nhỉ!
Cảm ơn các bạn đã theo dõi series thuật toán này.
Bình luận: