Data Structure and Algorithm

85 เส้นทางเชอ่ื มต่อ 2 เส้นจาก E ไป D มี 1 เส้นทาง คือ EBD เสน้ ทางเช่ือมต่อ 2 เส้นจาก E ไป E มี 2 เส้นทาง คือ EBE และ EDE ค้านวนหาจา้ นวนเสน้ เชือ่ มตอ่ 3 เสน้ 20021 01100 ABCDE 03211 10011 A05412 02201 10010 B52164 21031 01101 =C 4 1 0 5 2 11112 01010 D1652 4 E24242 เส้นทางเชอ่ื มต่อ 3 เส้นจาก B ไป B มี 2 เส้นทาง คือ BDEB และ BEDB เสน้ ทางเชอ่ื มต่อ 3 เสน้ จาก D ไป D มี 2 เส้นทาง คือ DBED และ DEBD เสน้ ทางเชอ่ื มต่อ 3 เสน้ จาก E ไป E มี 2 เสน้ ทาง คอื EBDE และ EDBE 6.4 การด้าเนนิ การบนกราฟ 6.4.1 การเพมิ่ 1. การเพิม่ โหนด คือ การเพิ่มโหนดเข้าไปในกราฟ โดยหลงั จากทีโ่ หนดได้ถกู เพม่ิ เข้า ไปในกราฟแล้ว โหนดน้ันจะยังไม่มีการเชอ่ื มตอ่ กับโหนดใด ๆ ดังภาพท่ี 6.11 AB AB CD CDE (a) ก่อนการเพมิ่ โหนด (b) หลังการเพิม่ โหนด ภาพท่ี 6.11 กอ่ นและหลงั การเพม่ิ โหนด เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอรทิ มึ

86 6.12 2. การเพ่ิมเส้นเช่ือมต่อ คือ การเพิ่มให้โหนดมีการเชื่อมต่อระหว่างกัน ดังภาพที่ A B AB CDE CDE (a) ก่อนการเพ่ิมเสน้ เชอื่ มต่อ (b) หลงั การเพิม่ เสน้ เช่ือมต่อ ภาพท่ี 6.12 กอ่ นและหลังการเพมิ่ เส้นเชอ่ื มต่อ 6.4.2 การลบ 1. การลบโหนด คือ การนาโหนดออกจากกราฟ ซ่ึงส่งผลให้ทุกเส้นท่ีเช่ือมต่อกับ โหนดนัน้ ถูกลบออกไปดว้ ย ดงั ภาพท่ี 6.13 AB AB CDE CDE (a) กอ่ นการลบโหนด (b) หลังการลบโหนด ภาพที่ 6.13 กอ่ นและหลังการลบโหนด 2. การลบเสน้ เชอ่ื มต่อ คอื การนาเสน้ เชอื่ มตอ่ ระหว่างโหนดออกไป ดังภาพที่ 6.14 AB AB CDE CDE (a) ก่อนการลบเสน้ เชอื่ มตอ่ (b) หลงั การลบเส้นเชื่อมต่อ ภาพท่ี 6.14 ก่อนและหลงั การลบเส้นเชอื่ มต่อ เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอรทิ ึม

87 6.5 การท่องไปในกราฟ การทอ่ งเข้าไปในกราฟมีรปู แบบ รูปแบบท่ีนยิ มใชม้ ี 2 รปู แบบ คอื 6.5.1 การท่องแบบแนวกวา้ ง (Breadth First Search : BFS) การท่องเข้าไปในกราฟแบบแนวกว้าง เป็นการท่องเข้าไปในกราฟโดยเข้าเย่ียมโหนดตัวแรก และดาเนนิ การ หากมีโหนดใกล้เคียงจะดาเนนิ การกับโหนดท่อี ย่ดู ้านซา้ ยก่อน ตัวอยา่ งที่ 6.9 จากภาพจงแสดงการท่องเขา้ ไปในกราฟแบบแนวกวา้ ง A BC D EF G H 1A 2B C3 D4 5E F G H 678 จากภาพการทอ่ งเขา้ ไปในกราฟแบบแนวกว้าง คือ ABCDEFGH 6.5.2 การทอ่ งแบบแนวลกึ (Depth First Search : DFS) การท่องเข้าไปในกราฟแบบแนวลึก เป็นลักษณะการท่องไปยังโหนดเริ่มต้น แล้วให้โหนด ใกล้เคียงเป็นโหนดเริ่มต้น เข้าเย่ียมโหนด ทาต่อไปจนไม่มีโหนดใกล้เคียงจึงย้อนกลับมายังโหนดก่อน หน้า และเขา้ เย่ียมโหนดอกี ด้านด้วยรูปแบบเดียวกันจนครบทุกโหนด เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมลู และอลั กอริทมึ

88 ตัวอยา่ งที่ 6.10 จากภาพจงแสดงการท่องเขา้ ไปในกราฟแบบแนวลึก A BC D EFG H 1A 2B C4 D6 3E F G H 578 จากภาพการท่องเข้าไปในกราฟแบบแนวกวา้ ง คือ ABECFDGH เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมูลและอลั กอรทิ มึ

89 ชือ่ หน่วยเรยี น : การเรยี งล้าดับขอ้ มูล (Sorting) รหสั วิชา 13-132-207 หน่วยเรียนที่ 7 เวลาสอน 12 คาบ ช่อื บทเรยี น 7.1 การจัดเรยี งข้อมลู แบบเลือก 7.2 การจดั เรยี งข้อมลู แบบบับเบลิ 7.3 การจดั เรยี งข้อมูลแบบแทรก 7.4 การจดั เรียงข้อมูลแบบเชลล์ 7.5 การจัดเรียงข้อมูลแบบฮีพ 7.6 การจัดเรียงข้อมูลแบบควกิ 7.7 การจดั เรยี งข้อมลู แบบผสาน จดุ ประสงคก์ ารสอน 7.1 รแู้ ละเข้าใจการจดั เรยี งข้อมลู แบบเลือก 7.1.1 อธบิ ายและยกตัวอยา่ งการจดั เรยี งข้อมลู แบบเลอื ก 7.1.2 แกไ้ ขปัญหาและหาผลลพั ธ์จดั เรยี งข้อมูลแบบเลอื ก 7.2 ร้แู ละเขา้ ใจการจดั เรียงข้อมูลแบบบับเบลิ 7.2.1 อธบิ ายและยกตวั อย่างการจัดเรียงข้อมูลแบบบบั เบิล 7.2.2 แกไ้ ขปญั หาและหาผลลพั ธ์การจัดเรยี งข้อมลู แบบบับเบิล 7.3 รู้และเขา้ ใจการจดั เรยี งข้อมูลแบบแทรก 7.3.1 อธบิ ายและยกตวั อย่างการจดั เรียงข้อมลู แบบแทรก 7.3.2 แก้ไขปญั หาและหาผลลัพธ์การจัดเรยี งขอ้ มลู แบบแทรก 7.4 รู้และเขา้ ใจการจดั เรยี งขอ้ มูลแบบเชลล์ 7.4.1 อธบิ ายและยกตัวอย่างการจดั เรียงข้อมลู แบบเชลล์ 7.4.2 แกไ้ ขปญั หาและหาผลลพั ธ์การจัดเรยี งขอ้ มลู แบบเชลล์ 7.5 รู้และเขา้ ใจการจัดเรยี งขอ้ มูลแบบฮีพ 7.5.1 อธบิ ายและยกตัวอยา่ งการจัดเรียงขอ้ มลู แบบฮีพ 7.5.2 แก้ไขปัญหาและหาผลลพั ธ์การจัดเรยี งข้อมูลแบบฮีพ 7.6 ร้แู ละเข้าใจการจัดเรียงข้อมูลแบบควกิ 7.6.1 อธิบายและยกตัวอย่างการจัดเรียงขอ้ มลู แบบควิก 7.6.2 แก้ไขปัญหาและหาผลลพั ธ์การจดั เรยี งข้อมลู แบบควกิ 7.7 รแู้ ละเขา้ ใจการจดั เรยี งขอ้ มูลแบบผสาน 7.7.1 อธบิ ายและยกตัวอย่างการจัดเรยี งขอ้ มลู แบบผสาน 7.6.2 แกไ้ ขปญั หาและหาผลลพั ธ์การจัดเรียงข้อมลู แบบผสาน เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอลั กอริทมึ

90 หน่วยเรยี นที่ 7 การเรียงล้าดบั ขอ้ มลู (Sorting) การเรียงลาดับข้อมูล (Sorting) คือ การจัดเรียงข้อมูลให้เรียงลาดับตามเงื่อนไขท่ีกาหนดไว้ โดยอาจเรียกจากคา่ นอ้ ยไปมาก หรือคา่ มากไปนอ้ ยกไ็ ด้ ประเภทของการจัดเรียงข้อมลู การจัดเรียงข้อมูลมีรูปแบบท่ีหลากหลาย จึงกาหนดการจัดเรียงข้อมูลออกเป็น 2 ประเภท คอื (วิวัฒน์ อภิสทิ ธ์ภิ ิญโญ และอมร มสุ ิกสาร. 2550 : 252) 1. การจัดเรียงข้อมูลภายใน (Internal Sorting) เป็นวิธีการท่ีจัดการเรียงข้อมูลภายใน หน่วยความจาหลกั ซึ่งการจัดเรยี งข้อมูลในหน่วยความจาหลักนีจ้ ะต้องมีการจดั เรียงให้มปี ระสิทธิภาพ มากท่ีสุด ดังน้ันจึงได้มีอัลกอริทึมที่หลากหลายเพื่อให้เลือกนาไปจัดเรียงกับข้อมูลในหน่วยความจา หลกั 2. การจัดเรียงข้อมูลภายนอก (External Sorting) วิธีการจัดเรียงข้อมูลภายนอกเป็นการ กาหนดการโอนย้ายข้อมูลจากหน่วยความจาหลัก ไปเก็บไว้ในหน่วยความจาสารอง เน่ืองจากข้อมูลมี มากจนไม่สามารถเก็บในหน่วยความจาหลักได้ท้ังหมด เช่น จานแม่เหล็ก (Magnetic disk) เทป แม่เหล็ก (Magnetic tape) โดยการวัดประสิทธิภาพของการจัดเรียงข้อมูลน้ันจะวัดจากเวลาท่ีใช้ใน การโอนย้ายข้อมูล สาหรับอัลกอริทมึ ที่จะนามาศกึ ษาในการจดั เรยี งข้อมูลนน้ั จะจดั แบ่งออกเปน็ 2 ลักษณะ คอื 1. อัลกอริทึมแบบเบ้ืองต้น (Simple) เป็นอัลกอริทึมของการจัดเรียงข้อมูลด้วยวิธีการท่ีเป็น เบ้ืองต้น เช่น การจัดเรียงข้อมูลแบบเลือก การจัดเรียงข้อมูลแบบบับเบิล และการจัดเรียงข้อมูลแบบ แทรก 2. อัลกอริทึมแบบข้ันสูง (Advance) เป็นอัลกอริทึมของการจัดเรียงข้อมูลท่ีใช้การจัดเรียง ข้อมูลที่รวดเร็วและมีประสิทธิภาพ เช่น การจัดเรียงข้อมูลแบบเชลล์ การจัดเรียงข้อมูลแบบผสาน การจดั เรยี งขอ้ มูลแบบฮพี และการจดั เรยี งข้อมูลแบบควกิ 7.1 การจัดเรียงข้อมลู แบบเลือก (Selection Sort) การจัดเรียงข้อมูลแบบเลือกเป็นอัลกอริทึมพื้นฐานที่สุดของการจัดเรียงข้อมูล โดยมีหลักการ ของการจัดเรียง คือ เลือกค่าข้อมูลท่ีน้อยหรือมากท่ีสุดอย่างใดอย่างหน่ึงในแต่ละฐานข้อมูลเป็นตัว หลัก จากน้ันนามาจัดเรียงแบบลาดับเลือกข้อมูลตัวต่อไปจนจัดเรียงเสร็จ โดยจานวนครั้งของการ จัดเรียงจะเท่ากับจานวนของข้อมูลที่นามาจัดเรียง การเรียงลาดับข้อมูลวิธีนี้จะเป็นวิธีที่ใช้งานมาก ที่สุด แตก่ ไ็ มเ่ หมาะสมสาหรบั ข้อมลู จานวนมาก เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอัลกอริทมึ

