บทที่ 8 การเรียงลำดับข้อมูล (Sorting)

การเรียงลำดับข้อมูล (Sorting)

การจัดเรียงลำดับ (Sorting) หมายถึงการจัดเรียงข้อมูล ให้เรียงลำดับตามเงื่อนไขที่กำหนดไว้ (มากไปน้อย หรือ น้อยไปมาก)

ในกรณีที่ข้อมูลในแต่ละ Record มีหลาย Field เราต้องพิจารณาเลือก Field ที่สนใจเพื่อใช้ในการเรียงลำดับ เช่น การจัดเรียงลำดับประวัตินักศึกษา อาจใช้หมายเลขประจำตัวของนักศึกษาเป็น Field โดยเรียงจากน้อยไปมาก

ประเภทของการเรียงลำดับข้อมูล

การจัดเรียงภายใน (Internal Sorting)

การจัดเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำของเครื่องคอมพิวเตอร์ การจัดเรียงแบบนี้จะต้องอาศัยเทคนิคและวิธีการของโครงสร้างข้อมูลมาช่วย เช่น การใช้ Array หรือ Linked-List เข้ามาช่วย

การจัดเรียงภายนอก (External Sorting)

การจัดเรียงข้อมูลที่เก็บอยู่ในสื่อบันทึกข้อมูล เช่น Disk โดยทั่วไปการเรียงประเภทนี้ มักใช้กับข้อมูลที่มีจำนวนมาก ที่ไม่สามารถเก็บไว้ในหน่วยความจำได้หมด การเรียงในแบบนี้จะต้องแบ่งข้อมูลออกเป็นส่วนย่อย แล้วนำมาเรียงด้วยการจัดเรียงแบบภายในก่อน แล้วจึงนำแต่ละส่วนย่อยมารวมกัน

วิธีการจัดเรียงข้อมูล

การจัดเรียงแบบแลกเปลี่ยน (Exchange Sort)

การจัดเรียงแบบแทรก (Insertion Sort)

การจัดเรียงแบบเลือก (Selection Sort)

การจัดเรียงแบบแลกเปลี่ยน (Bubble Sort)

เป็นการจัดเรียงโดยการเปรียบเทียบค่า 2 ค่าที่ติดกัน

ทำต่อเนื่องกันไปเรื่อย ๆ และตัดสินใจว่าจะสลับตำแหน่งกันหรือไม่ เช่น ถ้าต้องการเรียงข้อมูลจากน้อยไปมาก ก็คือ

➧ข้อมูลที่มีค่าน้อย ต้องอยู่ในตำแหน่งหน้า

➧ข้อมูลที่มีค่ามาก จะอยู่ตำแหน่งหลัง

➧ข้อมูล 2 ตัวที่อยู่ติดกัน ถ้า

➠ถ้าข้อมูลตัวแรกมากกว่าตัวหลัง ก็จะต้องสลับตำแหน่งกัน

➠แต่ถ้าข้อมูลตัวแรกน้อยกว่าข้อมูลตัวหลัง ก็ไม่ต้องสลับตำแหน่ง

➨ทำเช่นนี้ซ้ำกันไปเรื่อย ๆ จนกว่าการเปรียบเทียบของข้อมูลตลอดทั้งชุดจะไม่ต้องมีการสลับตำแหน่งเลย

Bubble Sort

เป็นวิธีที่ง่ายเช่นกัน

แนวคิด คือค่าที่มากๆ จะต้องถูกนำไป (ลอยไป) ไว้ด้านท้าย

เหมือนลูกโป่งที่ขนาดใหญ่จะลอยได้เร็วและสูง

⧭แนวคิด

￫เริ่มนำข้อมูลตัวแรกเทียบกับตัวที่ 2 ตัวไหนมากก็จะถูกสลับกัน ทำอย่างนี้ไปจนถึงตัวสุดท้าย เราจะได้

￫ค่าที่มากที่สุด 1 ตัวไว้ด้านท้าย

￫แต่ละครั้งจะได้ค่ามากที่สุดไปไว้ท้ายสุด

￫จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-1

￫จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-2

…

￫จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-x

ทำจน x = N-1

ตัวอย่าง: Bubble Sort

ข้อมูล 8  ตัวทำ 7  รอบ = 44,55,12,42,94,18,06,67

