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


Sorting

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

การจัดเรียงข้อมูลแบบแทรกใส่ (Insertion Sort)
เทคนิคมาจากลักษณะการจัดไพ่ในมือของผู้เล่น คือ เมื่อผู้เล่นได้ไพ่ใบใหม่เพิ่มขึ้นมา จะนำไพ่ใบนั้นไปแทรกในตำแหน่งที่เหมาะสม ทำให้ไพ่ในมือบางส่วนต้องขยับตำแหน่งออกไป ซึ่งการจัดเรียงลำดับข้อมูลแบบแทรกนี้จะเริ่มพิจารณาคีย์ในตำแหน่งที่ 2 เป็นต้นไป

หลักการ คือ จะอ่านข้อมูลไปทีล่ะตัว แล้วนำไปแทรกลงในตำแหน่งที่เหมาะสมบนข้อมูลใหม่ที่เตรียมไว้มีขั้นตอนดังนี้
  •        สร้างแถวข้อมูลมาใหม่ที่มีขนาดเท่ากับจำนวนข้อมูลที่ต้องการจัดเรียง
  •        อ่านข้อมูลแรกแล้วใส่ลงในตำแหน่งแทรกในแถวข้อมูลใหม่
  •        อ่านข้อมูลถัดไปมา 1 ตัว แล้วเปรียบเทียบกับข้อมูลใหม่ทีล่ะตัว ตั้งแต่ตัวแรกไปจนถึงตัวสุดท้าย เพื่อหาตำแหน่งที่เหมาะสมในแถวข้อมูลใหม่
  •        ทำซ้ำขั้นตอนที่ 3 จนครบทั้งชุดข้อมูล


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

มีหลักการและขั้นตอนดังนี้
  •        เริ่มจาก เลือกค่าของข้อมูลที่มีค่าน้อยที่สุด
  •        นำมาแลกเปลี่ยนกับค่าในตำแหน่งแรกสุดของกลุ่ม
  •        หลังจากนั้นกระทำตามหลักการทั้ง 2 กับข้อมูลที่เหลือ คือ ครั้งที่ 2 ค่า A(2) จะถูกแลกกับค่าที่เลือกแล้วว่าน้อยที่สุดในลิสต์ A(2)...A(N) และครั้งที่ 3 A(3) จะถูกแลกกับคืที่เลือกแล้วว่าน้อยที่สุดในลิสต์ A(3)...A(N)
  •        และเรื่อยไปจนกระทั่งเหลือข้อมูลที่จะเปรียบเทียบแค่ 2 ค่าคือ A(N-1)
  •        และ A(N) ดังนั้น จำนวนรอบในการกระทำเป็น n-1 รอบ

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

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

การจัดเรียงข้อมูลโดยใช้ฮีป Heap Sort
Heap Sort หรือบางครั้งเรียกว่า Tree Sort จะอาศัยโครงสร้างข้อมูลแบบ Binary Tree แต่การแตกกิ่งก้านของโหนดในต้นไม้จะต้องอยู่ภายใต้เงื่อนไขต่อไปนี้
  •        ที่ทุกระดับของ Heap จะแตกสาขาออกไปได้ 2 ทาง คือทางซ้ายและทางขวา
  •        จะต้องมีโหนดในระดับบนครบ 2 ด้านก่อน จึงจะแตกโหนดต่อในระดับล่างได้
  •        การแตกโหนดออกไปนั้นจะต้องเริ่มจากทางซ้ายก่อน จึงจะแตกไปทางด้านขวาตามลำดับ
  •        ค่าคีย์ของโหนด จะต้องถูกจัดในลักษณะที่ว่า โหนดตัวบน (FATHER) จะต้องมีค่าของคีย์สูงกว่าโหนดตัวล่าง (SON)