91 ตัวอยา่ งท่ี 7.1 กาหนดชุดข้อมูล 45 67 28 39 48 20 95 86 30 49 29 82 นามาจัดเรียงข้อมูล แบบเลือก โดยจดั ลาดับค่าตา่ สุดไปหาค่าสงู สุด ชดุ ขอ้ มูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 45 67 28 39 48 20 95 86 30 53 29 82 ครง้ั ท่ี 1 20 67 28 39 48 45 95 86 30 53 29 82 ครง้ั ที่ 2 20 28 67 39 48 45 95 86 30 53 29 82 ครง้ั ที่ 3 20 28 29 39 48 45 95 86 30 53 67 82 ครง้ั ที่ 4 20 28 29 30 48 45 95 86 39 53 67 82 ครั้งที่ 5 20 28 29 30 39 45 95 86 48 53 67 82 ครั้งท่ี 6 20 28 29 30 39 45 95 86 48 53 67 82 ครั้งท่ี 7 20 28 29 30 39 45 48 86 95 53 67 82 ครั้งที่ 8 20 28 29 30 39 45 48 53 95 86 67 82 ครงั้ ท่ี 9 20 28 29 30 39 45 48 53 67 86 95 82 ครงั้ ท่ี 10 20 28 29 30 39 45 48 53 67 82 95 86 ครง้ั ที่ 11 20 28 29 30 39 45 48 53 67 82 86 95 ครง้ั ท่ี 12 20 28 29 30 39 45 48 53 67 82 87 95 จากตัวอย่างท่ี 7.1 การจัดเรียงข้อมูลแบบเลือกของชุดข้อมูลทั้ง 12 ตัว ในแนวนอน ดาเนนิ การจดั เรยี ง โดยเลือกขอ้ มูลท่ีมีค่านอ้ ยท่สี ดุ นามาจดั เรยี งแบบลาดบั (เรม่ิ จาก 1,2,3,..,n) ครั้งท่ี 1 เลอื กขอ้ มลู ทน่ี ้อยลงมาเปน็ อันดบั ที่ 1 คือ 20 นาไปสลับกบั 45 ครั้งท่ี 2 เลือกข้อมลู ทนี่ อ้ ยลงมาเป็นอันดบั ท่ี 2 คือ 28 นาไปสลบั กบั 67 ครงั้ ท่ี 3 เลอื กขอ้ มูลท่นี อ้ ยลงมาเป็นอนั ดบั ที่ 3 คือ 29 นาไปสลบั กับ 67 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมลู และอลั กอริทมึ

92 ครง้ั ที่ 4 เลือกขอ้ มลู ทน่ี ้อยลงมาเป็นอนั ดับที่ 4 คอื 30 นาไปสลบั กบั 39 ครง้ั ที่ 5 เลือกขอ้ มูลท่ีนอ้ ยลงมาเปน็ อนั ดับที่ 5 คอื 39 นาไปสลบั กับ 48 คร้ังที่ 6 เลอื กข้อมูลท่ีนอ้ ยลงมาเป็นอนั ดบั ที่ 6 คอื 45 อยูใ่ นตาแหน่งเดมิ ครั้งที่ 7 เลือกข้อมลู ท่นี ้อยลงมาเป็นอนั ดบั ที่ 7 คอื 48 นาไปสลบั กับ 95 คร้ังท่ี 8 เลอื กขอ้ มลู ทน่ี ้อยลงมาเป็นอันดับที่ 8 คอื 53 นาไปสลับกบั 86 ครัง้ ที่ 9 เลือกข้อมูลท่ีน้อยลงมาเปน็ อนั ดับที่ 9 คอื 67 นาไปสลบั กบั 95 ครั้งที่ 10 เลือกขอ้ มูลท่ีนอ้ ยลงมาเปน็ อนั ดับที่ 10 คือ 82 นาไปสลับกบั 86 ครง้ั ท่ี 11 เลอื กขอ้ มลู ทน่ี ้อยลงมาเป็นอนั ดบั ที่ 11 คือ 86 นาไปสลับกบั 95 ครงั้ ท่ี 12 เลือกขอ้ มูลทนี่ ้อยลงมาเปน็ อนั ดบั ที่ 11 คอื 95 อยใู่ นตาแหน่งเดิม หลังจากจัดเรียงข้อมูลแบบเลือก โดยจัดลาดับค่าต่าสุดไปหาค่าสูงสุดการจัดเรียงข้อมูล ได้ ดงั น้ี ขอ้ มูลก่อน [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] การจัดเรียง 45 67 28 39 48 20 95 86 30 53 29 82 ข้อมลู หลงั 20 28 29 30 39 45 48 53 67 82 87 95 จากจัดเรยี ง ตวั อยา่ งที่ 7.2 กาหนดชุดข้อมูล 45 67 28 39 48 20 95 86 30 49 29 82 นามาจัดเรียงข้อมูล แบบเลือก โดยจัดลาดบั ค่าสูงสุดไปหาค่าตา่ สุด ชุดขอ้ มลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 45 67 28 39 48 20 95 86 30 53 29 82 คร้งั ท่ี 1 45 67 28 39 48 20 82 86 30 53 29 95 ครั้งท่ี 2 45 67 28 39 48 20 82 29 30 53 86 95 ครั้งท่ี 3 45 67 28 39 48 20 53 29 30 82 86 95 ครั้งที่ 4 45 30 28 39 48 20 53 29 67 82 86 95 ครง้ั ที่ 5 45 30 28 39 48 20 29 53 67 82 86 95 ครงั้ ท่ี 6 45 30 28 39 29 20 48 53 67 82 86 95 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มูลและอลั กอรทิ ึม

93 ครง้ั ที่ 7 20 30 28 39 29 45 48 53 67 82 86 95 ครั้งท่ี 8 20 30 28 29 39 45 48 53 67 82 86 95 ครัง้ ที่ 9 20 29 28 30 39 45 48 53 67 82 86 95 ครั้งท่ี 10 20 28 29 30 39 45 48 53 67 82 86 95 คร้ังท่ี 11 20 28 29 30 39 45 48 53 67 82 86 95 ครัง้ ที่ 12 20 28 29 30 39 45 48 53 67 82 86 95 จากตวั อยา่ งท่ี 7.2 การจัดเรียงขอ้ มูลแบบเลือกของชุดขอ้ มูลทง้ั 12 ตวั ในแนวนอน ดาเนินการ จัดเรยี ง โดยเลือกขอ้ มลู ที่มีค่ามากท่สี ุดนามาจดั เรียงแบบลาดบั (เริม่ จาก n,..,3,2,1) ครั้งที่ 1 เลอื กขอ้ มูลที่มากท่ีสดุ เปน็ อนั ดบั ท่ี 1 คือ 95 นาไปสลบั กบั 82 ครงั้ ที่ 2 เลือกขอ้ มลู ที่มากเป็นอันดับท่ี 2 คือ 86 นาไปสลบั กับ 29 ครง้ั ท่ี 3 เลือกข้อมูลทม่ี ากเปน็ อันดับที่ 3 คอื 82 นาไปสลับกบั 53 ครง้ั ท่ี 4 เลือกข้อมูลที่มากเปน็ อันดับที่ 4 คอื 67 นาไปสลบั กับ 30 ครง้ั ที่ 5 เลอื กข้อมลู ทม่ี ากเป็นอันดบั ท่ี 5 คือ 53 นาไปสลบั กับ 29 คร้งั ที่ 6 เลือกขอ้ มูลทมี่ ากเป็นอันดับที่ 6 คอื 48 นาไปสลบั กบั 29 ครั้งที่ 7 เลือกขอ้ มูลทีม่ ากเปน็ อันดบั ที่ 7 คอื 45 นาไปสลับกบั 20 คร้ังที่ 8 เลอื กข้อมูลท่มี ากเป็นอนั ดบั ท่ี 8 คือ 39 นาไปสลบั กับ 29 ครง้ั ที่ 9 เลอื กข้อมลู ทม่ี ากเปน็ อนั ดบั ที่ 9 คือ 30 นาไปสลบั กับ 29 ครง้ั ท่ี 10 เลือกข้อมูลทีม่ ากเปน็ อันดบั ท่ี 10 คอื 29 นาไปสลบั กับ 28 ครง้ั ท่ี 11 เลอื กขอ้ มลู ที่มากเป็นอันดบั ท่ี 11 คือ 28 อยูใ่ นตาแหน่งเดมิ คร้งั ท่ี 12 เลอื กข้อมูลทม่ี ากเป็นอันดับท่ี 12 คือ 20 อยู่ในตาแหนง่ เดิม หลังจากจัดเรียงข้อมูลแบบเลือก โดยจัดลาดับค่าสูงสุดไปหาค่าต่าสุดการจัดเรียงข้อมูล ได้ ดังนี้ ขอ้ มูลกอ่ น [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] การจัดเรียง 45 67 28 39 48 20 95 86 30 53 29 82 ข้อมลู หลงั 20 28 29 30 39 45 48 53 67 82 86 95 จากจัดเรยี ง เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอริทึม

94 7.2 การจัดเรียงข้อมูลแบบบบั เบิล (Bubble Sort) การจัดเรียงข้อมลู แบบบบั เบิลเป็นรปู แบบของการจัดเรยี งแบบแลกเปลี่ยน (Exchange Sort) เป็นลักษณะของการจดั เรียงจะใช้การเปรียบเทียบค่าใน 2 ตาแหนง่ ใกลเ้ คยี งกนั เรียงลาดบั การจัดจาก น้อยไปหามาก หรือจากมากไปหาน้อย จากน้ันจะสลับตาแหน่งกัน แล้วใช้ตาแหน่งที่ 2 เปรียบเทียบ กบั ตาแหน่งที่ 3 ไปจนถงึ ตาแหน่งที่ n จนเสร็จสิ้นการจดั เรยี ง ตวั อยา่ งที่ 7.3 กาหนดชุดข้อมูล 45 67 28 39 48 20 95 86 30 49 29 82 นามาจัดเรียงข้อมูล แบบบับเบลิ โดยจดั ลาดบั ค่าตา่ สุดไปหาคา่ สงู สุด รอบที่ 1 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดขอ้ มูล 45 67 28 39 48 20 95 86 30 53 29 82 ครง้ั ที่ 1 45 28 67 39 48 20 95 86 30 53 29 82 ครั้งท่ี 2 45 28 39 67 48 20 95 86 30 53 29 82 คร้ังท่ี 3 45 28 39 48 67 20 95 86 30 53 29 82 คร้งั ที่ 4 45 28 39 48 20 67 95 86 30 53 29 82 รอบที่ 1 ดาเนนิ การเปรยี บเทยี บ 4 คร้งั ดงั น้ี ครั้งที่ 1 เปรียบเทียบข้อมลู ตาแหนง่ ที่ 1,2 ขอ้ มูล 45<67 อยใู่ นตาแหน่งเดิม เปรียบเทียบข้อมูลตาแหน่งท่ี 2,3 ข้อมลู 67>28 สลบั ตาแหน่ง ครัง้ ที่ 2 เปรยี บเทียบขอ้ มลู ตาแหน่งท่ี 3,4 ขอ้ มลู 67>39 สลับตาแหน่ง ครั้งที่ 3 เปรยี บเทยี บข้อมูลตาแหนง่ ที่ 4,5 ขอ้ มลู 67>48 สลับตาแหนง่ ครง้ั ที่ 4 เปรียบเทยี บข้อมูลตาแหนง่ ท่ี 5,6 ข้อมลู 67>20 สลับตาแหนง่ รอบท่ี 2 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมูล 45 28 39 48 20 67 95 86 30 53 29 82 ครัง้ ที่ 1 28 45 39 48 20 67 95 86 30 53 29 82 ครั้งที่ 2 28 39 45 48 20 67 95 86 30 53 29 82 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอริทมึ

95 รอบท่ี 2 ดาเนินการเปรยี บเทยี บ 2 ครั้ง ดงั น้ี ครง้ั ท่ี 1 เปรียบเทยี บขอ้ มูลตาแหนง่ ท่ี 1,2 ข้อมลู 45>28 สลับตาแหน่ง ครง้ั ที่ 2 เปรยี บเทียบขอ้ มูลตาแหนง่ ที่ 2,3 ข้อมลู 45>39 สลบั ตาแหน่ง รอบท่ี 3 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดขอ้ มลู 28 39 45 48 20 67 95 86 30 53 29 82 คร้ังท่ี 1 28 39 45 20 48 67 95 86 30 53 29 82 รอบที่ 3 ดาเนินการเปรียบเทยี บ 1 ครัง้ ดังน้ี ครงั้ ท่ี 1 เปรียบเทียบขอ้ มลู ตาแหน่งท่ี 1,2 ขอ้ มลู 28<39 อย่ใู นตาแหน่งเดมิ เปรียบเทยี บข้อมูลตาแหน่งท่ี 2,3 ขอ้ มลู 39<45 อยู่ในตาแหนง่ เดิม เปรียบเทียบข้อมลู ตาแหน่งท่ี 3,4 ขอ้ มลู 45<48 อยู่ในตาแหน่งเดิม เปรียบเทียบข้อมลู ตาแหนง่ ท่ี 4,5 ขอ้ มูล 48>20 สลบั ตาแหนง่ รอบท่ี 4 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดข้อมูล 28 39 45 20 48 67 95 86 30 53 29 82 ครัง้ ท่ี 1 28 39 20 45 48 67 95 86 30 53 29 82 รอบท่ี 4 ดาเนินการเปรยี บเทยี บ 1 ครง้ั ดังนี้ ครัง้ ที่ 1 เปรยี บเทยี บขอ้ มูลตาแหนง่ ท่ี 1,2 ขอ้ มูล 28<39 อยใู่ นตาแหน่งเดิม เปรยี บเทยี บข้อมลู ตาแหนง่ ที่ 2,3 ข้อมลู 39<45 อยใู่ นตาแหนง่ เดิม เปรยี บเทยี บข้อมูลตาแหน่งท่ี 3,4 ขอ้ มลู 45>20 สลบั ตาแหนง่ รอบท่ี 5 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดข้อมูล 28 39 20 45 48 67 95 86 30 53 29 82 ครั้งท่ี 1 28 20 39 45 48 67 95 86 30 53 29 82 รอบท่ี 5 ดาเนนิ การเปรยี บเทียบ 1 ครงั้ ดังนี้ ครง้ั ท่ี 1 เปรียบเทยี บข้อมลู ตาแหนง่ ท่ี 1,2 ขอ้ มลู 28<39 อย่ใู นตาแหน่งเดิม เปรียบเทยี บข้อมลู ตาแหนง่ ท่ี 2,3 ขอ้ มลู 39>20 สลับตาแหน่ง เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอรทิ ึม

96 รอบท่ี 6 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดข้อมลู 28 20 39 45 48 67 95 86 30 53 29 82 คร้งั ท่ี 1 20 28 39 45 48 67 95 86 30 53 29 82 รอบที่ 6 ดาเนินการเปรียบเทยี บ 1 คร้งั ดังน้ี ครง้ั ท่ี 1 เปรยี บเทียบข้อมูลตาแหน่งที่ 1,2 ข้อมลู 28>20 สลับตาแหน่ง รอบท่ี 7 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดข้อมลู 20 28 39 45 48 67 95 86 30 53 29 82 ครง้ั ที่ 1 20 28 39 45 48 67 86 95 30 53 29 82 ครั้งที่ 2 20 28 39 45 48 67 86 30 95 53 29 82 ครัง้ ท่ี 3 20 28 39 45 48 67 86 30 53 95 29 82 คร้ังท่ี 4 20 28 39 45 48 67 86 30 53 29 95 82 ครั้งที่ 5 20 28 39 45 48 67 86 30 53 29 82 95 รอบที่ 7 ดาเนนิ การเปรยี บเทียบ 5 ครง้ั ดังน้ี ครง้ั ที่ 1 เปรยี บเทยี บขอ้ มูลตาแหน่งที่ 1,2 ขอ้ มลู 20<28 อย่ใู นตาแหน่งเดมิ เปรียบเทียบข้อมูลตาแหน่งที่ 2,3 ข้อมูล 28<39 อยใู่ นตาแหนง่ เดิม เปรยี บเทยี บข้อมลู ตาแหน่งท่ี 3,4 ข้อมูล 39<45 อยู่ในตาแหนง่ เดมิ เปรยี บเทยี บข้อมูลตาแหน่งที่ 4,5 ข้อมลู 45<48 อยู่ในตาแหนง่ เดิม เปรยี บเทียบข้อมูลตาแหนง่ ท่ี 5,6 ขอ้ มลู 48<67 อยู่ในตาแหน่งเดมิ เปรียบเทยี บข้อมูลตาแหนง่ ท่ี 6,7 ข้อมลู 67<95 อยู่ในตาแหนง่ เดิม เปรียบเทียบข้อมูลตาแหนง่ ที่ 7,8 ขอ้ มลู 95>86 สลบั ตาแหน่ง ครัง้ ที่ 2 เปรยี บเทียบข้อมลู ตาแหน่งที่ 8,9 ข้อมูล 95>30 สลบั ตาแหนง่ ครั้งที่ 3 เปรียบเทยี บข้อมลู ตาแหน่งที่ 9,10 ข้อมูล 95>53 สลบั ตาแหน่ง ครง้ั ที่ 4 เปรยี บเทียบข้อมลู ตาแหนง่ ที่ 10,11 ขอ้ มลู 95>29 สลับตาแหน่ง ครั้งที่ 5 เปรยี บเทียบข้อมลู ตาแหนง่ ที่ 11,12 ข้อมูล 95>82 สลับตาแหนง่ เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมูลและอลั กอรทิ ึม

97 รอบท่ี 8 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดข้อมลู 20 28 39 45 48 67 86 30 53 29 82 95 ครง้ั ท่ี 1 20 28 39 45 48 67 30 86 53 29 82 95 ครง้ั ท่ี 2 20 28 39 45 48 67 30 53 86 29 82 95 ครั้งที่ 3 20 28 39 45 48 67 30 53 29 86 82 95 คร้ังท่ี 4 20 28 39 45 48 67 30 53 29 82 86 95 รอบท่ี 8 ดาเนินการเปรยี บเทียบ 4 คร้งั ดังนี้ ครง้ั ท่ี 1 เปรยี บเทียบขอ้ มูลตาแหน่งที่ 1,2 ขอ้ มลู 20<28 อยู่ในตาแหน่งเดิม เปรยี บเทยี บข้อมลู ตาแหน่งท่ี 2,3 ขอ้ มลู 28<39 อยู่ในตาแหน่งเดิม เปรยี บเทยี บข้อมลู ตาแหนง่ ที่ 3,4 ข้อมูล 39<45 อยูใ่ นตาแหน่งเดมิ เปรยี บเทียบข้อมลู ตาแหน่งที่ 4,5 ขอ้ มลู 45<48 อยู่ในตาแหนง่ เดิม เปรียบเทยี บข้อมูลตาแหนง่ ที่ 5,6 ขอ้ มลู 48<67 อยู่ในตาแหน่งเดิม เปรียบเทียบข้อมลู ตาแหน่งที่ 6,7 ขอ้ มลู 67<86 อยู่ในตาแหนง่ เดมิ เปรียบเทยี บข้อมูลตาแหนง่ ที่ 7,8 ขอ้ มลู 86>30 สลบั ตาแหนง่ ครัง้ ท่ี 2 เปรยี บเทยี บข้อมูลตาแหน่งที่ 8,9 ขอ้ มูล 86>53 สลับตาแหน่ง ครัง้ ท่ี 3 เปรยี บเทยี บข้อมลู ตาแหน่งที่ 9,10 ข้อมลู 86>29 สลบั ตาแหน่ง ครง้ั ที่ 4 เปรียบเทยี บขอ้ มูลตาแหน่งที่ 10,11 ข้อมลู 86>82 สลับตาแหน่ง รอบท่ี 9 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมูล 20 28 39 45 48 67 30 53 29 82 86 95 ครง้ั ที่ 1 20 28 39 45 48 30 67 53 29 82 86 95 ครงั้ ท่ี 2 20 28 39 45 48 30 53 67 29 82 86 95 ครง้ั ที่ 3 20 28 39 45 48 30 53 29 67 82 86 95 รอบท่ี 9 ดาเนินการเปรียบเทียบ 3 ครั้ง ดงั นี้ ครั้งที่ 1 เปรยี บเทียบขอ้ มูลตาแหนง่ ท่ี 1,2 ข้อมลู 20<28 อย่ใู นตาแหน่งเดิม เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มูลและอลั กอริทมึ

