โครงสร้างข้อมูลและอัลกอริธึม

Quick Sort การจัดเรียงข้อมูลแบบ Quick Sort มีขั้นตอน 4 ขั้นคือ 1.       ถ้าจำนวนตัวเลขมีเพียง 0 หรือ 1 ตัวไม่ต้องทำงาน ให้หยุดทำได้ 2.       เลือกตัวเลขขึ้นมาหนึ่งตัว เรียกเลขตัวนี้ว่า Pivot สมมุติว่าคือ v 3.       แบ่งกลุ่มตัวเลขออกเป็น 2 กลุ่ม โดยกลุ่มที่ 1 จะต้องเป็นเลขที่น้อยกว่า v ทั้งหมด และกลุ่มที่ 2 จะต้องเป็นเลขที่มากกว่า v ทั้งหมด 4.       กลับไปที่ขั้นตอนที่ 1 ใหม่ โดยทำกับเลข กลุ่มที่ 1 และทำกับเลขกลุ่มที่ 2 ทำแบบนี้ไปเรื่อยๆ จนเลขในกลุ่มย่อยๆ ลดเหลือเพียงแค่ 0 หรือ 1 ตัวก็หยุดได้ ตัวอย่างการทำ Quick Sort เช่น ถ้ามีเลขอยู่ 10 ตัวอยู่ในอะเรย์ a ดังนี้ ถ้าจะจัดเรียงแบบ Quick Sort เราจะต้องหา Pivot ก่อนวิธีการหา Pivot ที่ไม่แนะนำคือ o     ใช้เลขตัวแรกสุดเป็น Pivot แบบนี้เสี่ยงในกรณีที่เลขในชุดนั้นจัดเรียงไว้เรียบร้อยแล้วจะได้ O(N 2 ) o     ใช้วิธีสุ่มเลขแบบ Random มีข้อเสียคือ อัลกอริธึมการสร้างเลขสุ่มเสียเวลาค่อนข้างนาน เราจ...

Shell Sort การจัดเรียงข้อมูลแบบ Shell Sort เป็นวิธีการที่ช่วยปรับปรุง Insertion Sort ให้มีจำนวนครั้งการสับเปลี่ยนข้อมูลลดลง เนื่องจากวิธีการ Insertion Sort อาจจะเกิด Worst-Case ในกรณีเลวร้าย ที่ค่าตัวเลขเล็กๆ ดันไปอยู่ที่ข้างท้ายๆ ทำให้การสแกนหาตำแหน่งที่เหมาะสม ต้องใช้วิธีนานมาก วิธีการ Shell Sort ปรับปรุงโดยทำการจัดเรียงชุดย่อย โดยแต่ละชุดย่อยเรียกว่า k-sorted โดย k จะเป็นเลขลำดับที่เพิ่มมากขึ้นเรื่อยๆ เช่น k อาจจะเป็นเลข {1, 3, 5} หมายถึง ครั้งแรกที่ทำ 5-sorted จะจัดเรียงตัวเลขทุกตัวที่ห่างกันทีละ 5 ช่อง  เมื่อเรียงเสร็จแล้วจะทำ 3-sorted โดยจัดเรียงตัวเลขทุกตัวที่ห่างกันทีละ 3 ช่อง และสุดท้ายจะทำ 1-sorted โดยจัดเรียงตัวเลขทุกตัวที่ติดกันอยู่ ซึ่งในรอบสุดท้ายที่ 1-sorted จะเป็นวิธีการเดียวกับ Insertion Sort นั่นเอง เราเรียกค่า k = {1, 3, 5} นี้ว่า increment sequence และบางครั้งเรียกวิธีการจัดเรียง Shell Sort นี้ว่า diminishing increment sort ตัวอย่างเช่น ถ้ามีเลขอยู่ 13 ตัวดังนี้ และให้ k = {1, 3, 5} ถ้าจะจัดเรียงแบบ Shell Sort รอบแรกเราจะทำ 5-sorted ก่อน โดยจัดเร...

Biconnectivity กราฟจะเรียกว่าเป็น biconnected ถ้าพบว่าเมื่อตัดจุดใดๆออกไปจากกราฟแล้วจุดที่เหลือยังต่อกันอยู่ โดยการตัดจุดไปไม่ทำให้กราฟแตกออกเป็น 2 กราฟ ประโยชน์ของ biconnected ถูกนำมาใช้ในการวางระบบเครือข่ายที่มีเสถียรภาพ เพื่อให้แน่ใจว่าเมื่ออุปกรณ์ต่อเชื่อมในเครือข่ายเสียหายไปสักตัว จะไม่ทำให้เครือข่ายถูกตัดขาดออกจากกัน และยังคงมีเส้นทางอื่นๆที่สามารถวิ่งถึงกันได้ แม้ว่าจะเป็นทางอ้อมก็ตาม ถ้ากราฟไม่ได้เป็น biconnected เราจะพบจุดที่เรียกว่าเป็น articulation point (articulation – แปลว่า ชัดเจน ฟังออก) ซึ่งจุดพวกนี้ ถ้าตัดออกไปจะทำให้กราฟถูกแตกออกจากกันเป็นหลายกราฟ ตัวอย่างเช่นกราฟต่อไปนี้ สังเกตว่าหากเราตัดจุด B, A, G, E, F ออกไปจะไม่ทำให้กราฟแตกออกจากกัน แต่ถ้าตัดจุด C หรือ จุด D ออกจะทำให้กราฟแตกออกจากกันดังนี้ วิธีการหา articulation point ในกราฟ ทำได้ตามขั้นตอนดังนี้ 1.       ท่องไปในกราฟแบบ depth-first search และใส่หมายเลขลำดับประจำจุดเอาไว้ (เรียกว่า Num(v)) 2.       ท่องไปใน depth-first spanni...