Search…

Insertion Sort

17/08/20201 min read
Giải thuật sắp xếp chèn - Insertion Sort hiện thực bằng C/C++.

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ó.

Thuật toán Insertion Sort.

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ỏ.
IO Stream

IO Stream Co., Ltd

30 Trinh Dinh Thao, Hoa Thanh ward, Tan Phu district, Ho Chi Minh city, Vietnam
+84 28 22 00 11 12
developer@iostream.co

383/1 Quang Trung, ward 10, Go Vap district, Ho Chi Minh city
Business license number: 0311563559 issued by the Department of Planning and Investment of Ho Chi Minh City on February 23, 2012

©IO Stream, 2013 - 2024