CoE KKU

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

• อัลกอริทึมอย่างง่ายสำหรับการจัดเรียงค่าที่ใช้เวลาเป็น $O(N^2)$ เช่น insertion sort
• อัลกอริทึมที่ค่อนข้างง่ายที่มี running time เป็น $o(N^2)$ คือ Shellsort
• อัลกอริทึมที่ซับซ้อนขึ้นที่มี running time $O(N\ log\ N)$