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

การ เรียงลำดับข้อมูลเป็นเรื่องสำคัญมากเรื่องหนึ่งเนื่องจากทำให้ผู้ต้องการใช้ ข้อมุลเช่น ผู้บริหาร,ผู้ปฏิบัติงาน (พนักงาน) สามารถทำความเข้าใจกับข้อมูลหรือทำการค้นหาข้อมูลได้ง่ายและเร็วยิ่งขึ้นตาม ที่ต้องการ

ประเภทของการจัดการจัดเรียงข้อมูลในระบบคอมพิวเตอร์ แบ่งเป็น 2 ประเภทคือ

  • 1. Internal Sorting คือ การเรียงลำดับข้อมูลโดยเก็บไว้ในหน่วยความจำหลัก และข้อมูลของสมาชิกจะถูกเก็บ อยู่ในโครงสร้างอะเรย์
  • 2. External Sorting คือ การเรียงลำดับข้อมูลโดยเก็บไว้ในหน่วยความจำสำรอง ข้อมูลส่วนใหญ่มีจำนวนมาก จึงไม่ สามารถเก็บไว้ในหน่วยความจำหลักได้ทั้งหมด

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

วิธีหรือชนิดของการเรียงลำดับ มีวิธีต่าง ๆ ที่มักจะได้พบโดยทั่วไปดังนี้
  • 1. SELECTION SORT
  • 2. INSERTION SORT / LINEAR INSERTION SORT
  • 3. BUBBLE SORT
  • 4. SHELL SORT
  • 5. BUCKET SORT /RADIX SORT
  • 6. QUICK SORT
  • 7. HEAP SORT / TREE SORT
1. การเรียงลำดับแบบเลือก (Selection Sort)
เป็นวิธีที่ง่ายที่สุดในการเรียงลำดับข้อมูล โดยเริ่มจาก
# - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดแล้วสลับค่าของตำแหน่งข้อมูลนั้นกับค่าข้อมูลในตำแหน่ง A(1) จะได้ A(1) มีค่าน้อยที่สุด
# - หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดในกลุ่ม A(2), A(3),....,A(n) แล้วทำกับสลับค่าข้อมูลในตำแหน่ง A(2) อย่างนี้เรื่อยไปจน กระทั่งไม่เกิน N-1 รอบ ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก

2. การเรียงลำดับแบบแทรก (Insertion Sort)
หลักการ คือ
  • 1. อ่านข้อมุลที่ต้องการเรียงลำดับเข้ามาทีละตัวโดยเริ่มจากตัวแรกก่อน และหาตำแหน่งของข้อมูลที่ควรจะอยู่
  • 2. หาที่ว่างสำหรับข้อ 1.
  • 3. Insert หรือแทรกข้อมูล ณ ตำแหน่งในข้อ 2.
3. การเรียงลำดับแบบบับเบิล (Bubble Sort)

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

ในวิธีแบบ Bubble Sort ค่าในการเปรียบเทียบที่น้อยที่สุดหรือมากที่สุด จะลอยขึ้นข้างบน เหมือนกับฟองอากาศ

4. การรียงลำดับแบบเชลล์(shell sort)

เป็นรูปแบบของการ sort ข้อมูลโดยการนำเอาข้อดีของการค้นหาข้อมูลแบบ แทรกและแบบเลือกและหลีกเลี่ยง การเกิดปัญหาของทั้งแบบแทรกและแบบเลือก ซึ่งการเปรียบเทียบข้อมูลในการเรียงลำดับแบบแทรก โดยการเปรียบเทียบ ข้อมูลที่อยู่ไกลออกไป ซึ่งจะทำให้เราสามารถเรียงดับข้อมูลในตำแหน่งที่อยู่ไกลออกไปหลังจากนั้นก็ จะเรียงลำดับข้อมูล ที่อยู่ใกล้กันเข้ามา(กว่าในครั้งแรก) และความห่างของข้อมูลที่เปรียบเทียบก็จะน้อยลงจนเหลือ 1

วิธีนี้คิดค้นเมื่อปี ค.ศ.1959 โดย ดี.แอล.เชลล์(D.L.SHELL) เรียกว่า การเรียงลำดับแบบเชลล์(shell sort)

