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 รายการ)