Code Tu Tam

Thuật toán sắp xếp – Insertion sort (sắp xếp chèn) với C++

Nguyễn Quang Anh
5/5 - (1 bình chọn)

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 Insertion sort

Các bước mô phỏng thuật toán sắp xếp

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

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:

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.

Exit mobile version