การจัดเรียงข้อมูล (Sorting) การจัดเรียงหรือเรียงลำดับข้อมูล(Sorting) คือ การจัดเรียงข้อมูลให้เรียงลำดับตามเงื่อนไขที่กำหนดไว้ โดยอาจเรียงจากน้อยไปมาก หรือค่ามากไปน้อยก็ได้ การเรียงลำดับข้อมูลในระบบคอมพิวเตอร์ จะแบ่งเป็น 2 ลักษณะใหญ่ ๆ คือ 1. การจัดเรียงลำดับข้อมูลภายใน (Internal sorting) ใช้กับข้อมูลที่มีจำนวนไม่ใหญ่กว่าเนื้อที่ในหน่วยความจำ (main memory) ไม่ต้องใช้หน่วยความจำสำรอง เช่น ดิสก์, เทป เป็นต้น 2. การเรียงลำดับข้อมูลภายนอก (External sorting) ใช้กับข้อมูลที่มีจำนวนใหญ่เกินกว่าที่จะเก็บลงในหน่วยความจำได้หมดภายในครั้งเดียว จะใช้หน่วยความจำภายนอก เช่น ดิสก์, เทป สำหรับเก็บข้อมูลบางส่วนที่ได้รับการเรียงลำดับข้อมูลแล้ว แล้วจึงค่อยจัดการเรียงลำดับข้อมูลในส่วนต่อไป ประเภทของการเรียงลำดับข้อมูล 1. Insertion Sort การจัดเรียงแบบแทรก คือ การเรียงข้อมูลโดยนำข้อมูลที่จะทำการจัดเรียงนั้นๆ ไปจัดเรียงทีละตัว โดยการแทรกตัวที่จะเรียงไว้ในตำแหน่งที่เหมาะสมของข้อมูลที่มีการจัดเรียงเรียบร้อยแล้ว ณ ตำแหน่งที่ถูกต้อง ขั้นตอนการทำงาน เปรียบเที
Asymptotic notation คือเครื่องหมายที่ใช้อธิบายการเติบโตของฟังก์ชันในการวิเคราะห์อัลกิริทึมจะนำเครื่องหมายนี้มาใช้ในการระบุประสิทธิภาพของอัลกริทึม โดยมีหลายสัญลักษณ์ดังนี้ 1. Big-O Notation : O บิ๊ก-โอ ใช้ในการระบุทรัพยากรที่ใช้ในการทำงานของอัลกอริทึมเมื่อมีขนาดของอินพุทเปลี่ยนไป ปกติแล้วทรัพยากรดังกล่าวจะหมายถึงเวลานั่นคือ ความสัมพันธ์ระหว่าง เวลา กับ ขนาดของอินพุท หรืออินพุทที่ขนาดใดขนาดหนึ่ง เวลาที่ใช้ในการทำงานมากที่สุด (Upper bound) จะเป็นเท่าไร ซึ่งฟังก์ชันบิ๊ก-โอเป็นที่นิยมใช้มากที่สุดในการระบุประสิทธิภาพของอัลกอริทึม ตัวอย่าง O(n) คือฟังก์ชันที่ใช้เวลาทำงานช้าที่สุด ≤ n เช่น อัลกอริทึม A มีประสิทธิภาพเป็น O( n 2 ) ถ้า n = 10 แล้ว ฟังก์ชัน A จะใช้เวลาทำงานช้าที่สุด 100 หน่วยเวลา (อาจจะเร็วกว่า100ได้ แต่ช้าสุดไม่เกิน100) จะเขียนได้ว่า f(n) є O(g(n)) เพื่อบอกว่า f(n) เป็นฟังก์ชันที่ไม่โตเร็วกว่า g(n) f(n) є O(g(n)) f(n) ≤ (g(n)) 2. Big-Omega Notation : Ω โอเมก้าใหญ่ ใช้สำหรับบอกถึงเวลาที่ใช้น