98 เปรียบเทยี บข้อมลู ตาแหน่งท่ี 2,3 ข้อมูล 28<39 อยใู่ นตาแหน่งเดมิ เปรียบเทยี บข้อมูลตาแหน่งที่ 3,4 ขอ้ มูล 39<45 อยู่ในตาแหน่งเดิม เปรยี บเทียบข้อมูลตาแหน่งท่ี 4,5 ขอ้ มูล 45<48 อยู่ในตาแหนง่ เดมิ เปรียบเทยี บข้อมูลตาแหน่งท่ี 5,6 ขอ้ มูล 48<67 อยู่ในตาแหนง่ เดิม เปรยี บเทียบข้อมูลตาแหน่งที่ 6,7 ข้อมูล 67>30 สลบั ตาแหน่ง ครง้ั ที่ 2 เปรยี บเทยี บข้อมลู ตาแหน่งที่ 7,8 ข้อมูล 67>53 สลับตาแหน่ง ครั้งท่ี 3 เปรยี บเทียบข้อมลู ตาแหนง่ ที่ 8,9 ขอ้ มูล 67>29 สลบั ตาแหนง่ รอบที่ 10 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมลู 20 28 39 45 48 30 53 29 67 82 86 95 ครัง้ ท่ี 1 20 28 39 45 30 48 53 29 67 82 86 95 รอบที่ 10 ดาเนินการเปรียบเทยี บ 1 ครงั้ ดังน้ี คร้ังที่ 1 เปรียบเทียบข้อมลู ตาแหนง่ ที่ 1,2 ข้อมูล 20<28 อยู่ในตาแหน่งเดิม เปรยี บเทยี บข้อมูลตาแหน่งท่ี 2,3 ข้อมูล 28<39 อยู่ในตาแหนง่ เดมิ เปรยี บเทยี บข้อมลู ตาแหนง่ ที่ 3,4 ขอ้ มลู 39<45 อยใู่ นตาแหนง่ เดิม เปรียบเทยี บข้อมูลตาแหนง่ ที่ 4,5 ขอ้ มลู 45<48 อย่ใู นตาแหน่งเดิม เปรยี บเทยี บข้อมูลตาแหน่งท่ี 5,6 ขอ้ มลู 48>30 สลบั ตาแหน่ง รอบท่ี 11 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมลู 20 28 39 45 30 48 53 29 67 82 86 95 ครั้งท่ี 1 20 28 39 30 45 48 53 29 67 82 86 95 รอบที่ 11 ดาเนินการเปรยี บเทยี บ 1 ครัง้ ดงั นี้ คร้งั ท่ี 1 เปรยี บเทยี บขอ้ มลู ตาแหน่งท่ี 1,2 ขอ้ มลู 20<28 อยใู่ นตาแหน่งเดิม เปรยี บเทยี บข้อมลู ตาแหน่งท่ี 2,3 ขอ้ มลู 28<39 อยู่ในตาแหนง่ เดิม เปรยี บเทียบข้อมูลตาแหนง่ ท่ี 3,4 ขอ้ มูล 39<45 อยใู่ นตาแหน่งเดมิ เปรยี บเทียบข้อมูลตาแหน่งที่ 4,5 ขอ้ มลู 45>30 สลับตาแหน่ง เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมลู และอลั กอริทมึ

99 รอบท่ี 12 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมูล 20 28 39 30 45 48 53 29 67 82 86 95 ครั้งท่ี 1 20 28 30 39 45 48 53 29 67 82 86 95 รอบท่ี 12 ดาเนินการเปรียบเทยี บ 1 ครงั้ ดงั น้ี ครัง้ ที่ 1 เปรยี บเทียบขอ้ มลู ตาแหนง่ ท่ี 1,2 ขอ้ มูล 20<28 อยู่ในตาแหน่งเดมิ เปรยี บเทียบข้อมลู ตาแหนง่ ที่ 2,3 ขอ้ มลู 28<39 อยใู่ นตาแหน่งเดิม เปรยี บเทียบข้อมลู ตาแหนง่ ท่ี 3,4 ข้อมลู 39>30 สลับตาแหนง่ รอบท่ี 13 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ขอ้ มลู 20 28 30 39 45 48 53 29 67 82 86 95 ครั้งที่ 1 20 28 30 39 45 48 29 53 67 82 86 95 รอบที่ 13 ดาเนินการเปรียบเทียบ 1 ครง้ั ดังนี้ ครง้ั ที่ 1 เปรียบเทียบขอ้ มูลตาแหนง่ ที่ 1,2 ข้อมูล 20<28 อยใู่ นตาแหน่งเดมิ เปรยี บเทียบข้อมูลตาแหน่งที่ 2,3 ขอ้ มูล 28<30 อยู่ในตาแหนง่ เดมิ เปรียบเทียบข้อมลู ตาแหน่งท่ี 3,4 ข้อมลู 30<39 อยู่ในตาแหน่งเดมิ เปรยี บเทยี บข้อมลู ตาแหน่งท่ี 4,5 ขอ้ มูล 39<45 อยใู่ นตาแหนง่ เดมิ เปรียบเทียบข้อมูลตาแหนง่ ที่ 5,6 ขอ้ มูล 45<48 อยู่ในตาแหน่งเดมิ เปรียบเทยี บข้อมลู ตาแหน่งที่ 6,7 ขอ้ มลู 48<53 อยใู่ นตาแหน่งเดมิ เปรียบเทียบข้อมูลตาแหน่งที่ 7,8 ขอ้ มลู 53>29 สลบั ตาแหนง่ รอบท่ี 14 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ขอ้ มูล 20 28 30 39 45 48 29 53 67 82 86 95 ครงั้ ที่ 1 20 28 30 39 45 29 48 53 67 82 86 95 รอบที่ 14 ดาเนนิ การเปรียบเทยี บ 1 ครงั้ ดงั นี้ ครง้ั ท่ี 1 เปรยี บเทยี บขอ้ มูลตาแหน่งที่ 1,2 ข้อมลู 20<28 อย่ใู นตาแหน่งเดิม เปรียบเทียบข้อมูลตาแหนง่ ท่ี 2,3 ขอ้ มลู 28<30 อยู่ในตาแหน่งเดิม เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอัลกอรทิ มึ

100 เปรยี บเทียบข้อมลู ตาแหนง่ ท่ี 3,4 ขอ้ มูล 30<39 อยู่ในตาแหน่งเดิม เปรียบเทียบข้อมลู ตาแหนง่ ท่ี 4,5 ขอ้ มลู 39<45 อยู่ในตาแหนง่ เดิม เปรียบเทียบข้อมลู ตาแหนง่ ท่ี 5,6 ข้อมูล 45<48 อยู่ในตาแหนง่ เดิม เปรยี บเทียบข้อมูลตาแหนง่ ท่ี 6,7 ขอ้ มลู 48>29 สลับตาแหน่ง รอบท่ี 15 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ขอ้ มลู 20 28 30 39 45 29 48 53 67 82 86 95 ครัง้ ท่ี 1 20 28 30 39 29 45 48 53 67 82 86 95 รอบที่ 15 ดาเนนิ การเปรียบเทียบ 1 ครงั้ ดงั นี้ คร้ังที่ 1 เปรียบเทียบขอ้ มลู ตาแหนง่ ที่ 1,2 ข้อมูล 20<28 อยู่ในตาแหน่งเดมิ เปรยี บเทียบข้อมลู ตาแหน่งที่ 2,3 ข้อมลู 28<30 อยูใ่ นตาแหนง่ เดมิ เปรียบเทียบข้อมลู ตาแหน่งที่ 3,4 ขอ้ มูล 30<39 อยใู่ นตาแหน่งเดมิ เปรียบเทียบข้อมูลตาแหน่งที่ 4,5 ข้อมูล 39<45 อยู่ในตาแหน่งเดมิ เปรียบเทียบข้อมลู ตาแหนง่ ที่ 5,6 ขอ้ มลู 45>29 สลับตาแหน่ง รอบที่ 16 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมูล 20 28 30 39 29 45 48 53 67 82 86 95 ครงั้ ที่ 1 20 28 30 29 39 45 48 53 67 82 86 95 รอบท่ี 16 ดาเนนิ การเปรยี บเทียบ 1 ครัง้ ดงั นี้ ครั้งที่ 1 เปรยี บเทยี บขอ้ มลู ตาแหน่งที่ 1,2 ข้อมลู 20<28 อยู่ในตาแหน่งเดมิ เปรียบเทียบข้อมลู ตาแหน่งที่ 2,3 ข้อมูล 28<30 อยู่ในตาแหนง่ เดิม เปรยี บเทียบข้อมลู ตาแหนง่ ที่ 3,4 ข้อมลู 30<39 อยใู่ นตาแหน่งเดมิ เปรียบเทยี บข้อมูลตาแหน่งที่ 4,5 ขอ้ มลู 39>29 สลบั ตาแหน่ง เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอัลกอรทิ ึม

