Quick
sort
วิธีนี้เป็นการเรียงที่ใช้กับข้อมูล หรือตารางที่มีขนาดใหญ่
โดยจะมีหลักการง่าย ๆ คือ ใช้เรคอร์ดหรือคีย์พิเศษตัวหนึ่งเป็นตัวแบ่ง
โดยให้ ข้อมูลแบ่งออกเป็น 2 ส่วน คือ ส่วนแรกจะมีค่ามากกว่าคีย์ใหญ่
เป็นพิเศษนี้โดยจะอยู่ข้างขวา และส่วนจะน้อยกว่าคีย์นี้จะอยู่ทางซ้าย
จากนั้นแต่ละส่วนก็แบ่งออกเป็น
2 ส่วนย่อย ๆ ทำเช่นนี้ไปเรื่อย ๆ ก็จะได้ข้อมูลที่เรียงออกมา ตัวอย่างเช่น
42 23 74 11
65 58 94 36
99 87
เราจะใช้ตัวแปรอินเด็กซ์ i กับ j ซึ่งจะให้ค่าเริ่มต้นเป็น 2 และ 10 ตามลำดับ
เพราะเราจะใช้คีย์ตัวแรกในการเปรียบเทียบ ( ในตัวอย่าง นี้คือ
42 ) โดยมีเงื่อนไขว่าถ้า item < 42 แล้ว i จะเพิ่มอีก 1
ทำจนกระทั่ง item >= 42 (อย่าลืม! จะต้องมีการจำค่า i นี้ด้วย ) แล้วจึงเปรียบ
เทียบ item กับ 42 โดยให้ลดค่า j ลงทีละ 1 จนกว่า item < = 42
จะได้ i ชี้อยู่ที่ item[i] และ j ชี้อยู่ท ี่item[j]
(ในที่นี้คือ 74 และ 36 )จากนั้นก็ ทำการสลับค่ากัน
ทำเช่นนี้ไปเรื่อย ๆ จนกว่า i >= j จึงทำการเปรียบเทียบกันครั้งสุดท้าย
และถ้าคีย์นั้นน้อยกว่าคีย์ตัวแรก (42) ก็สลับที่ด้วย 42 กับ 11 )
ข้อมูลทั้งสองส่วนจะถูกขั้นด้วยคีย์พิเศษนั้น (42 ) ซึ่งคือ
[ 11,23,36 ] และ [ 65,58,94,74,99,87 ] และเมื่อนำข้อมูลทั้งสองส่วนนี้มาทำตาม
กระบวนข้างต้น ( แบ่งข้อมูลออกเป็นสองส่วนโดยวิธีการเรียกใช้ตนเอง : recursive )
จนกว่าจะเหลือเพียงตัวเดียว เราก็จะได้ข้อมูลที่เรียงไว้เรียบร้อยแล้ว
ตัวอย่างโปรแกรมของ
Quick sort