5. การเรียงลำดับโดยการใช้ฐานเลข(radix sort)

การเรียงลำดับแบบนี้การเรียงลำดับ จะอยู่บนพื้นฐานของการแทนตำแหน่งของตัวเลขที่ต้องการนำมาเรียงลำดับ จะเริ่มจากตัวที่มีเลขนัยสำคัญสูงที่สุด ดำเนินจนกระทั่งถึงตัวเลขที่มีเลขนัยสำคัญต่ำสุด การเรียงลำดับในวิธีนี้การเรียงลำดับ จะเรียงจากตัวเลขที่มีนัยสำคัญน้อยที่สุดก่อน เมื่อตัวเลขทั้งหมดถูกนำมาเรียงลำดับตามเลขนัยสำคัญที่สูงขึ้น ตัวเลขที่เหมือนกัน ในตำแหน่งน้น จะต่างกันในตำแหน่งของเลขนัยสำคัญที่น้อยกว่า การประมวลผลแบบนี้จะประมวลผลกับข้อมูลทั้งหมดได้ โดยที่ไม่ต้องมีการแบ่งข้อมูลแบบกลุ่มย่อย

6. การเรียงลำดับอย่างเร็ว(quick sort)

ถูก สร้างและตั้งชื่อโดย ซี.เอ.อาร์.ฮาร์เวร์ (C.A.R HOARE) การเรียงลำดับอย่างเร็ว จะแบ่งข้อมูลเป็นสองกลุ่ม โดยใน การจัดเรียงจะเลือกข้อมุลตัวใดตัวหนึ่งออกมา ซึ่งจะเป็นตัวที่แบ่งข้อมูลออกเป็นสองกลุ่ม โดยกลุ่มแรกจะต้องมีข้อมูลน้อยกว่า ตัวแบ่ง และกลุ่มที่มีข้อมูลน้อยกว่าตัวแบ่ง และอีกกลุ่มจะมีข้อมูลที่มากกว่าตัวแบ่ง ซึ่งเราเรียกตัวแบ่งว่า ตัวหลัก(pivot) ในการเลือกตัวหลักจะมีอิสระในการเลือกข้อมูลตัวใดก็ได้ที่เราต้องการ การเรียงลำดับแบบเร็วเหมาะกับข้อมูลที่มีการเรียกซ้ำ

7.การเรียงลำดับฮีพ(heapsort)

เป็นการเรียงลำดับที่อยู่บนพื้นฐานบนพื้นฐานของโครงสร้างแบบไบนารี จะดำเนินการ 2 ขั้นตอน คือ
  • 1. การจัดข้อมูลในอะเรย์ให้สอดคล้องกับความต้องการของฮีพ
  • 2. การขจัดหนือการเคลื่อนย้ายข้อมูลในตำแหน่งสูงสุดหรือตำแหน่งยอดของของฮีพออกไปและสนับสนุนข้อมูลข้อมูล ตัวอื่นไปแทนตำแหน่งนั้น

โครงสร้างข้อมูลกราฟ

กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูป และการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด

กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้

กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้

G = ( V , E )

G คือ กราฟ

V คือ กลุ่มของ vertex

E คือ กลุ่มของ edge

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

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

2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด

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

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

ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น

ประเภทของกราฟ

แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ edge ได้ดังนี้

1. Direct Graph (กราฟแสดงทิศทาง) เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดแสดงทิศทางของการเชื่อมต่อด้วย

2. Undirected Graph กราฟที่แสดงเส้นเชื่อมต่อระหว่าง vertex แต่ไม่แสดงทิศทางของการเชื่อมต่อ

3. Cyclic Graph กราฟที่มีเส้นเชื่อมต่อระหว่าง vertex ที่ทำให้ vertex มีลักษณะเป็นวงจรปิด (Cycle) เส้นเชื่อมต่อระหว่าง vertex อาจจะแสดงทิศทางหรือไม่แสดงทิศทางการเชื่อมต่อก็ได้

เส้นทาง (Path)

