Insertion Sort

Giới thiệu và hiện thực thuật toán sắp xếp chèn - Insertion Sort qua code C/C++ sắp xếp tăng dần 1 mảng, đây cũng là 1 trong các thuật toán sắp xếp kinh điển và dễ hiện thực.

Insertion Sort

Ý tưởng

Xét danh sách con gồm k phần tử đầu a1 … ak. Với k = 1, danh sách gồm một phần tử đã được sắp xếp thành mảng tăng dần. Giả sử trong danh sách k - 1 phần tử đầu a1 … ak - 1 đã được sắp xếp.

Để sắp xếp phần tử ak = x, tìm vị trí thích hợp của nó trong mảng a1 … ak - 1. Vị trí thích hợp cần tìm là vị trí đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

Hiện thực

void insertionSort(int a[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int x = a[i];
		int j = i;
		while (j > 0 && a[j - 1] > x)
		{
			a[j] = a[j - 1];
			j--;
		}
		a[j] = x;
	}
}

Đánh giá

• Trong trường hợp tốt nhất thuật toán sữ dụng n - 1 phép so sánh và 0 lần hoán vị.
• Trung bình thuật toán sử dụng n2/4 phép so sánh và n2/4 lần hoán vị.
• Trong trường hợp xấu nhất thuật toán sử dụng n2/2 phép so sánh và n2/2 lần hoán vị.
• Thuật toán thích hợp đối với mảng đã được sắp xếp một phần hoặc mảng có kích thước nhỏ.