รอบที่ ข้อมูล

1 06 44 55 12 42 94 18 67

2 06 12 44 55 18 42 94 67

3 06 12 18 44 55 42 67 94

4 06 12 18 42 44 55 67 94

5 06 12 18 42 44 55 67 94

6 06 12 18 42 44 55 67 94

7 06 12 18 42 44 55 67 94

การจัดเรียงแบบแทรก (Insertion Sort)

เป็นการจัดเรียงโดยการนำข้อมูลที่จะทำการเรียงนั้น ๆ ไปจัดเรียงทีละตัว

โดยการแทรกตัวที่จะเรียงไว้ในตำแหน่งที่เหมาะสมของข้อมูลที่มีการจัดเรียงเรียบร้อยแล้ว ณ ตำแหน่งที่ถูกต้อง

⧭ วิธีการลักษณะนี้จะคล้ายกับการหยิบไพ่ขึ้นมาเรียงทีละใบ ซึ่ง

ไพ่ใบแรกจะไม่ต้องสนใจอะไร

แต่เมื่อหยิบไพ่ใบที่ 2 ก็จะต้องพิจารณาว่าจะไว้ก่อนหรือไว้หลังใบแรก

และเช่นเดียวกัน เมื่อหยิบไพ่ใบถัด ๆ มา ก็จะต้องพิจารณาว่าจะวางใบตำแหน่งใดเพื่อให้เกิดการเรียงลำดับ จนกระทั่งหมด

ตัวอย่าง: Insertion Sort

ข้อมูล 8  ตัวทำ 7  รอบ = 44,55,12,42,94,18,06,67

รอบที่ ข้อมูล

2 44   55 12 42 94 18 06 67

3 12 44 55 42 94 18 06 67

4 12 42 44 55 94 18 06 67

5 12 42 44 55 94 18 06 67

6 12 18 42 44 55 94 06 67

7 06 12 18 42 44 55 94 67

8 06 12 18 42 44 55 67 94

การจัดเรียงแบบเลือก (Selection Sort)

🔺เป็นการจัดเรียงโดยการเริ่มต้นค้นหาข้อมูลตัวที่น้อยที่สุดจากข้อมูลที่มีอยู่ทั้งหมด

แล้วเอามาเก็บไว้ข้างนอก

แล้วกลับไปหาข้อมูลตัวที่น้อยที่สุดในกองต่อไปจนกว่าจะหมดกอง

ตัวอย่าง: Selection Sort

ข้อมูล 8  ตัวทำ 7  รอบ = 44,55,12,42,94,18,06,67

รอบที่ ข้อมูล

1 06 55 12 42 94 18 44 67

2 06 12 55 42 94 18 44 67

3 06 12 18 42 94 55 44 67

4 06 12 18 42 94 55 44 67

5 06 12 18 42 44 55 94 67

6 06 12 18 42 44 55 94 67

7 06 12 18 42 44 55 67 94

Heap sort

🔼ในการจัดเรียงด้วยเวลา O(N log N)  อัลกอริทึมที่ใช้พื้นฐานแนวคิดนี้ เรียกว่า heapsort และมี Big-Oh running time ดีกว่าอัลกอริทึม

อื่น ๆ ที่กล่าวมาแล้ว

🔼วิธีการ คือ สร้าง binary heap (มีสมาชิก N ตัว) ซึ่งใช้เวลา O(N) จากนั้นทำ deleteMin N ครั้ง สมาชิกที่ถูกย้ายออกไปจาก heap ตัวแรก คือตัวที่มีค่าน้อยที่สุด และเรียงลำดับตามค่าไป แล้วนำไปเก็บใน Arrray อีกตัวหนึ่งจากนั้นก็คัดลอกกลับไปยัง Array เดิมซึ่งก็จะเป็นคำตอบในการจัดเรียง เนื่องจากการทำ deleteMin แต่ละตัวใช้ O(log N) ดังนั้น running time รวมทั้งหมด คือ O(N log N)

🔼หลังการทำงานจนเสร็จ Array ที่ได้ก็จะเป็น Arrayของสมาชิกที่จัดเรียงจากมากไปน้อย

      🔽ถ้าต้องการจัดเรียงจากน้อยไปมาก เราก็จะใช้ heap ที่ parent มีค่ามากกว่า child ของมัน นั่นคือ (max)heap