101 รอบที่ 17 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมลู 20 28 30 29 39 45 48 53 67 82 86 95 ครัง้ ท่ี 1 20 28 29 30 39 45 48 53 67 82 86 95 รอบที่ 17 ดาเนินการเปรียบเทยี บ 1 ครงั้ ดังนี้ ครัง้ ท่ี 1 เปรียบเทียบขอ้ มลู ตาแหน่งท่ี 1,2 ขอ้ มลู 20<28 อยู่ในตาแหน่งเดมิ เปรยี บเทียบข้อมูลตาแหน่งท่ี 2,3 ขอ้ มูล 28<30 อยู่ในตาแหน่งเดิม เปรียบเทยี บข้อมูลตาแหน่งท่ี 3,4 ขอ้ มูล 30>29 สลับตาแหน่ง หลังจากจัดเรียงข้อมูลแบบบับเบิล โดยจัดลาดับค่าต่าสุดไปหาค่าสูงสุดการจัดเรียง ข้อมลู ไดด้ งั นี้ ข้อมูลกอ่ น [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] การจัดเรียง 45 67 28 39 48 20 95 86 30 53 29 82 ขอ้ มูลหลงั 20 28 29 30 39 45 48 53 67 82 86 95 จากจัดเรยี ง 7.3 การจัดเรียงขอ้ มลู แบบแทรก (Insertion Sort) การเรียงข้อมูลแบบแทรกจะใช้หลักการของการจัดเรียงท่ีเป็นการกาหนดพื้นท่ีออกเป็น 2 ส่วน คอื 1. ส่วนข้อมูลที่มีการเรียงลาดับ (Sorted) คือ ข้อมูลในพ้ืนท่ีดาเนินการจัดเรียงลาดับ โดย สามารถจัดเรียงข้อมูลจากน้อยไปหามาก หรือจากมากไปหาน้อย และดาเนินการไปจนกว่าการ จัดเรยี งจะถูกตอ้ ง 2. ส่วนขอ้ มลู ทมี่ ียังไม่มกี ารเรียงลาดับ (Unsorted) คอื ขอ้ มลู ในพ้นื ทย่ี งั ไมจ่ ัดเรียงลาดับ ขอ้ มลู ที่มีการเรยี งลาดบั ข้อมูลท่ีมยี งั ไม่มีการเรยี งลาดับ ภาพที่ 7.1 การกาหนดพน้ื ที่ในการจดั เรยี งข้อมลู แบบแทรก จากภาพที่ 7.1 การแบ่งพ้ืนที่ในการจัดเรียงข้อมูลจะกาหนดพ้ืนท่ีส่วนหน้าเป็นพื้นท่ีจัดเรียง ข้อมูล พ้ืนที่ส่วนหลังใช้ในการเก็บข้อมูลท่ียังไม่ได้จัดเรียง หากนาข้อมูลมากจากพ้ืนที่ด้านหลังก็จะ นามาแทรกยังตาแหนง่ ท่ีถูกต้องด้านหน้า เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอริทมึ

102 ตัวอย่างที่ 7.4 กาหนดชุดข้อมูล 45 67 28 39 48 20 95 86 30 49 29 82 นามาจัดเรียงข้อมูล แบบแทรก โดยจดั ลาดบั คา่ ตา่ สดุ ไปหาค่าสงู สดุ ชดุ ข้อมลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 45 67 28 39 48 20 95 86 30 53 29 82 ครง้ั ที่ 1 45 67 28 39 48 20 95 86 30 53 29 82 ครั้งท่ี 2 45 67 28 39 48 20 95 86 30 53 29 82 ครง้ั ท่ี 3 28 45 67 39 48 20 95 86 30 53 29 82 ครั้งท่ี 4 28 39 45 67 48 20 95 86 30 53 29 82 ครั้งท่ี 5 28 39 45 48 67 20 95 86 30 53 29 82 ครง้ั ท่ี 6 20 28 39 45 48 67 95 86 30 53 29 82 ครง้ั ท่ี 7 20 28 39 45 48 67 95 86 30 53 29 82 ครั้งที่ 8 20 28 39 45 48 67 86 95 30 53 29 82 ครงั้ ที่ 9 20 28 30 39 45 48 67 86 95 53 29 82 ครง้ั ท่ี 10 20 28 30 39 45 48 53 67 86 95 29 82 ครั้งท่ี 11 20 28 29 30 39 45 48 53 67 86 95 82 ครง้ั ท่ี 12 20 28 29 30 39 45 48 53 67 82 86 95 คร้ังที่ 1 ข้อมูลพื้นที่จดั เรยี งตาแหนง่ ที่ 1 ขอ้ มลู 45 อยูใ่ นตาแหน่งเดิม ครง้ั ท่ี 2 ข้อมลู พื้นที่จัดเรยี งตาแหนง่ ที่ 1,2 ข้อมูล 45<67 อย่ใู นตาแหน่งเดิม ครง้ั ท่ี 3 ข้อมูลพื้นทีจ่ ัดเรียงตาแหนง่ ท่ี 1,2,3 ข้อมูล 28<45<67 แทรก 28 กอ่ น 45 คร้ังท่ี 4 ข้อมูลพื้นที่จัดเรียงตาแหน่งท่ี 1,2,3,4 ข้อมูล 28<39<45<67 แทรก 39 ระหว่าง 28 และ 45 เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอริทมึ

103 ครั้งที่ 5 ข้อมูลพื้นท่ีจัดเรียงตาแหน่งท่ี 1,2,3,4,5 ข้อมูล 28<39<45<48<67 แทรก 48 ระหว่าง 45 และ 67 คร้ังที่ 6 ข้อมูลพื้นท่ีจัดเรียงตาแหน่งที่ 1,2,3,4,5,6 ข้อมูล 20<28<39<45<48<67 แทรก 20 ก่อน 28 คร้ังที่ 7 ข้อมูลพื้นที่จัดเรียงตาแหน่งท่ี 1,2,3,4,5,6,7 ข้อมูล 20<28<39<45<48<67<95 แทรก 95 หลงั 67 ครัง้ ที่ 8 ข้อมูลพ้ืนที่จดั เรียงตาแหน่งที่ 1,2,3,4,5,6,7,8 ข้อมูล 20<28<39<45<48<67<86 <95 แทรก 86 ระหว่าง 67 และ 95 ครั้งที่ 9 ข้อมูลพ้ืนท่ีจัดเรียงตาแหน่งท่ี 1,2,3,4,5,6,7,8,9 ข้อมูล 20<28<30<39<45<48 <67<86<95 แทรก 30 ระหวา่ ง 28 และ 39 คร้ังที่ 10 ข้อมูลพื้นท่ีจัดเรียงตาแหน่งท่ี 1,2,3,4,5,6,7,8,9,10 ข้อมูล 20<28<30<39<45 <48<53<67<86<95 แทรก 53 ระหว่าง 48 และ 67 ครั้งที่ 11 ข้อมูลพ้ืนท่ีจัดเรียงตาแหน่งท่ี 1,2,3,4,5,6,7,8,9,10,11 ข้อมูล 20<28<29<30 <39<45<48<53<67<86<95 แทรก 29 ระหวา่ ง 28 และ 30 ครั้งที่ 12 ข้อมูลพ้ืนที่จดั เรียงตาแหน่งที่ 1,2,3,4,5,6,7,8,9,10,11,12 ข้อมลู 20<28<29<30 <39<45<48<53<67<82<86<95 แทรก 82 ระหวา่ ง 67 และ 86 หลังจากจัดเรียงข้อมูลแบบแทรก โดยจัดลาดับค่าต่าสุดไปหาค่าสูงสุดการจัดเรียงข้อมูล ได้ ดังน้ี ขอ้ มูลกอ่ น [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] การจดั เรียง 45 67 28 39 48 20 95 86 30 53 29 82 ขอ้ มลู หลงั 20 28 29 30 39 45 48 53 67 82 86 95 จากจดั เรยี ง 7.4 การจัดเรียงขอ้ มูลแบบเชลล์ (Shell Sort) เชลล์เป็นอัลกอริทึมท่ีมีประสิทธิภาพ ในด้านการค้นหาข้อมูลได้อย่างรวดเร็ว เมื่อข้อมูลนั้นมี จานวนมาก การดาเนินการจัดเรียงนั้นจะนาชุดข้อมูลซึ่งจัดเก็บเป็นรายการในอาร์เรย์ แบ่งชุดข้อมูล ออกเป็นเซกเมนต์ หรือกลุ่มข้อมูลเพ่ือเรียงในแต่ละเซกเมนต์ ด้วยวิธีการจัดเรียงแบบแทรกหรือ แบบบับเบ้ิล จากน้ันแบ่งเซกเมนต์ของชุดข้อมูลอีกโดยลดจานวนลงจนกระท่ังเซกเมนต์มีค่าเป็น 1 แล้วจัดเรียงขอ้ มลู อีกคร้ัง สาหรับการแบ่งเซกเมนต์น้ันจะทาการแบ่งโดยกาหนดค่าตัวแปร K เป็นระยะห่างของการ เลือกชุดข้อมูล ซึ่งแต่ละเซกเมนต์จะมีจานวนข้อมูลอยู่ประมาณ N/K ค่า โดยในแต่ละเท่ียวของการ จัดเรียงจานวนชุดข้อมูลในแต่ละเซกเมนต์อาจมีจานวนที่ไม่เท่ากัน โดยมีการกาหนดเลือกดังภาพที่ 7.2 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มูลและอลั กอริทึม

104 A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[1] A[1+K] A[1+2*K] A[1+3*K] 1 A[2] A[2+K] A[2+2*K] 2 A[3] A[3+K] A[3+2*K] 3 ภาพที่ 7.2 เซกเมนตใ์ นชดุ อารเ์ รย์ (ท่ีมา : ววิ ฒั น์ อภิสทิ ธิ์ภิญโญ และอมร มุสิกสาร. 2550 : 262) ตัวอย่างที่ 7.5 กาหนดชุดข้อมูลของอาร์เรย์ จานวน 12 ตัว คือ 45 67 28 39 48 20 95 86 30 49 29 82 นามาจัดเรียงข้อมูลแบบเชลล์ โดยกาหนดจานวนเท่ียวในการจัดเรียงค่า K=5, 3 และ 1 ครัง้ ที่ 1 กาหนดคา่ K=5 ชดุ ขอ้ มลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 45 67 28 39 48 20 95 86 30 53 29 82 เซกเมนต์ 1 45 20 29 เซกเมนต์ 2 67 95 82 เซกเมนต์ 3 28 86 เซกเมนต์ 4 39 30 เซกเมนต์ 5 48 53 เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอลั กอริทึม