เส้นทางคือการเดินทางจาก vertex หนึ่งไปยังอีก vertex หนึ่งที่ต้องการ โดยผ่าน edge ที่เชื่อมระหว่าง vertex

ความยาวของเส้นทาง (The length of path) คือ จำนวนของ edge ในเส้นทางเดินนั้น ว่ามีจำนวนเท่าไหร่ ในการเดินทางจาก vertex หนึ่ง ไปยังอีก vertex หนึ่ง ถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

การแทนที่กราฟด้วยเมตริกซ์

โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1

ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ

ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง

ตัวอย่างจากรูปกราฟแบบ Direct Graph

สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้

ตัวอย่าง หากเป็นกราฟแบบ Undirected Graph

การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix

จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 3 เส้นได้ดังนี้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 4 เส้นได้ดังนี้

โครงสร้างข้อมูลกราฟ

กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูป และการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด

กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้

กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้

G = ( V , E )

G คือ กราฟ

V คือ กลุ่มของ vertex

E คือ กลุ่มของ edge

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

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

2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด

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

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

ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น

ประเภทของกราฟ

แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ edge ได้ดังนี้

1. Direct Graph (กราฟแสดงทิศทาง) เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดแสดงทิศทางของการเชื่อมต่อด้วย

2. Undirected Graph กราฟที่แสดงเส้นเชื่อมต่อระหว่าง vertex แต่ไม่แสดงทิศทางของการเชื่อมต่อ

3. Cyclic Graph กราฟที่มีเส้นเชื่อมต่อระหว่าง vertex ที่ทำให้ vertex มีลักษณะเป็นวงจรปิด (Cycle) เส้นเชื่อมต่อระหว่าง vertex อาจจะแสดงทิศทางหรือไม่แสดงทิศทางการเชื่อมต่อก็ได้

เส้นทาง (Path)

เส้นทางคือการเดินทางจาก vertex หนึ่งไปยังอีก vertex หนึ่งที่ต้องการ โดยผ่าน edge ที่เชื่อมระหว่าง vertex

ความยาวของเส้นทาง (The length of path) คือ จำนวนของ edge ในเส้นทางเดินนั้น ว่ามีจำนวนเท่าไหร่ ในการเดินทางจาก vertex หนึ่ง ไปยังอีก vertex หนึ่ง ถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

การแทนที่กราฟด้วยเมตริกซ์

โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1

ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ

ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง

ตัวอย่างจากรูปกราฟแบบ Direct Graph

สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้

ตัวอย่าง หากเป็นกราฟแบบ Undirected Graph

การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix

จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 3 เส้นได้ดังนี้

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 4 เส้นได้ดังนี้

ทรี (Tree)
หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก


จุดเด่นของทรี
เป็นโครงสร้างที่เน้นข้อมูลที่เปรียบเทียบกันได้ (comparable) เช่นต้นไม้ค้นหา หรือมีลำดับความสำคัญเป็นขั้นตอน เช่นฮีป มักใช้ในการจัดการค้นหาอย่างรวดเร็วเป็น O (log n) หรือการจัดลำดับความสำคัญ เช่นการจัดนิพจน์ซึ่งเรียงลำดับการทำงานโดยต้นไม้นิพจน์

ความเร็วในการทำงานของทรี
ต้นไม้เน้นการทำงานอย่างรวดเร็วโดยการตัดทอนกิ่งที่ไม่สนใจ เช่นต้นไม้ค้นหาแบบทวิภาคที่สามารถไล่ไปตามกิ่งของต้นไม้ ทำให้อย่างมากที่สุด การค้นหาก็จะผ่านจำนวนข้อมูลเท่ากับความสูงของต้นไม้ ซึ่งความสูงของต้นไม้ที่น้อยที่สุดเป็น O (log n) จึงทำให้บริการที่เร็วที่สุดเป็น O (log n) อย่างไรก็ตาม หากจัดการไม่เหมาะสม ความสูงของต้นไม้อาจยืดเป็น O (n) ได้ส่งผลให้บริการช้า จึงต้องมีการจำกัดความสูงและคงสมดุลของต้นไม้ให้เหมาะสม