การจัดเรียงแบบ Insertion Sort

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

และถ้าเราต้องการจัดเรียงอะเรย์ a นี้ตามวิธีของ Insertion Sort จะเริ่มต้นโดยกำหนดให้มีตัวแปร i ชี้ไว้ที่ช่องที่เป็นไพ่ใบใหม่ที่รับเข้ามาในมือ

โดยเริ่มต้นรอบแรกสุด i = 0 จะมีภาพการทำงานดังนี้

รูปภาพ 1 รอบแรกสุดเมื่อ i = 0

และรอบต่อมาเมื่อ i = 1 จะมีภาพการทำงานดังนี้

รูปภาพ 2 รอบที่ 2 เมื่อ i = 1 (อ่านจากบนลงล่างและจากซ้ายไปขวา)

และรอบต่อมาเมื่อ i = 2 จะมีภาพการทำงานดังนี้

และรอบต่อมาเมื่อ i = 2 จะมีภาพการทำงานดังนี้

รูปภาพ 3 รอบที่ 3 เมื่อ i = 2 (อ่านจากบนลงล่างและจากซ้ายไปขวา)

และรอบต่อมาเมื่อ i = 3 จะมีภาพการทำงานดังนี้

รูปภาพ 4 รอบที่ 4 เมื่อ i = 3

และรอบสุดท้ายเมื่อ i = 4 จะมีภาพการทำงานดังนี้

รูปภาพ 5 รอบที่ 5 เมื่อ i = 4 (ภาพส่วนที่ 1 ต่อที่ภาพถัดไป)

เมื่อทำไปเรื่อยๆ จะได้ผลลัพธ์สุดท้ายดังนี้

รูปภาพ 6รอบที่ 5 เมื่อ i = 4 ผลลัพธ์สุดท้ายที่เกิดขึ้น

จากขั้นตอนที่อธิบายมาทั้งหมดสามารถเขียนเป็นโปรแกรม Java ได้ดังนี้

ซอร์สโค้ด 1 ไฟล์ InsertionSort.java แสดงวิธีการเขียนโปรแกรมเพื่อจัดเรียงแบบ Selection Sort

package aczept.examples.algorithm;

public class InsertionSort {
	public static void main(String[] args) {
		int[] a = { 4, 1, 3, 5, 2 };

		// i เริ่มที่ 1 เพราะตัวที่ 0 ถือว่าได้มาอยู่ในมือโดยไม่ต้องจัดเรียงใดๆ
		for (int i = 1; i < a.length; i++) {
			int tmp = a[i];
			int j = i - 1;

			// สแกนจากตัวที่ i - 1 ไปถึงตัวแรกสุด
			for (; j >= 0 && a[j] > tmp; j--) {
				a[j + 1] = a[j];
			}

			// เมื่อหยุดสแกนช่องที่ j + 1 คือจุดที่จะวางค่าลงไป
			a[j + 1] = tmp;
		}

		// พิมพ์ค่าออกมาดู
		print(a);
	}

	public static void print(int[] a) {
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
	}
}

ในกรณีที่ต้องการจัดเรียงค่าข้อมูลชนิดอะไรก็ได้ เราจำเป็นต้องใช้เทคนิค Generic ของ Java 5 ช่วยเล็กน้อย โดยเขียนโค้ดได้ใหม่เป็นดังนี้

ซอร์สโค้ด 2 ไฟล์ InsertionSortGeneric.java สำหรับการจัดเรียงชนิดข้อมูลใดๆก็ได้

package aczept.examples.algorithm;

public class InsertionSortGeneric {
	public static void main(String[] args) {
		Integer[] a = { 4, 1, 3, 5, 2 };
		sort(a);
		print(a);

		System.out.println();
		String[] b = { "Zeebra", "Cat", "Ant", "Dog" };
		sort(b);
		print(b);
	}

	public static <T extends Comparable<? super T>> void sort(T[] a) {
		// i เริ่มที่ 1 เพราะตัวที่ 0 ถือว่าได้มาอยู่ในมือโดยไม่ต้องจัดเรียงใดๆ
		for (int i = 1; i < a.length; i++) {
			T tmp = a[i];
			int j = i - 1;

			// สแกนจากตัวที่ i - 1 ไปถึงตัวแรกสุด
			for (; j >= 0 && a[j].compareTo(tmp) > 0; j--) {
				a[j + 1] = a[j];
			}

			// เมื่อหยุดสแกนช่องที่ j + 1 คือจุดที่จะวางค่าลงไป
			a[j + 1] = tmp;
		}
	}

	public static <T extends Comparable<? super T>> void print(T[] a) {
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
	}
}

โปรแกรมสาธิตการจัดเรียงลำดับแบบ Insertion Sort

ท่านสามารถดาวน์โหลดโปรแกรมสาธิตการเรียงลำดับแบบ Insertion Sort ได้ที่ http://www.softwaredevelop.com/content.jsp?category=algorithm&name=InsertionSort เมื่อรันโปรแกรม DemoInsertionSortApp.java จะได้ผลลัพธ์ดังนี้

รูปภาพ 7 โปรแกรม DemoInsertionSortApp สำหรับศึกษาวิธีการจัดเรียงแบบ Insertion

ให้ทดลองกดปุ่ม Play Auto จะสังเกตเห็นความเปลี่ยนแปลง ของตัวแปรแต่ละตัว หรือกดปุ่ม Play เพื่อทดลองทำงานทีละขั้น