พบคลิ๊ปที่ใช้อธิบาย Algorithm เรื่อง Heap Sort โดย CHUA, PATRICIA G. & MAGSINO, ALBERT ROQUE G.

ว่ากันด้วยเรื่องโครงสร้างข้อมูล (Data Structure) ครับวันนี้
พบว่ามีหัวข้อน่าสนใจมากมาย หนึ่งในเรื่องการจัดเรียง (Sorting) คือ Heap Sort
เป็นการจัดเรียงที่ยากจะเขียนให้เข้าใจด้วยตารางเป็นช่อง ๆ
เพราะหลักการเป็นการใช้ Binary Tree หรือ Tree แบบ Heap
ถูกนำมาช่วยกำหนดแนวคิดการเคลื่อนย้ายข้อมูล เพื่อการจัดเรียง

ภาพนี้แสดงว่า 4 ถูกแทนด้วย 8 และ 8 จะถูกแทนด้วย 4  แนวนั้น
ภาพนี้แสดงว่า 4 ถูกแทนด้วย 8 และ 8 จะถูกแทนด้วย 4 แนวนั้น

นั่งดูคลิ๊ปของนักวิชาการมาหลายท่านแล้ว
พบว่าคลิ๊ปของ CHUA, PATRICIA G. & MAGSINO, ALBERT ROQUE G.
วิชา CS141 – AC1
อธิบายการจัดเรียงข้อมูลแบบ Heap Sort ได้ดีมาก
แบ่งการอธิบายเป็น 2 รอบ
รอบแรก เล่าให้เห็นภาพการทำงานของ Heap Sort
รอบสอง เล่าพร้อมกับการอธิบายอัลกอริทึม

เทคนิคที่ใช้ คือ
การแสดงซอร์ทโค้ด แล้วแสดงผลลัพธ์ของตัวแปรที่เกี่ยวข้อง
ในแต่ละบรรทัด ผ่านตารางค่าตัวแปร
ไปพร้อมกับภาพการเคลื่อนข้อมูลในอาร์เรย์ (Array)
และเปลี่ยนโครงสร้าง Heap Tree ไปพร้อมกัน

ใช้อาร์เรย์เก็บข้อมูล เพื่อตอบตาม index

function to create array
function to create array

อ่านแฟ้มแบบตัวอักษรมาเก็บในอาร์เรย์ เพื่อใช้ตอบการร้องขอข้อมูลตาม index

กรณีแรก ..
ในทางทฤษฎีเราใช้ระบบฐานข้อมูลสำหรับเก็บข้อมูล และใช้คำสั่ง SQL ที่เรียกว่า query ด้วยคำสั่ง select ถามหาข้อมูลที่ต้องการ ซึ่งมีประสิทธิภาพทำงานได้อย่างรวดเร็ว สมเป็นมืออาชีพ แต่ในทางปฏิบัติอาจไม่เป็นเช่นนั้นเสมอไป
เช่น กองฉลากเคยเก็บข้อมูลในระบบฐานข้อมูล ชาวไทยต้องการตรวจผลรางวัลก็กรอกข้อมูลแล้วระบบก็ส่ง query เข้าไปสอบถามจากเครื่องบริการ เป็นเช่นนี้อยู่ระยะหนึ่ง ต่อมาเห็น sanook.com ให้บริการตรวจฉลากกินแบ่ง โดยนำข้อมูลตัวเลขมาเก็บในแฟ้ม html แล้วใช้ javascript เป็นตัวตอบคำถาม ภาระในการสืบค้นการถูกรางวัลกลายเป็นของ script + browser ฝั่งผู้ใช้ ที่ทำงานได้รวดเร็วที่สุดในโลก
ปัจจุบันกองฉลากก็ใช้เทคนิค javascript ทำให้ตรวจฉลากหลายสิบใบได้เร็วมาก เพราะทั้งหมดแทบจะทำงานที่ฝั่งผู้ใช้ ยกเว้นการเปิดเว็บไซต์ในครั้งแรก เพื่อร้องขอการดาวน์โหลดข้อมูลมาไว้ในเครื่องผู้ใช้ที่เกิดขึ้นในครั้งแรก

กรณีที่สอง ..
ข้อมูลปริมาณมาก ย่อมต้องใช้ระบบฐานข้อมูล เพราะมีระบบบริหารจัดการ และค้นคืนได้อย่างมีประสิทธิภาพ แต่ถ้ามีข้อมูลไม่กี่สิบระเบียน ก็ไม่จำเป็นต้องใช้งานระบบฐานข้อมูล เพราะระบบฐานข้อมูลนั้นจำเป็นต้องมีโปรแกรมทำงานที่หลากหลาย แต่ถ้าเก็บข้อมูลในอาร์เรย์ หรือเก็บใน text file แล้วอ่านมาไว้ในอาร์เรย์ ก็จะทำให้เรียกใช้ข้อมูลได้ง่าย และเร็ว เหมือนการทำงานของ cache หรือ ram หรือ harddisk ที่ทำงานได้เร็วกว่า external harddisk สำหรับตัวอย่างนี้ มีข้อมูลใน text file แล้วอ่านมาเก็บใน array โดยกำหนด index ให้แต่ละสมาชิก เมื่อต้องการข้อมูลก็เรียกสมาชิกตาม index ได้ทันที ซึ่งประมวลผลได้เร็ว และไม่เป็นภาระกับระบบฐานข้อมูล โดยฟังก์ชันเขียนให้รองรับการคืนค่าของสมาชิก เช่น ชื่อ-สกุล หรือ ชื่อ-ชื่อกลาง-สกุล หรือ ชื่ออย่างเดียว เมื่อส่งรหัสเข้าไปเรียกจากอาร์เรย์

Source code
$ar_advisor = array();
$ar_advisor = create_ar_advisor(“advisor”,”0″,”1-2″);
echo $ar_advisor[“5601”];
function create_ar_advisor($filename,$f_key,$f_val) {
$ar = array();
$fileaddr = “/data/”. $filename . “.csv”;
$fn = file($fileaddr);
$get_k = split(“-“,”$f_key”);
$get_v = split(“-“,”$f_val”);
foreach($fn as $v) {
$r = split(“\t”,”$v”);
$rk = “”; $rv = “”;
foreach($get_k as $kv) $rk .= $r[intval($kv,10)];
foreach($get_v as $vv) $rv .= $r[intval($vv,10)].” “;
$ar[$rk] = $rv;
}
return $ar;
}