105 คา่ หลงั จากการจดั เรยี งครัง้ ท่ี 1 ชุดขอ้ มลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 67 28 30 48 29 82 86 39 53 45 95 เซกเมนต์ 1 25 29 45 เซกเมนต์ 2 67 82 95 เซกเมนต์ 3 28 86 เซกเมนต์ 4 30 39 เซกเมนต์ 5 48 53 คร้ังที่ 2 กาหนดคา่ K=3 ชดุ ขอ้ มูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 67 28 30 48 29 82 86 39 53 45 95 เซกเมนต์ 1 20 30 82 53 เซกเมนต์ 2 67 48 86 45 เซกเมนต์ 3 28 29 39 95 ค่าหลงั จากการจัดเรยี งครง้ั ท่ี 2 ชุดขอ้ มลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 45 28 30 48 29 53 67 39 82 86 95 เซกเมนต์ 1 20 30 53 82 เซกเมนต์ 2 45 48 67 86 เซกเมนต์ 3 28 29 39 95 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมลู และอลั กอริทมึ

106 ครัง้ ท่ี 3 กาหนดคา่ K=1 ชุดข้อมลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 45 28 30 48 29 53 67 39 82 86 95 เซกเมนต์ 1 20 45 28 30 48 29 53 67 39 82 86 95 คา่ หลงั จากการจดั เรียงคร้ังท่ี 3 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดขอ้ มลู 20 28 29 30 39 45 48 53 67 82 86 95 เซกเมนต์ 1 20 28 29 30 39 45 48 53 67 82 86 95 7.5 การจัดเรียงขอ้ มลู แบบฮีพ (Heap Sort) การจดั เรียงแบบฮีพเป็นการจัดเรยี งโดยใช้โครงสร้างหลักของไบนารีทรี ซึ่งเป็นทรีทมี่ ีลักษณะ ของโครงสร้างสมบูรณ์หรือเกือบสมบูรณ์ การจัดเรียงภายในโหนดมีการปรับตาแหน่งข้อมูลภายใน โหนดกาหนดให้ข้อมูลท่ีมีค่ามากที่สุดอยู่ในตาแหน่งรูทโหนด สาหรับโหนดพ่อแม่ (K) จะมีค่าข้อมูล มากกวา่ โหนดลกู เช่นกัน 40 40 35 37 15 37 20 30 20 30 (a) (b) ภาพท่ี 7.3 โครงสรา้ งโครงสร้างแบบฮีพเทยี บกบั แบบไบนารีทรี จากภาพที่ 7.3 โครงสร้าง (a) ถือเป็นโครงสร้างแบบฮีพคือ มีข้อมูลสูงสุดอยู่ท่ีรูทโหนดและ ขอ้ มูลในโหนดลูกดา้ นซ้าย 35<40 และโหนดลูกของ 35 มีค่าน้อยกว่า 20 ,30 แต่ในโครงสร้าง (b) ไม่ ถอื เปน็ ฮพี เนอ่ื งจากโหนดลกู ของ 15 มีค่ามากกว่า 20,30 จึงไม่ถอื เปน็ โครงสรา้ งฮีพ การจัดเรียงข้อมลู แบบฮพี ตอ้ งดาเนนิ การ 3 ขนั้ ตอนดังนี้ 1. จดั ชุดข้อมูลจากอาร์เรย์ใหอ้ ยใู่ นโครงสร้างไบนารีทรี เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมูลและอัลกอรทิ ึม

107 2. จัดตามโครงสร้างฮีพ ค่าสูงสุดที่รูทโหนด ส่วนค่าของโหนดพ่อแม่จะมีค่ามากกว่าโหนดลูก ซ่ึงทาได้โดยการเล่ือนข้อมูลน้ันขึ้น (reheap up) และการเล่ือนข้อมูลลง (reheap down) จนกว่าจะ อยใู่ นตาแหน่งทีถ่ ูกต้อง 3. จดั เรยี งแบบฮพี เมอ่ื จัดโครงสร้างของฮพี เสรจ็ ดาเนินการต่อไปนี้ 3.1 นาคา่ ขอ้ มลู ที่อยใู่ นรูทโหนดไปสบั เปล่ยี นกับตาแหน่งท้ายสดุ (n) 3.2 สลบั ตาแหน่งรทู โหนดกับโหนดลกู ท่มี คี ่ามากกว่า 3.3 จดั ตาแหนง่ โหนดใหถ้ กู ตอ้ ง 3.4 สลบั ตาแหนง่ รูทโหนดกับโหนดท่ีตอ่ จากโหนดท่ีมีการสับเปลีย่ นจากดา้ นท้าย 3.5 ทาซ้า 3.2-3.4 จนกระทั่งไมส่ ามารถดาเนนิ การได้ ตวั อย่างท่ี 7.6 กาหนดชุดข้อมูลของอาร์เรย์ จานวน 12 ตัว คือ 45 67 28 39 48 20 95 86 30 49 29 82 นามาจัดเรียงข้อมลู แบบฮีพ นาขอ้ มลู มาจัดเรียงให้อยู่ในรูปแบบของอารเ์ รย์ ชุดข้อมูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 45 67 28 39 48 20 95 86 30 53 29 82 นาขอ้ มูลมาจดั เรยี งให้อยใู่ นรูปแบบของอาร์เรย์ไบนารีทรี ดงั ภาพที่ 7.4 45 67 28 39 48 20 95 86 30 53 29 82 ภาพท่ี 7.4 การจัดชดุ ขอ้ มูลอารเ์ รยล์ งโครงสรา้ งไบนารีทรี เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอลั กอริทึม

108 รอบที่ 1 จากภาพที่ 7.4 ดาเนนิ การการเล่ือนข้อมลู ในฮีพของค่าข้อมูล ดังนี้ คร้งั ที่ 1 เลือ่ น 45 ลงเปล่ยี นตาแหน่งกับ 67 45 67 28 39 48 20 95 86 30 53 29 82 ครง้ั ที่ 2 เล่ือน 45 ลงเปลย่ี นตาแหนง่ กับ 48 67 45 28 39 48 20 95 86 30 53 29 82 ครง้ั ที่ 3 เลื่อน 45 ลงเปล่ยี นตาแหนง่ กับ 53 67 48 28 39 45 20 95 86 30 53 29 82 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มูลและอัลกอรทิ มึ

109 ครั้งที่ 4 เลื่อน 48 ลงเปล่ียนตาแหน่งกับ 53 67 48 28 39 53 20 95 ครั้งท่ี 5 86 30 45 25 82 เล่ือน 39 ลงเปลย่ี นตาแหน่งกับ 86 67 53 28 39 48 20 95 86 30 45 25 82 ครั้งท่ี 6 เลอื่ น 53 ลงเปลีย่ นตาแหนง่ กับ 86 67 53 28 86 48 20 95 39 30 45 25 82 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอัลกอรทิ มึ

110 คร้งั ที่ 7 เลื่อน 67 ลงเปล่ียนตาแหน่งกับ 86 67 86 28 53 48 20 95 ครงั้ ท่ี 8 39 30 45 25 82 เลื่อน 95 ลงเปลย่ี นตาแหน่งกับ 28 86 67 28 53 48 20 95 39 30 45 25 82 ครั้งท่ี 9 เล่ือน 86 ลงเปลีย่ นตาแหนง่ กับ 95 86 67 95 53 48 20 28 39 30 45 25 82 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอรทิ มึ

111 คร้ังท่ี 10 เลอ่ื น 20 ลงเปลย่ี นตาแหน่งกับ 82 95 67 86 53 48 20 28 39 30 45 25 82 ได้ข้อมลู ตามโครงสร้างฮีพ จึงนาข้อมูลมาดาเนินการตามขั้นตอนของการจัดเรยี ง 95 67 86 53 48 82 28 39 30 45 25 20 ครง้ั ท่ี 11 สลับค่าข้อมลู โหนดแรกกับโหนดสุดทา้ ย ซ่ึงถือวา่ ข้อมลู ของโหนดสุดท้ายมีการ จัดเรยี งแลว้ คือ 95 กับ 20 95 67 86 53 48 82 28 39 30 45 25 20 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอลั กอริทมึ

112 ข้อมลู จัดเรยี ง รอบที่ 1 20 67 86 53 48 82 28 39 30 45 25 95 นาขอ้ มูลมาจัดเรยี งให้อยู่ในรูปแบบของอารเ์ รย์ได้ คือ ชุดขอ้ มลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 67 86 53 48 82 28 39 30 45 25 95 รอบท่ี 2 ดาเนินการการเลอื่ นข้อมลู ในฮีพของคา่ ข้อมลู ดังน้ี ครง้ั ท่ี 1 เลื่อน 20 ลงเปลีย่ นตาแหน่งกับ 86 20 67 86 53 48 82 28 39 30 45 25 95 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มูลและอลั กอรทิ มึ

113 ครง้ั ท่ี 2 เลื่อน 20 ลงเปลีย่ นตาแหน่งกับ 82 86 67 20 53 48 82 28 39 30 45 25 95 ครง้ั ที่ 3 สลบั ค่าขอ้ มูลโหนดแรกกับโหนดสุดทา้ ย คอื 86 กับ 25 86 67 82 53 48 20 28 ขอ้ ม3ลู 9จัดเรยี งร3อ0บที่ 425 25 95 25 67 82 53 48 20 28 39 30 45 86 95 นาข้อมลู มาจัดเรยี งให้อยูใ่ นรูปแบบของอาร์เรย์ได้ คือ เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอลั กอรทิ มึ

114 ชดุ ข้อมูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 25 67 82 53 48 20 28 39 30 45 86 95 รอบท่ี 3 ดาเนนิ การการเลือ่ นขอ้ มลู ในฮีพของคา่ ข้อมูล ดงั นี้ ครั้งที่ 1 เล่อื น 25 ลงเปล่ยี นตาแหน่งกับ 82 25 67 82 53 48 20 28 39 30 45 86 95 คร้ังที่ 2 เลือ่ น 25 ลงเปลยี่ นตาแหน่งกับ 28 82 67 25 53 48 20 28 39 30 45 86 95 เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอัลกอรทิ มึ

115 คร้งั ท่ี 3 สลับค่าขอ้ มูลโหนดแรกกับโหนดสดุ ทา้ ย คือ 82 กับ 45 82 67 28 53 48 20 25 39 30 45 86 95 ข้อมลู จัดเรียงรอบท่ี 3 45 67 28 53 48 20 25 39 30 82 86 95 นาขอ้ มลู มาจัดเรียงให้อยู่ในรูปแบบของอาร์เรย์ได้ คือ ชดุ ข้อมูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 45 67 28 53 48 20 25 39 30 82 86 95 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอัลกอริทมึ

116 รอบที่ 4 ดาเนนิ การการเลอื่ นข้อมลู ในฮีพของค่าข้อมูล ดงั นี้ ครงั้ ท่ี 1 เลือ่ น 45 ลงเปลย่ี นตาแหน่งกับ 67 45 67 28 53 48 20 25 39 30 82 86 95 ครง้ั ท่ี 2 เล่อื น 45 ลงเปลยี่ นตาแหน่งกับ 53 67 45 28 53 48 20 25 39 30 82 86 95 ครง้ั ท่ี 3 สลับค่าขอ้ มูลโหนดแรกกับโหนดสดุ ทา้ ย คือ 67 กบั 30 67 53 28 45 48 20 25 39 30 82 86 95 เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอัลกอรทิ มึ

117 ขอ้ มูลจัดเรียงรอบที่ 4 30 53 28 45 48 20 25 39 67 82 86 95 นาข้อมูลมาจัดเรียงให้อยู่ในรูปแบบของอาร์เรย์ได้ คือ ชุดข้อมูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 30 53 28 45 48 20 25 39 67 82 86 95 รอบท่ี 5 ดาเนินการการเลื่อนขอ้ มูลในฮีพของคา่ ข้อมลู ดงั น้ี ครัง้ ที่ 1 เลอื่ น 30 ลงเปล่ียนตาแหนง่ กับ 53 30 53 28 45 48 20 25 39 67 82 86 95 เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มูลและอลั กอริทึม

118 คร้ังที่ 2 เล่ือน 30 ลงเปลย่ี นตาแหน่งกับ 48 53 30 28 45 48 20 25 39 67 82 86 95 คร้งั ที่ 3 สลบั ค่าข้อมลู โหนดแรกกับโหนดสดุ ทา้ ย คือ 53 กบั 39 53 48 28 45 30 20 25 39 67 82 86 95 39 ข้อมูลจดั เรยี งรอบที่ 5 48 28 45 30 20 25 53 67 82 86 95 เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอริทมึ

119 นาขอ้ มูลมาจัดเรียงให้อยูใ่ นรูปแบบของอาร์เรย์ได้ คือ ชุดข้อมูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 39 48 28 45 30 20 25 53 67 82 86 95 รอบท่ี 6 ดาเนินการการเล่อื นข้อมูลในฮีพของคา่ ขอ้ มูล ดงั น้ี ครงั้ ท่ี 1 เลือ่ น 39 ลงเปลย่ี นตาแหนง่ กับ 48 39 48 28 45 30 20 25 53 67 82 86 95 ครัง้ ท่ี 2 เลื่อน 39 ลงเปลย่ี นตาแหน่งกับ 45 48 39 28 45 30 20 25 53 67 82 86 95 เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอัลกอริทึม

120 คร้งั ท่ี 3 สลับคา่ ข้อมูลโหนดแรกกับโหนดสุดทา้ ย คือ 48 กบั 25 48 45 28 39 30 20 25 53 67 82 86 95 ข้อมูลจดั เรยี งรอบที่ 6 25 45 28 39 30 20 48 53 67 82 86 95 นาข้อมูลมาจดั เรยี งให้อย่ใู นรูปแบบของอาร์เรย์ได้ คือ ชดุ ขอ้ มูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 25 45 28 39 30 20 48 53 67 82 86 95 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอริทมึ

121 รอบที่ 7 ดาเนินการการเล่อื นข้อมูลในฮีพของค่าขอ้ มลู ดังนี้ ครง้ั ที่ 1 เล่อื น 25 ลงเปลยี่ นตาแหนง่ กับ 45 25 45 28 39 30 20 48 53 67 82 86 95 ครั้งท่ี 2 เลื่อน 25 ลงเปล่ียนตาแหนง่ กับ 39 45 25 28 39 30 20 48 53 67 82 86 95 ครั้งที่ 3 สลับค่าข้อมูลโหนดแรกกบั โหนดสุดทา้ ย คือ 45 กับ 20 45 39 28 25 30 20 48 53 67 82 86 95 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มูลและอลั กอรทิ มึ

122 ข้อมูลจดั เรียงรอบท่ี 7 20 39 28 25 30 45 48 53 67 82 86 95 นาขอ้ มูลมาจัดเรียงให้อย่ใู นรูปแบบของอาร์เรย์ได้ คือ ชุดข้อมูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 39 28 25 30 45 48 53 67 82 86 95 รอบที่ 8 ดาเนินการการเล่อื นขอ้ มูลในฮีพของคา่ ขอ้ มูล ดงั นี้ ครง้ั ท่ี 1 เลือ่ น 20 ลงเปล่ียนตาแหน่งกับ 39 20 39 28 25 30 45 48 53 67 82 86 95 เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอริทมึ

123 ครัง้ ที่ 2 เลื่อน 20 ลงเปล่ียนตาแหน่งกับ 30 39 20 28 25 30 45 48 53 67 82 86 95 ครั้งท่ี 3 สลับค่าข้อมูลโหนดแรกกบั โหนดสุดท้าย คอื 39 กบั 20 39 30 28 25 20 45 48 53 67 82 86 95 20 ข้อมูลจดั เรยี งรอบท่ี 8 30 28 25 39 45 48 53 67 82 86 95 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมลู และอลั กอริทมึ

124 นาขอ้ มลู มาจัดเรียงให้อยูใ่ นรูปแบบของอาร์เรย์ได้ คือ ชุดขอ้ มลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 30 28 25 39 45 48 53 67 82 86 95 รอบที่ 9 ดาเนนิ การการเลอ่ื นข้อมลู ในฮีพของคา่ ข้อมูล ดงั นี้ ครั้งที่ 1 เลื่อน 20 ลงเปลย่ี นตาแหนง่ กับ 30 20 30 28 25 39 45 48 53 67 82 86 95 คร้ังที่ 2 เลื่อน 20 ลงเปลยี่ นตาแหน่งกับ 25 30 20 28 25 39 45 48 53 67 82 86 95 เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มูลและอลั กอรทิ ึม

