การจัดเรียงแบบ Insertion Sort
การจัดเรียงแบบ Insertion Sort
มีหลักการจัดเรียงเหมือนกับการเรียงไพ่ในมือ
โดยจะรับไพ่มาทีละใบ
เมื่อรับไพ่มาแล้วจะหาว่าไพ่ใบนั้นควรจะแทรกลงไปที่ช่องไหนในกองไพ่ที่อยู่ในมือดี
สมมุติฐานคือ ไพ่ในมือจะต้องจัดเรียงไว้อยู่แล้ว อาจจะเรียงจากน้อยไปมาก
หรือจากมากไปน้อยก็ได้ เมื่อรับไพ่มาจนครบทุกใบ
ไพ่ทั้งหมดที่อยู่ในมือจะจัดเรียงกันอย่างถูกต้อง
ตัวอย่างเช่นถ้าเรามีอะเรย์ขนาด
5 ช่องที่มีค่าเก็บอยู่ดังนี้
และถ้าเราต้องการจัดเรียงอะเรย์
a นี้ตามวิธีของ Insertion Sort จะเริ่มต้นโดยกำหนดให้มีตัวแปร
i ชี้ไว้ที่ช่องที่เป็นไพ่ใบใหม่ที่รับเข้ามาในมือ
โดยเริ่มต้นรอบแรกสุด i
= 0 จะมีภาพการทำงานดังนี้
รูปภาพ 1
รอบแรกสุดเมื่อ i = 0
และรอบต่อมาเมื่อ i
= 1 จะมีภาพการทำงานดังนี้
รูปภาพ 2 รอบที่ 2
เมื่อ i = 1 (อ่านจากบนลงล่างและจากซ้ายไปขวา)
และรอบต่อมาเมื่อ 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
01 package aczept.examples.algorithm;
02
03 public class InsertionSort {
04 public static void main(String[] args) {
05 int[] a = {4, 1, 3, 5, 2};
06
07 // i เริ่มที่ 1 เพราะตัวที่ 0 ถือว่าได้มาอยู่ในมือโดยไม่ต้องจัดเรียงใดๆ
08 for(int i
= 1; i < a.length; i++) {
09 int tmp = a[i];
10 int j = i - 1;
11
12 // สแกนจากตัวที่ i - 1
ไปถึงตัวแรกสุด
13 for(; j >= 0 && a[j] > tmp; j--) {
14 a[j + 1]
= a[j];
15 }
16
17 // เมื่อหยุดสแกนช่องที่ j + 1
คือจุดที่จะวางค่าลงไป
18 a[j + 1]
= tmp;
19 }
20
21 // พิมพ์ค่าออกมาดู
22 print(a);
23 }
24
25 public static void print(int[] a) {
26 for(int i
= 0; i < a.length; i++)
27 System.out.print(a[i] + " ");
28 }
29 }
ในกรณีที่ต้องการจัดเรียงค่าข้อมูลชนิดอะไรก็ได้
เราจำเป็นต้องใช้เทคนิค Generic ของ Java 5 ช่วยเล็กน้อย โดยเขียนโค้ดได้ใหม่เป็นดังนี้
ซอร์สโค้ด 2
ไฟล์ InsertionSortGeneric.java สำหรับการจัดเรียงชนิดข้อมูลใดๆก็ได้
01 package aczept.examples.algorithm;
02
03 public class InsertionSortGeneric {
04 public static void main(String[] args) {
05 Integer[] a = {4, 1, 3, 5, 2};
06 sort(a);
07 print(a);
08
09 System.out.println();
10 String[] b = {"Zeebra", "Cat", "Ant",
"Dog"};
11 sort(b);
12 print(b);
13 }
14
15 public static <T extends Comparable<? super T>> void sort(T[] a) {
16 // i เริ่มที่ 1 เพราะตัวที่ 0 ถือว่าได้มาอยู่ในมือโดยไม่ต้องจัดเรียงใดๆ
17 for(int i
= 1; i < a.length; i++) {
18 T tmp = a[i];
19 int j = i - 1;
20
21 // สแกนจากตัวที่
i - 1 ไปถึงตัวแรกสุด
22 for(; j >= 0 && a[j].compareTo(tmp) > 0; j--) {
23 a[j + 1]
= a[j];
24 }
25
26 // เมื่อหยุดสแกนช่องที่ j + 1
คือจุดที่จะวางค่าลงไป
27 a[j + 1]
= tmp;
28 }
29 }
30
31 public static <T extends Comparable<? super T>>void print(T[] a) {
32 for(int i
= 0; i < a.length; i++)
33 System.out.print(a[i] + " ");
34 }
35 }
โปรแกรมสาธิตการจัดเรียงลำดับแบบ Insertion Sort
ท่านสามารถดาวน์โหลดโปรแกรมสาธิตการเรียงลำดับแบบ
Insertion Sort ได้ที่ http://www.softwaredevelop.com/content.jsp?category=algorithm&name=InsertionSort
เมื่อรันโปรแกรม DemoInsertionSortApp.java จะได้ผลลัพธ์ดังนี้
รูปภาพ 7
โปรแกรม DemoInsertionSortApp สำหรับศึกษาวิธีการจัดเรียงแบบ
Insertion
ให้ทดลองกดปุ่ม Play
Auto จะสังเกตเห็นความเปลี่ยนแปลง ของตัวแปรแต่ละตัว หรือกดปุ่ม Play
เพื่อทดลองทำงานทีละขั้น
ความคิดเห็น
แสดงความคิดเห็น