Insertion Sort คือ?

การจัดเรียงแบบแทรก เป็นอัลกอริทึมการจัดเรียงอย่างง่าย มีหลักการคล้ายกับการเรียงไพ่ในมือของคุณ อาร์เรย์จะแบ่งออกเป็นสองส่วน ส่วนที่จัดเรียงแล้วกับส่วนที่ยังไม่ถูกจัดเรียง เมื่อได้รับไพ่จากส่วนที่ยังไม่จัดเรียงมาแล้วควรเอาไพ่ไปแทรกช่องไหนในส่วนที่ถูกจัดเรียงแล้วดี อาจจะเรียงจากน้อยไปมาก หรือจากมากไปน้อยก็ได้

หลักการทำงานของ Insertion Sort

ตัวอย่าง: 4 3 2 1 5 6 เรียงจากน้อยไปมาก

รอบที่ 1: เปรียบเทียบคู่แรกในอาร์เรย์ จะเห็นว่า 4 > 3 ให้ทำการสลับตำแหน่ง (Swap)
4 3 2 1 5 6 -> 3 4 2 1 5 6

รอบที่ 2: ตอนนี้มีสองตัวที่เรียงแล้วนั่นคือ 3 4 ให้เปรียบเทียบคู่ต่อมาคือ 4 กับ 2 จะเห็นว่า 4 > 2 ให้ทำการสลับ
3 4 2 1 5 6 -> 3 2 4 1 5 6
หลังจากสลับแล้ว จะเห็นได้ว่า 3 กับ 2 ยังไม่ถูกจัดเรียง จึงต้องสลับอีกครั้ง
3 2 4 1 5 6 -> 2 3 4 1 5 6

รอบที่ 3: เปรียบเทียบคู่ต่อมาคือ 4 กับ 1 จะเห็นว่า 4 > 1 ให้สลับตำแหน่ง
2 3 4 1 5 6 -> 2 3 1 4 5 6
จะเห็นได้ว่าอาร์เรย์ยังไม่ถูกจัดเรียง ดังนั้นจึงต้องสลับจนกว่า 1 จะอยู่ในตำแหน่งที่เหมาะสม 3 > 1 จึงสลับ
2 3 1 4 5 6 -> 2 1 3 4 5 6
2 > 1 จึงสลับ
2 1 3 4 5 6 -> 1 2 3 4 5 6

จะเห็นได้ว่าอาร์เรย์ถูกจัดเรียงสำเร็จแล้ว มองง่ายๆมันเหมือนกับการจั่วไพ่ขึ้นมาแล้วเอาไพ่ใบนั้นไปแทรกในตำแหน่งที่เหมาะสมที่สุดนั่นเอง

ตัวอย่างโค้ด Insertion Sort

#include <iostream>
using namespace std;

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

void printArray(int arr[], int n){
	int i;
	for (i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
}

int main(){
	int arr[] = { 12, 11, 13, 5, 6 };
	int N = sizeof(arr) / sizeof(arr[0]);
	insertionSort(arr, N);
	cout << "Sorted array: ";
	printArray(arr, N);
	return 0;
}

ผลลัพธ์:
Sorted array: 5 6 11 12 13

Time Complexity: O(N²)