🔼เราจะใช้ (max)heap ในการ implement ของเราและยังคงใช้ Array เช่นเดิม

     🔽ขั้นแรกสร้าง heap ด้วย linear time จากนั้นทำ deleteMaxes จำนวน N - 1 ครั้ง ด้วยการสลับสมาชิกตัวสุดท้ายใน heap กับสมาชิกตัวแรก แล้วลดขนาดของ heap ลงแล้วทำการ percolating down 

      🔽หลังจบอัลกอริทึมจะได้ Arrayที่มีสมาชิกเรียงตามลำดับค่า

Quick Sort

หลักการดำเนินงาน

* หาตำแหน่งในการแยกลิสต์

* แบ่งแยกข้อมูลออกเป็นสองส่วน และหาตำแหน่ง  

    ในการแยกลิสต์

* ทำจนกว่าข้อมูลจะเรียงลำดับเรียบร้อย

การดำเนินการ

🔼เริ่มต้นใช้ข้อมูลตัวแรกเป็นตัวเปรียบเทียบ (pivot)

🔼ทำการเปรียบเทียบค่าของข้อมูลที่ชี้โดย first กับ

Pivot ถ้าน้อยกว่า pivot ให้ทำการเลื่อน first

ไปยังข้อมูลต่อไปและเปรียบเทียบไปจนกว่าจะพบ

แล้วจึงหยุดการเปรียบเทียบ

🔼เมื่อพบตำแหน่งแล้ว จะหันมาพิจารณาที่ last ชี้อยู่

หากค่าที่ last ชี้อยู่มีค่าน้อยกว่าที่ first ชี้อยู่ให้สลับตำแหน่ง

🔼ทำการเปรียบเทียบค่าของข้อมูลที่ชี้โดย first กับ

Pivot ถ้าน้อยกว่า pivot ให้ทำการเลื่อน first

ไปยังข้อมูลต่อไปและเปรียบเทียบไปจนกว่าจะพบ

แล้วจึงหยุดการเปรียบเทียบ

🔼เมื่อพบตำแหน่งแล้ว จะหันมาพิจารณาที่ last ชี้อยู่

หากค่าที่ last ชี้อยู่มีค่าน้อยกว่าที่ first ชี้อยู่ให้สลับตำแหน่ง

🔼พบตำแหน่งที่จะใช้แบ่งชุดข้อมูลแล้ว จึงทำการแบ่งข้อมูล

ออกเป็นสองชุด

🔼ดำเนินการแบบเดียวกับกับข้อมูลชุดขวามือดำเนินการกับข้อมูลที่เหลือเหมือนเดิมจนกว่าจะได้ข้อมูลในตำแหน่งต่างๆ จนครบ

* เราจะ

พิจารณาชุดข้อมูลด้านซ้ายมือก่อนเสมอ

Merge Sort

กระบวนการแยกชุดข้อมูล

กระบวนการรวมชุดข้อมูล

ได้ชุดข้อมูลที่เรียงลำดับเรียบร้อยแล้ว

Merge Sort Algorithm Analysis

จำนวนครั้งของการเปรียบเทียบทั้งหมด

=ผลบวกทุกระดับของ(จำนวนลิสต์ในแต่ละระดับ * จำนวนครั้งของการเปรียบเทียบแต่ละลิสต์ )

= (N-1) *1 + (N/2 -1)*2 + (N/4 – 1)*4 +..+(2-1)*N/2

= ( N-1) + (N-2)+(N-4)+..+(N-N/2) 

=  Nlog2N    จะได้ bigO(Nlog2N)

Merge Sort 

        ⧭สรุป⧭

ไมควรใชการเรียงลําดับแบบฟอง

การเรียงลำดับแบบเลือกยายขอมูลนอยครั้งสุด

ถ้าขอมูลมีมากไม่ควรใช้การเรียงลำดับแบบแทรก

การเรียงลำดับแบบผสานเร็วกว่าถ้าขอมูลมีมากแตตองการเนื้อที่เสริม

การเรียงลำดับแบบฮีปเปน O(n log n) แตชา

การเรียงลำดับแบบเร็ว ตองเขียนดี ๆ ถึงเร็ว