ขั้นตอนในการเรียงลำดับข้อมูลด้วยวิธีดังต่อไปนี้
  1. สร้างไบนารีทรี
  2. สร้างฮีป โดยให้โหนดแม่มีค่ามากกว่าโหนดลูกเสมอ
  3. สลับข้อมูลในตำแหน่งที่ 1 กับตำแหน่งที่ n แล้วตัดข้อมูลในตำแหน่งที่ n ออก
  4. ปรับทรีที่เหลือให้เป็นฮีป โดยทำการเปรียบเทียบโหนดลูกสองโหนดพร้อมกันในแต่ละระดับ ถ้าโหนดลูกโหนดใด มีค่ามากกว่าก็สลับตำแหน่งกับโหนดแม่
  5. สลับข้อมูลในตำแหน่งที่ 1 กับตำแหน่งที่ n-1
  6. ปรับทรีที่เหลือให้เป็นฮีป
  7. ทำวนไปอย่างนี้เรื่อยๆ จนกระทั่งถึงการสลับข้อมูลในตำแหน่งที่ 1 กับตำแหน่งที่ 2 ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปหามากตามต้องการ

การจัดเรียงข้อมูลโดยการรวมข้อมูลเข้าด้วยกัน Merge Sort
เป็นการเรียงลำดับที่อาศัยหลักการ Divide and Conquer โดยจะแบ่งข้อมูลออกป็น 2 ส่วน ซึ่งแต่ละส่วนจะแบ่งย้อย ข้อมูลออกป็น 2 ส่วนเรื่อยไปจนกระทั่งไม่สามารถแบ่งได้อีก แล้วจึงเรียงลำดับข้อมูลแต่ละส่วนย่อย จากนั้นนำข้อมูลแต่ละส่วนย่อยมารวม (Merge)เข้าเป็นข้อมูลชุดเดียวกันพร้อมทั้งเรียงลำดับข้อมูล

การจัดเรียงข้อมูลแบบเร็ว Quick Sort
เป็นการเรียงลำดับที่อาศัยหลักการ Divide and Conquer โดยจะแบ่งข้อมูลออกป็น 2 ส่วน ซึ่งแต่ละส่วนจะแบ่งย้อย ข้อมูลออกป็น 2 ส่วนเรื่อยไปจนกระทั่งไม่สามารถแบ่งได้อีก แล้วจึงเรียงลำดับข้อมูลแต่ละส่วนย่อย จากนั้นนำข้อมูลแต่ละส่วนย่อยมารวม (Merge)เข้าเป็นข้อมูลชุดเดียวกันพร้อมทั้งเรียงลำดับข้อมูล

มีขั้นตอนในการจัดเรียงข้อมูลดังนี้
  1. เลือก pivot  มา 1 ตัว (นิยมตัวกลาง หรือสุ่ม)
  2. เตรียมตัวชี้ไว้ 2 ตัวนึงชี้ซ้าย ตัวนึงชี้ขวา
  3. ตัวชี้ซ้าย ให้ไล่ไปทางขวาเรื่อยๆ จนกว่าจะเจอตัวที่มากกว่าหรือเท่ากับ pivot  
  4. ส่วนตัวขวา ให้ไล่ไปทางขวาเรื่อยๆ จนกว่าจะเจอตัวที่มากกว่าหรือเท่ากับ pivot  
  5. จับตัวที่ตัวชี้ทั้ง 2 ชี้อยู่ สลับที่กัน แล้วขยับตัวชี้ทั้ง 2 เข้าหากัน 1 ตำแหน่ง
  6. ถ้าเกิดตัวชี้ทั้ง 2 ยังไม่ไขว้กัน กลับไปทำข้อ 3 ไปเรื่อยๆ
  7. ถ้าไขว้กันแล้ว แบ่งฟาก เรียงฟากซ้ายก่อน แล้วเรียงฟากขวา






ความคิดเห็น

แสดงความคิดเห็น

โพสต์ยอดนิยมจากบล็อกนี้

Queue structure

