ADT Lecture 2
แบบข้อมูลนามธรรม และ โครงสร้างข้อมูล
- เซตเป็น abstract data type (แบบข้อมูลนามธรรม) ซึ่งนิยามว่าคือรายการที่ไม่มีสมาชิกซ้ำกันเลย
- สามารถเก็บเซตในโปรแกรมได้โดยใช้โครงสร้างข้อมูล (data structure) array หรือ array เรียงลำดับ (sorted array)
- การเขียนเซตด้วย array เรียงลำดับนั้นจะทำให้กระบวนการบางอย่างทำงานได้ไวขึ้น
- ฉะนั้นสามารถสรุปได้ว่าโครงสร้างข้อมูลบางแบบนั้นทำกระบวนการบางอย่างได้เร็วกว่า
โครงสร้างข้อมูลและอัลกอริธึม
- อัลกอริธึมทำงานกับโครงสร้างข้อมูล
- ตัวอย่างกระบวนการที่ทำงานกับโครงสร้างข้อมูล เช่น
- การแทรก
- การลบ
- การค้นหา
การจัดเรียง
สมมุติว่ามีรายการ 6 5 3 1 8 7 2 4
(เรียงลำดับแบบมั่วๆ) ต้องการจะเรียงข้อมูลจากมากไปน้อย
ในตัวอย่างนี้เราจะใช้ list ในการเก็บข้อมูลรายการนี้เพราะมีรายการที่ซ้ำกันอยู่
Array
- สามารถใช้ array ในการเขียน list ได้
- เสร็จแล้วเรียงข้อมูลด้วยการเขียน bubble sort
.
เดิม: 6 5 3 1 8 7 2 4
เทียบ 6 กับ 5: 6 5 3 1 8 7 2 4
เทียบ 5 กับ 3: 6 5 3 1 8 7 2 4
เทียบ 3 กับ 1: 6 5 3 1 8 7 2 4
เทียบ 1 กับ 8: 6 5 3 8 1 7 2 4
เทียบ 1 กับ 7: 6 5 3 8 7 1 2 4
เทียบ 1 กับ 2: 6 5 3 8 7 2 1 4
เทียบ 1 กับ 4: 6 5 3 8 7 2 4 1
จะเห็นว่า 1 เรียงลำดับแล้ว ในรอบต่อไปจะมองข้ามไป
รอบ 2: 6 5 3 8 7 2 4 1
เทียบ 6 กับ 5: 6 5 3 8 7 2 4 1
เทียบ 5 กับ 3: 6 5 3 8 7 2 4 1
เทียบ 3 กับ 8: 6 5 8 3 7 2 4 1
เทียบ 3 กับ 7: 6 5 8 7 3 2 4 1
เทียบ 3 กับ 2: 6 5 8 7 3 2 4 1
เทียบ 2 กับ 4: 6 5 8 7 3 4 2 1
จะเห็นว่า 1, 2 เรียงลำดับแล้ว ในรอบต่อไปจะมองข้ามไป
อัลกอริธึม bubble sort สามารถเรียงลำดับข้อมูลได้โดยใช้การวนซ้ำ n
รอบ โดย n
คือจำนวนสมาชิกในรายการ
จะเห็นได้ว่า bubble sort เป็นอัลกอริธึมที่ไม่ค่อยมีประสิทธิภาพ
Heap
- Heap เป็น binary tree แบบสมบูรณ์ (ยกเว้นชั้นล่างสุด)
- Binary Tree คือแผนภาพที่มีตัวแม่ (root) และจากตัวแม่ออกไปจะมีตัวลูกไม่เกิน 2 ตัว ตัวลูกแต่ละตัวสามารถมีลูกต่อไปได้เป็นทอดๆ แต่ไม่เกินทอดละ 2 ตัว
- ข้อจำกัดบของ Heap คือตัวแม่จะต้องมีค่ามากกว่าตัวลูก
รายการ: 6 5 3 1 8 7 2 4
เขียน binary tree
6
/ \
5 3
/ \ | \
1 8 <-- ไม่สามารถใส่ได้ (ผิดกฎแม่ต้องมากกว่าลูก) ให้ยกขึ้นข้างบนไปเรื่อยๆ
6
/ \
8 <-- ยกขึ้นมาแล้วก็ยังมากกว่าตัวแม่
/ \
1 5
8
/ \
6 3
/ \ | \
1 5 7 <-- ยกขึ้น
8
/ \
6 7
/ \ | \
1 5 3 2
|
4 <-- ยกขึ้น
8 ผลลัพท์ที่สมบูรณ์
/ \
6 7
/ \ | \
4 5 3 2
|
1
หลังจากสร้างแผนภาพได้แล้วสามารถอ่านค่าได้โดยดึงตัวแม่ออกมาแล้วเอาสมาชิกแถวล่างสุดตัวไหนก็ได้ขึ้นไปแทน จากนั้นแก้ให้เป็น Heap ตามกฎ
. เรียงแล้ว: 8
/ \
6 7
/ \ | \
4 5 3 2
|
1
1 <-- ดึงตัวล่างสุดตัวไหนก็ได้ขึ้นมาแล้วแก้ตามกฎ
/ \
6 7
/ \ | \
4 5 3 2
แก้ไข:
7 เรียงแล้ว: 8
/ \
6 1
/ \ | \
4 5 3 2
7 เรียงแล้ว: 8 7
/ \
6 3
/ \ | \
4 5 1 2 <-- ดึง 7 ข้างบนออก แล้วเอา 2 ขึ้นไปแทน
6 Sorted: 8 7 6 ...
/ \
5 3
/ \ \
4 2 1
อัลกอริธึม heap จะไวกว่าเนื่องจากรายการที่มีสมาชิก 1 ล้านตัวสามารถเขียนเป็นแผนภาพได้ไม่เกิน 20 ชั้น (แผนภาพ 20 ชั้นมีได้ 220 = 1,048,576 รายการ)