บทที่ 7 กราฟ

  กราฟ (Graph)

    กราฟ (Graph)  เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นอีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน 

    ตัวอย่าง

     

        V = {A,B,C,D,E,F,G}

       E = {ab,ac,ad,be,cd,cf,de,ef,fg,eg}

    โครงสร้างข้อมูลแบบกราฟ (Graph)

    ศัพท์ที่เกี่ยวข้อง

   1. เวอร์เทก (Vertex)  หมายถึง  โหนด

   2. เอดจ (Edge)หมายถึงเส้นเชื่อมต่อระหว่างเวอร์เท็กซ์บนกราฟ แบบ Undirected Graph

   3. Arc หมายถึง เส้นที่เชื่อมต่อระหว่างเวอร์เท็กซ์บนกราฟ แบบ Directed Graph

  4. ดีกรี (Degree)หมายถึงจำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด

     แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน

      Graph แบ่งเป็น 1.Directed Graph (Digraph)   

                                2.Undirected Graph

    โครงสร้างข้อมูลแบบกราฟ (Graph)

     

    แอดจาเซนท์โหนด (Adjacent Node)

    A กับ B ใช่

    D กับ F ไม่ใช่

    

      

       เส้นทาง (Path) 

   ใช้เรียกลำดับของ เวอร์เทก (Vertex) ที่เชื่อมต่อกันจากจุดหนึ่งไปยังอีกจุดหนึ่ง

     (A,B,C,D,E)

     (A,B,E,F)

     Cycle

     Path ที่ประกอบด้วยอย่างน้อย 3 Vertex และมีจุดเริ่มต้นและสิ้นสุดเดียวกัน เช่น

    (B,C,E,B)

    (B,C,D,E,B)

     ลูป (Loop)

  มีเพียง Arc เดียวและมีจุดเริ่มต้นและสิ้นสุดเดียวกัน

     Directed Graph : มีการกำหนดทิศทาง

     Strongly Connected   ทุก ๆ 2 Vertex มี Path ทั้งไปและกลับ 

     (ทุกโหนดในกราฟมีพาทติดต่อถึงกันหมด)

    Weakly Connected : มีอย่างน้อย 2 Vertex ที่มี Path ในทิศทางเดียว(บางโหนดไม่สามารติดต่อไปยังทุกโหนดในกราฟนั้นได้)

    สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบมีทิศทาง  =  N * (N –1)

จากภาพที่ (ข) ซึ่งเป็นกราฟแบบมีทิศทาง และจำนวนเวอร์เทกซ์ที่มีทั้งหมดเท่ากับ 4 เวอร์เทกซ์ จึงคำนวณหาจำนวนเอดจ์ได้ดังนี้

สูตรหาจำนวนเอดจ์ของกราฟมีทิศทาง     =  N * (N –1)

  = 4 * ( 4 – 1)

  = 4 * 3

  = 12 เส้น

    

       

     Undirected Graph : ไม่มีการกำหนดทิศทาง

   

     

  

เป็นกราฟที่ไม่ระบุทิศทางของการเชื่อมต่อ

    ซึ่งสามารถทำให้สามารถเดินทางไปมาระหว่างกันได้

       สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบไม่มีทิศทาง 

  = (N * (N – 1)) / 2

  กราฟแบบไม่มีทิศทาง และจำนวนเวอร์เทกซ์ที่มีทั้งหมด   เท่ากับ 4 เวอร์เทกซ์ จึงคำนวณหาจำนวนเอดจ์ได้ดังนี้

   สูตรหาจำนวนเอดจ์ของกราฟไม่มีทิศทาง  = (N * (N – 1)) / 2

           = (4 * (4 – 1)) / 2

           = (4 * 3 ) / 2

           = 12 / 2

          = 6 เส้น

    กราฟที่มีน้ำหนัก (Weighted Graphs)

     กราฟที่แต่ละเอดจ์จะมีค่าบ่งบอกถึงความหมายอย่างใดอย่างหนึ่ง เช่น ระยะทาง ความเร็ว เวลาเดินทาง ค่าโดยสาร เป็นต้น 

    

  

    

 กราฟที่ไม่มีน้ำหนัก (Unweighted Graphs)

    เป็นกราฟที่ไม่กำหนดน้ำหนักของเส้นเชื่อมต่อโดยให้แต่ละเส้นมีน้ำหนักเป็น 1  เท่ากัน

     หมดทุกเส้น

  การเก็บข้อมูลในหน่วยความจำสามารถทำได้ 2 แบบ ดังนี้

   1.Adjacency Matrix  :   ใช้อาร์เรย์เก็บข้อมูล

   2. Adjacency List  :  ใช้ลิงค์ลิสต์เก็บข้อมูล

     Adjacency Matrix

    เป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง  หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x n

     Mk เป็นเมทริกซ์ของกราฟใด ๆ  k คือทางเดินที่มีความยาว k จากโหนดหนึ่งไปอีกโหนดหนึ่ง 

      0 : ไม่เป็นแอดจาเซนซีกัน

      1 : เป็นแอดจาเซนซีกัน

      

   1

  

    การแทนกราฟด้วยอะเรย์สองมิติ

     Adjacency List

     Graph Traversal

    สามารถทำได้ 2 วิธี