รูปภาพ
Queue structure โครงสร้างการทำงานแบบคิวคือการมีการจัดลำดับการเข้าและออกข้อมูลอย่างเป็นลำดับ ข้อมูลใดเข้ามาก่อนก็จะดำเนินการก่อน  หากข้อมูลใดเข้ามาทีหลังก็จะดำเนินการทีหลัง เรียกลักษณะของการดำเนินการแบบนี้ว่า   First In First Out (FIFO) หรือ เข้าก่อนออกก่อน ลักษณะของคิว         โครงสร้างข้อมูลแบบคิวเป็นโครงสร้างเชิงเส้นและไม่เชิงเส้น         มีทางเข้าและออก 2  ทาง         มีการทำงานแบบลำดับ         สามารถนำข้อมูลเข้าและนำข้อมูลออกสลับกันได้         มีลำดับการทำงานแบบเข้าก่อนออกก่อน (FIFO) ประเภทของคิว มี 3 ประเภท         คิวธรรมดา (Queue)         คิววงกลม (Circular Queue)         คิวที่เรียงลำดับตามความสำคัญ (Priority Queue) การดำเนินการของคิว      เมื่อนำเข้าข้อมูลจะต้องจัดเรียงในลักษณะการต่อท้ายกัน         ข้อมูลที่อยู่ส่วนท้ายของการเก็...
อ่านเพิ่มเติม

กราฟ(Graph)

รูปภาพ
กราฟ (Graph) กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน เช่น วางข่ายงานคอมพิอเตอร์วิเคระห์เส็นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น             นิยามกราฟ ·        กราฟเป็นโครงสร้างที่นำมาใช้เพื่อแสดงความสำพันธ์ระหว่างวัตถุ โดยแทน วัตถุด้วยเวอร์เท็กซ์ ( Vertex) หรือโหนด ( Node) และเซื่อมโยง ความสำพันธ์ด้วยเอดจ์ ( Edge)  ·        เขียนในรูปของลักษณ์ได้เป็น G=(V,E) ·        V(G)  คือ เซตของเวอร์เท็กซ์  ที่ไม่ใช้เซ็ตต่างๆ และมีจำนวนจำกัด ·        E(G) คือ เซตของเอดจ์ ซึ่งเขียนด้วยคู่ของเวอร์เท็กร์ ศัพท์ที่เกี่ยวข้อง 1.             เวอร์เทกซ์  ( Vertex)     หมายถึง   โหนด 2.        ...
อ่านเพิ่มเติม

Tree

รูปภาพ
Tree ทรี  หมายถึงโครงสร้างที่มีความสำพันธ์ในลักษณะลำดับชั้น ชมาชิกแต่ล่ะโหนดล้วนมีความสำพันธ์กันในลักษณะเหมือนครอบครัวเดี่ยวกันโดยมีโหนดพ่อซึ่งอยู่ระดับเหนือกว่ามีเส้นเซื่ยมโยงจากโหนดพ่อไปอย่างโหนดที่อยู่ในระดับต่ำมากกว่าที่เรียกว่าโหนดลูก องค์ประกอบของทรีประกอบด้วย   โหนดราก ( Root Node) คือโหนด A ซึ่งโหนดรากหรือรูทโหนดถือเป็นโหนดแรกสำรับโครงสร้างทรีเป็นโหนดเริ่มต้นเพื่อขยายลูกหลานต่อไป โหนดพ่อ ( Parents) คือโหนด A,B และ F ก็คือโหนดที่มี Successor โหนดลูก ( Children) B,E,F,C,D,G,H และ I ซึ่งก็คือโหนดที่มี Predecessor โหนดพี่น้อง ( Siblings) คือโหนด {B,E,F},{C,D} และ {G,H,I} โหนดใบ ( Leaf Node) คือโหนด C,D,E,G,H และ I ซึ่งก็คือโหนดที่ไม่มี Successor ดีกรี ( Degree) ทั้งหมดของทรี มีค่าเท่ากับ 8 ดีกรี ( Degree) ทั้งหมดของโหนด F มีค่าเท่ากับ 3 จำนวนของ Leaf  โหนด มีค่าเท่ากับ 6 ระดับความสูงหรือความลึกของทรี             -คำนวนได้จากสูตร Height = 2+1+3 ซับทรี (Subtree)       ...
อ่านเพิ่มเติม