125 คร้ังท่ี 3 สลับคา่ ข้อมลู โหนดแรกกับโหนดสุดทา้ ย คอื 30 กับ 20 30 25 28 20 39 45 48 53 67 82 86 95 20 ขอ้ มลู จดั เรยี งรอบที่ 9 25 28 30 39 45 48 53 67 82 86 95 นาข้อมูลมาจัดเรียงให้อยูใ่ นรูปแบบของอาร์เรย์ได้ คือ ชุดขอ้ มูล [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 25 28 30 39 45 48 53 67 82 86 95 เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอัลกอรทิ มึ

126 รอบที่ 10 ดาเนนิ การการเลื่อนข้อมูลในฮีพของคา่ ขอ้ มลู ดงั นี้ คร้งั ท่ี 1 เล่ือน 20 ลงเปล่ยี นตาแหน่งกับ 28 20 25 28 30 39 45 48 53 67 82 86 95 ครัง้ ท่ี 2 สลบั ค่าขอ้ มลู โหนดแรกกับโหนดสดุ ท้าย คือ 28 กบั 20 28 25 20 30 39 45 48 53 67 82 86 95 ข้อมูลจัดเรยี งรอบท่ี 10 20 25 28 30 39 45 48 53 67 82 86 95 เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอรทิ ึม

127 นาข้อมูลมาจัดเรียงให้อยู่ในรูปแบบของอารเ์ รย์ได้ คือ ชดุ ข้อมลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 25 28 30 39 45 48 53 67 82 86 95 รอบท่ี 11 ดาเนินการการเลื่อนข้อมูลในฮีพของคา่ ข้อมลู ดงั นี้ ครัง้ ที่ 1 เลื่อน 20 ลงเปล่ียนตาแหน่งกับ 25 20 25 28 30 39 45 48 53 67 82 86 95 ครง้ั ท่ี 2 สลบั คา่ ขอ้ มลู โหนดแรกกับโหนดสุดท้าย คอื 25 กบั 20 25 20 28 30 39 45 48 53 67 82 86 95 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอรทิ มึ

128 ข้อมูลจดั เรียงรอบท่ี 11 20 25 28 30 39 45 48 53 67 82 86 95 นาขอ้ มูลมาจดั เรียงให้อยใู่ นรูปแบบของอาร์เรย์ได้ คือ ชดุ ขอ้ มลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 25 28 30 39 45 48 53 67 82 86 95 รอบท่ี 12 ดาเนนิ การการเลื่อนขอ้ มลู ในฮีพของค่าขอ้ มูล ดงั นี้ ครง้ั ที่ 1 เปลี่ยน 20 เป็นค่าทจี่ ดั เรยี งได้ เนือ่ งจากเป็นค่าสุดทา้ ย 20 25 28 30 39 45 48 53 67 82 86 95 โครงสร้างฮีพเมอ่ื จัดเรยี บร้อย เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอลั กอริทึม

129 20 25 28 30 39 45 48 53 67 82 86 95 หลังจากจดั เรียงข้อมลู แบบฮพี ไดข้ ้อมลู ดังน้ี ข้อมลู ก่อน [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] การจดั เรียง 45 67 28 39 48 20 95 86 30 53 29 82 ขอ้ มูลหลงั 20 25 28 30 39 45 48 53 67 82 86 95 จากจดั เรียง 7.6 การจัดเรยี งข้อมลู แบบควิก (Quick Sort) การจัดเรียงข้อมูลแบบเร็ว คือ การเปรียบเทียบค่าและจัดเรียงข้อมูล แต่ได้เพิ่มประสิทธิภาพ ของการจัดเรียงด้วยการแบ่งครึ่งข้อมูลเทียบกับค่าข้อมูล (pivot) ท่ีกาหนดในชุดข้อมูล ทาให้ได้กลุ่ม ข้อมูล 3 กลุม่ คอื 1. กลมุ่ ชุดข้อมูลที่น้อยกว่าค่าข้อมลู ท่ีเลอื ก (keys < pivot) 2. ค่าขอ้ มลู ที่เลอื ก (pivot) 3. กลุม่ ข้อมูลทีม่ ีคา่ ข้อมลู มากกวา่ หรือเท่ากบั คา่ ข้อมลู ทเี่ ลือก (keys >= pivot) จากน้ันจัดเรียงข้อมูลแบบควิกในชุดข้อมูลด้านซ้ายเรียบร้อยก่อนแล้วตามด้วยการจัดเรียง ข้อมูลดา้ นขวา แสดงวิธกี ารจดั เรียง [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ครง้ั ท่ี 1 keys<pivot pivot key>=pivot ครั้งท่ี 2 keys<pivot Pivot key>=pivot เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอลั กอรทิ มึ

130 ครงั้ ที่ 3 จัดเรยี งขอ้ มูล pivot ครง้ั ที่ 4 จัดเรยี งข้อมลู ครงั้ ท่ี 5 จดั เรยี งขอ้ มลู keys<pivot pivot key>=pivot ครง้ั ที่ 6 จดั เรยี งขอ้ มลู ครัง้ ที่ 7 จดั เรยี งขอ้ มลู ภาพท่ี 7.5 รูปแบบการจดั เรียงข้อมลู แบบควิก สาหรับการเลือกค่าข้อมูลท่ีใช้ในการแบ่งชุดข้อมูลเพื่อจัดเรียงนั้น จะพิจารณาจากชุดข้อมูล โดยนาตาแหน่งแรกของชุดข้อมูล + ตาแหน่งสุดท้าย หารด้วย 2= (First + Last) Div 2 ซึ่งค่าที่ได้ก็ คือ ค่าก่ึงกลางของข้อมูล จากน้ันกาหนดเปรียบเทียบโดยใช้ค่าตัวเลือกเป็นหลัก กาหนดอินเด็กซ์ ด้านซ้าย (Up Counter) และด้านขวา (Down Counter) หากค่าด้านซ้ายมากกว่าค่าตัวเลือกระบุค่า เป็น Up Counter และหาค่าท่ผี ดิ ตาแหน่งทางด้านขวาระบุเปน็ Down Counter สลบั ตาแหน่งกันไป จนกว่าจะจัดเรียงในชุดข้อมูลจบ จากน้ันวนซ้าการทางานในชดุ ข้อมลู ด้านซา้ ยแบบเดมิ และมาทางาน ทชี่ ดุ ขอ้ มลู ด้านขวา ตัวอย่างที่ 7.7 กาหนดชุดข้อมูลของอาร์เรย์ จานวน 12 ตัว คือ 45 67 28 39 48 20 95 86 30 49 29 82 นามาจดั เรยี งข้อมูลแบบควกิ ตาแหน่ง [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ขอ้ มูล 45 67 28 39 48 20 95 86 30 53 29 82 คร้งั ที่ 1 หาคา่ ก่งึ กลางเพือ่ ใช้ในการแบ่งชุดขอ้ มูล = (1+12) Div 2 = 6 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 45 67 28 39 48 20 95 86 30 53 29 82 ขอ้ มูลดา้ นซ้าย Pivot ข้อมูลดา้ นขวา ชุดข้อมูลในตาแหน่งท่ี 6 คือ 20 จะเป็นค่ากาหนดในการแบ่งข้อมูล ออกเป็น 2 กลุ่ม เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอัลกอริทึม

131 คอื ข้อมูลด้านซา้ ย pivot และขอ้ มลู ดา้ นขวา โดยดาเนินการตรวจสอบคอื - ตรวจสอบคา่ ดา้ นขวา 20 มากกว่า 20 จงึ ไมส่ ลับ - ตรวจสอบคา่ ดา้ นซา้ ย 45 มากกวา่ 20 จงึ สลบั ตาแหนง่ 20 และ 45 หลังจากจดั เรียงคร้งั ท่ี 1 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 67 28 39 48 45 95 86 30 53 29 82 ตาแหน่ง [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดขอ้ มลู 20 67 28 39 48 45 95 86 30 53 29 82 คร้ังที่ 2 หาค่าก่งึ กลางเพ่ือใชใ้ นการแบ่งชุดขอ้ มลู = (2+12) Div 2 = 7 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 67 28 39 48 45 95 86 30 53 29 82 pivot ชดุ ข้อมลู ในตาแหน่งที่ 7 คือ 95 และดาเนินการตรวจสอบคอื - ตรวจสอบคา่ ดา้ นซ้าย 95 นอ้ ยกวา่ 95 จงึ ไมส่ ลบั - ตรวจสอบค่าดา้ นขวา 95 น้อยกวา่ 95 จึงสลบั ตาแหนง่ 95 และ 82 หลังจากจดั เรียงครง้ั ท่ี 2 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 67 28 39 48 45 82 86 30 53 29 95 ตาแหน่ง [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมลู 20 67 28 39 48 45 82 86 30 53 29 95 คร้งั ที่ 3 หาค่ากงึ่ กลางเพือ่ ใชใ้ นการแบ่งชุดข้อมลู = (2+11) Div 2 = 6 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 67 28 39 48 45 82 86 30 53 29 pivot ชุดขอ้ มลู ในตาแหนง่ ที่ 6 คอื 45 และดาเนนิ การตรวจสอบคอื - ตรวจสอบค่าด้านซา้ ย 67 มากกวา่ 45 จึงสลับตาแหน่ง 67 และ 29 - ตรวจสอบคา่ ดา้ นซ้าย 48 มากกวา่ 45 จงึ สลับตาแหน่ง 48 และ 30 หลงั จากจัดเรียงครั้งที่ 3 เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอัลกอรทิ มึ

132 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 29 28 39 30 45 82 86 48 53 67 ตาแหน่ง [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ขอ้ มูล 20 29 28 39 30 45 82 86 48 53 67 95 ครั้งท่ี 4 หาค่ากงึ่ กลางเพือ่ ใชใ้ นการแบ่งชุดข้อมลู = (2+5) Div 2 = 3 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 29 28 39 30 pivot ชุดข้อมูลในตาแหน่งที่ 3 คือ 28 และดาเนนิ การตรวจสอบคอื - ตรวจสอบคา่ ดา้ นซ้าย 29 มากกว่า 28 จงึ สลบั ตาแหน่ง 28 และ 29 หลังจากจัดเรยี งครงั้ ที่ 4 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 28 29 39 30 ตาแหนง่ [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดข้อมลู 20 28 29 39 30 45 82 86 48 53 67 95 ครง้ั ที่ 5 หาคา่ ก่ึงกลางเพื่อใชใ้ นการแบ่งชุดข้อมูล = (3+5) Div 2 = 4 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 29 39 30 Pivot ชดุ ขอ้ มลู ในตาแหนง่ ท่ี 4 คอื 39 และดาเนินการตรวจสอบคือ - ตรวจสอบค่าดา้ นขวา 30 นอ้ ยกว่า 39 จึงสลบั ตาแหน่ง 39 และ 30 - และจะไดค้ า่ 29 และ 30 ท่ีจัดเรียงแล้ว หลงั จากจดั เรยี งคร้ังที่ 5 ตาแหนง่ [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ขอ้ มลู 29 30 39 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 20 28 29 30 39 45 82 86 48 53 67 95 เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอรทิ ึม

133 ครั้งที่ 6 หาคา่ กง่ึ กลางเพอื่ ใชใ้ นการแบ่งชุดขอ้ มลู = (7+11) Div 2 = 9 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 82 86 48 53 67 pivot ชุดข้อมูลในตาแหนง่ ท่ี 9 คอื 48 และดาเนินการตรวจสอบคือ - ตรวจสอบคา่ ด้านซา้ ย 82 มากกวา่ 48 จงึ สลับตาแหนง่ 48 และ 82 หลังจากจัดเรยี งครัง้ ที่ 6 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 48 86 82 53 67 ตาแหนง่ [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชุดขอ้ มลู 20 28 29 30 39 45 48 86 82 53 67 95 ครั้งท่ี 7 หาค่ากง่ึ กลางเพ่ือใช้ในการแบ่งชุดข้อมูล = (8+11) Div 2 = 9 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 86 82 53 67 Pivot ชดุ ข้อมูลในตาแหน่งที่ 9 คือ 48 และดาเนินการตรวจสอบคอื - ตรวจสอบค่าด้านซา้ ย 86 มากกวา่ 82 จึงสลับตาแหน่ง 86 และ 67 - ตรวจสอบคา่ ด้านขวา 53 นอ้ ยกวา่ 82 จึงสลับตาแหนง่ 82 และ 53 หลงั จากจัดเรยี งครงั้ ที่ 7 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 67 53 82 86 ตาแหนง่ [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมลู 20 28 29 30 39 45 48 67 53 82 86 95 ครงั้ ท่ี 8 หาค่ากง่ึ กลางเพอ่ื ใช้ในการแบ่งชุดข้อมลู = (8+9) Div 2 = 8 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 67 53 Pivot เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอัลกอรทิ มึ

134 ชุดขอ้ มลู ในตาแหนง่ ที่ 8 คือ 67 และดาเนนิ การตรวจสอบคือ - ตรวจสอบค่าดา้ นขวา 53 นอ้ ยกวา่ 67 จงึ สลับตาแหนง่ 67 และ 53 หลงั จากจัดเรียงคร้ังท่ี 8 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 53 67 ตาแหนง่ [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมูล 20 28 29 30 39 45 48 53 67 82 86 95 หลังจากจัดเรยี งข้อมลู แบบควกิ ไดข้ ้อมลู ดงั นี้ ข้อมลู ก่อน [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] การจดั เรยี ง 45 67 28 39 48 20 95 86 30 53 29 82 ข้อมูลหลัง 20 28 29 30 39 45 48 53 67 82 86 95 จากจัดเรยี ง 7.7 การจดั เรียงขอ้ มูลแบบผสาน (Merge Sort) การจัดเรียงข้อมูลแบบผสาน เป็นอีกอัลกอริทึมที่ใช้ในการจัดเรียงข้อมูล แต่จะใช้ในการ จัดเรียงข้อมูลภายนอก คือ ข้อมูลท่ีเก็บอยู่ในหน่วยความจาสารอง เช่น ดิสก์ เทปแม่เหล็ก สาหรับ อลั กอริทึมของการดาเนินการจัดเรียงข้อมูลแบบผสานนั้นมีหลกั การคือ ทาการจับคู่ข้อมูลภายชุดโดน แต่ละคู่จะทาการจัดเรียงไปในคู่ของตัวเอง จากน้ันจึงผสานกับคู่ใกล้เคียงจัดเรียงค่าดาเนินการต่อไป จนกว่าจะได้การผสานในคสู่ ดุ ท้ายของชุดข้อมูลซ่งึ เป็นชดุ ขอ้ มูลทม่ี กี ารจัดเรยี งเรยี บร้อย ตัวอย่างท่ี 7.8 กาหนดชุดข้อมูลของอาร์เรย์ จานวน 12 ตัว คือ 45 67 28 39 48 20 95 86 30 49 29 82 นามาจดั เรียงข้อมลู แบบผสาน ตาแหนง่ [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ขอ้ มลู 45 67 28 39 48 20 95 86 30 53 29 82 เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอัลกอรทิ ึม