1. แนวลึก : Depth-first Traversal  

2. แนวราบ : Breath-first Traversal

     Breath-first Traversal

    เป็นการท่องเข้าไปในกราฟโดยเข้าเยี่ยมโหนดตัวแรก และดำเนินการ  หากมีโหนดใกล้เคียงจะดำเนินการกับโหนดที่อยู่ด้านซ้ายก่อน

   1. Enqueue vertex

   2. Dequeue vertex และประมวลผล

   3. Enqueue adjacent ทั้งหมดของ Vertex ในข้อ 2

   4. ทำซ้ำข้อ 2-3 จนกว่าจะครบทุก Vertex และ Queue ว่าง

    

     Network

    คือ Graph ที่ทุก Edge มี Weight กำกับโดยความหมายของ Weight นั้นขึ้นอยู่กับการใช้งาน

   Adjacency Matrix

Adjacency List

    

    

    Minimum Spanning Tree (MST) 

    คือSpanning Tree ที่มีผลรวมของ Weight ทั้งหมดน้อยที่สุด

   1.ใส่ Vertex เริ่มต้นใน Tree

   2.เลือก Edge จาก Vertex ใน Tree ไปยัง Vertex ที่ไม่อยู่ใน Tree และมี Weight ต่ำสุด

  3.ทำซ้ำข้อ 2 จนกว่าจะครบทุก Vertex

 Shortest Path หมายถึง Path ที่สั้นที่สุดระหว่าง 2 Vertexหาเส้นทางการส่งข้อมูลจากต้นทางไปปลายทาง โดยให้มีระยะทางสั้นที่สุด

   1.ใส่ Vertex เริ่มต้นใน Tree

   2.เลือก Edge จาก Vertex ใน Tree ไปยัง Vertex ที่ไม่อยู่ใน Tree และมีผลรวมของ Weight ต่ำสุด

   3.ทำซ้ำข้อ 2 จนกว่าจะครบทุก Vertex

  minimum Spanning Tree เป็นรูปแบบของการค้นหาโดยกำหนดเรียกใช้โหนดทุกโหนดและทุกเส้นการเชื่อมต่อ  มาลำดับความสำคัญของน้ำหนักโดยเริ่มจากค่าน้อยที่สุดในข่ายงาน  ทำการเชื่อมต่อคู่โหนดนั้น  และดำเนินการต่อไปในค่าน้ำหนักที่ต่อกัน  แต่ถ้าโหนดใดมีการเชื่อมต่อคู่โหนดแล้วจะไม่เชื่อมต่ออีก

   Shortest Path เป็นอัลกอริทึมที่ใช้ในการหาระยะทางที่สั้นที่สุดเช่นเดียวกับ  MST  แต่จะเปลี่ยนจากการหาเส้นทางจากโหนดแรกไปยังโหนดปลายทางของข่ายงาน  เป็นโหนดที่กำหนดเป็นโหนดต้นทางไปยังโหนดต่าง ๆ โดยหาระยะทางสั้นที่สุดแต่ละเส้นทาง

 Minimum Spanning Tree

Spanning Tree หมายถึง Tree ที่ประกอบด้วยทุก Vertex ใน Graph ซึ่งอาจมีได้มากกว่า 1 แบบ