การจัดเรียงแบบ Quick Sort

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²)

o    ใช้วิธีสุ่มเลขแบบ Random มีข้อเสียคือ อัลกอริธึมการสร้างเลขสุ่มเสียเวลาค่อนข้างนาน

เราจะเลือก Pivot โดยใช้วิธี Median-of-Threee คือเลือกเลขตัวที่ 1 ตัวสุดท้าย และตัวตรงกลางขึ้นมา และหาค่า Median ของเลข 3 ตัวนี้ เช่นในตัวอย่างข้างต้นเราจะได้ Pivot ดังนี้

เมื่อรู้แล้วว่า ตำแหน่งที่ 4 (คือค่า 6) เป็น Pivot เราจะสลับ Pivot กับตำแหน่งสุดท้าย เพื่อกันเลขที่เป็น Pivot ไว้ก่อน ดังนี้

เราจะให้มีตัวแปรจำนวนเต็ม 2 ตัวคือ i กับ j โดย i ใช้สแกนหาเลขที่มากกว่า 6 เพื่อสลับไปด้านขวา ส่วน j ใช้สแกนหาเลขที่น้อยกว่า 6 เพื่อสลับกลับมาด้านซ้าย

เมื่อไรก็ตามที่ i > j คือ i สแกนไปด้านขวาจนกระทั่งเลยตำแหน่งของ j ออกไป เราจะถือว่าหยุดได้ และจะมีเลขที่น้อยกว่า 6 อยู่ด้านซ้ายทั้งหมด และมีเลขที่มากกว่า 6 อยู่ด้านขวาทั้งหมด

จากภาพเริ่มต้น i จะชี้ไว้ที่ตำแหน่งซ้ายสุดคือ 0 และ j จะชี้ที่ตำแหน่งขวาสุดคือ 8 (ไม่นับตำแหน่งที่ 9 ที่กันไว้สำหรับวาง Pivot) และสุดท้ายถ้าการสแนกเพื่อแยกกลุ่มทำเสร็จ เราจะได้เลขกลุ่มด้านซ้าย เป็นเลขที่ < 6 ทั้งหมด และได้กลุ่มด้านขวา เป็นเลขที่มีค่า > 6 ทั้งหมด

เริ่มต้นสแกน i = 0, j = 8

o    จะพบว่า a[i] = 8 ซึ่ง > 6 ดังนั้นหยุดตัว i ไว้ที่ตำแหน่งนี้ก่อน

o    จะพบว่า a[j] = 7 ซึ่ง > 6 ดังนั้นต้องเลื่อน j ลงอีก 1 ตำแหน่ง ดังนี้

ณ ตำแหน่ง i = 0, j = 7

o    สำหรับ a[i] เราได้ตำแหน่ง i ที่ > 6 แล้วหยุดไว้แค่นั้น

o    จะพบว่า a[j] = 2 ซึ่ง 2 < 6 ดั้งนั้น ถือว่าเราเจอตัวที่ a[j] < 6 แล้ว เราจะหยุด j ไว้ที่ตำแหน่งนี้

สลับค่าตำแหน่งที่ a[i] กับ a[j] จะได้ผลลัพธ์ดังภาพ

เลื่อน i มาทางขวาอีก 1 ตำแหน่ง และเลื่อน j มาทางซ้ายอีก 1 ตำแหน่ง ขณะนี้ i = 1, j = 6

ณ ตำแหน่งที่ i = 1, j = 6

o    ค่า a[i] = 1 ซึ่ง 1 < 6 ดังนั้นต้องเลื่อน i ไปอีก 1 ตำแหน่ง

ณ ตำแหน่งที่ i = 2, j = 6

o    ค่า a[i] = 4 ซึ่ง 4 < 6 ดังนั้นต้องเลื่อน i ไปอีก 1 ตำแหน่ง

ณ ตำแหน่งที่ i = 3, j = 6

o    ค่า a[i] = 9 ซึ่ง 9 > 6 ดังนั้นหยุด i ไว้ที่ตำแหน่งนี้

ย้ายไปดูทางตัว j ได้ ตอนนี้ j = 6

o    ค่า a[j] = 5 ซึ่ง 5 < 6 ดังนั้นหยุด j ไว้ที่ตำแหน่งนี้ (เตรียมสลับ)

สลับค่า a[i] กับ a[j] ค่า 9 กับ 5 จะสลับกันตามภาพนี้

เสร็จแล้วเลื่อน i ไปด้านขวาอีก 1 ตำแหน่ง แล้วสแกนต่อ

ณ ตำแหน่งที่ i = 4

o    a[i] = 0 ซึ่ง 0 < 6 ดังนั้นเลื่อน i ต่อไป

ณ ตำแหน่งที่ i = 5

o    a[i] = 3 ซึ่ง 3 < 6 ดังนั้นเลื่อน i ต่อไป

ณ ตำแหน่งที่ i = 6

o    a[i] = 9 ซึ่ง 9 > 6 ดังนั้นหยุด i ไว้ที่ตำแหน่งนี้

กลับมาดูด้านตัว j เราจะสแกน j ต่อ โดยเลื่อน j ไปด้านซ้ายอีก 1 ตำแหน่ง ดังนี้

ณ ตำแหน่งที่ j = 5 (i หยุดแล้ว)

o    a[j] = 3 ซึ่ง 3 < 6 ดังนั้นเราหยุด j ไว้ที่ตำแหน่งนี้

ถึงตอนนี้ทั้ง i และ j หยุดสแกน จริงๆเราจะต้องสลับค่าในตำแหน่ง i กับ j แต่ปรากฏว่าตอนนี้ i ได้กระโดดข้าม j ไปแล้ว จึงถือว่าเสร็จสิ้นการแบ่งกลุ่ม และได้กลุ่มมา 2 กลุ่ม ดังนี้

ให้สลับค่า Pivot กับตำแหน่งที่ i จะทำให้ได้กลุ่มที่สมบูรณ์ที่มี Pivot เป็นตัวคั่นกลางพอดีดังนี้

เมื่อมาถึงจุดนี้ เราจะเสร็จสิ้นการแบ่งกลุ่มรอบที่ 1 โดยมี 6 เป็นตัว Pivot

รอบที่ 2

รอบที่ 2 เราจะนำกลุ่มแรกตั้งตัวที่ 0 ถึง 5 ไปทำ Quick Sort ซ้ำเหมือนเดิม โดยเริ่มต้นหา Median-of-Three ของ 2, 3, 4 จะได้ Median เป็นค่า 3 ณ ตำแหน่งที่ 5 ดังนี้

หมายเหตุ – ส่วนกลุ่มขวามือ เรายังไม่สนใจ รอไว้ทำรอบที่ 3

นำค่าที่ตำแหน่ง Pivot ไปไว้ท้ายสุด (ในที่นี้อยู่ท้ายสุดอยู่แล้ว) และเริ่มปักหมุด i กับ j เพื่อสแกน แบ่งกลุ่มได้

ด้านตัว i ณ ตำแหน่ง i = 0

o    a[0] = 2 ซึ่ง 2 < 3 ดังนั้น เลื่อน i ต่อไป เป็น i = 1

o    a[1] = 1 ซึ่ง 1 < 3 ดังนั้น เลื่อน i ต่อไป เป็น i = 2

o    a[2] = 4 ซึ่ง 4 > 3 ดังนั้น หยุดตัว i ไว้ที่ i = 2

ด้านตัว j ณ ตำแหน่ง j = 4

o    a[4] = 0 ซึ่ง 0 < 3 ดังนั้น หยุดตัว j ไว้ที่ j = 4

สลับที่ i กับ j จะได้ภาพดังนี้

ด้านตัว i เลื่อน i อีก 1 ตำแหน่งเป็น i = 3

ณ ตำแหน่งที่ i = 3

o    a[3] = 5 ซึ่ง 5 > 3 เราหยุดตัว i ไว้ที่ตำแหน่งนี้

ด้านตัว j เลื่อน j อีก 1 ตำแหน่งเป็น j = 3

ณ ตำแหน่งที่ j = 3

o    a[3] = 5 ซึ่ง 5 > 3 ดังนั้น เลื่อน j ต่อไป เป็น j = 2

o    a[2] = 0 ซึ่ง 0 < 3 ดังนั้น หยุด j ไว้ที่ตำแหน่งนี้

ปรากฏว่าตอนนี้ i กระโดดข้าม j ไปแล้ว ดังนั้นเราหยุดการแบ่งกลุ่มได้ และสลับ Pivot กับ i จะได้กลุ่มออกมา 2 กลุ่มดังนี้

รอบที่ 3

เราจะทำ Quick Sort เฉพาะที่ตำแหน่ง 0 ถึง 2 โดยหา Median-of-Three ได้เป็น 1 และสลับไปอยู่ที่ท้ายสุด ดังนี้

ด้านตัว i

a[0] = 2 ซึ่ง 2 > 1 ดังนั้นหยุด i ไว้ตรงนี้

ด้านตัว j

a[1] = 0 ซึ่ง 0 < 1 ดังนั้นหยุด j ไว้ตรงนี้

สลับค่าที่ i กับ j จะได้ภาพเป็นดังนี้

ด้านตัว i เลื่อน i ไปอีก 1

ที่ตำแหน่ง i = 1 จะเลื่อน i ไปอีก 1 ไม่ได้ เนื่องจากสุดขอบเขตข้อมูลแล้ว จึงไปดูที่ตัว j แทน

ด้านตัว j เราเลื่อน j ไปอีก 1 ที่ j = 0

ที่ j = 0

              a[0] = 0 ซึ่ง 0 < 1 ดังนั้น หยุด j ไว้ที่ตำแหน่งนี้

ณ จุดนี้ i ได้กระโดดข้าม j ไปแล้ว ดังนั้น เราจึงหยุดการแบ่งกลุ่ม และสลับค่า i กับ Pivot จะได้ภาพดังนี้

รอบที่ 4

เราจะทำ Quick Sort ที่ตำแหน่ง 0 ถึง 0 ซึ่งมีเลขเพียง ตัวเดียวคือ 0 ดังนั้น Quick Sort จึงหยุด

รอบที่ 5

เราจะทำ Quick Sort ที่ตำแหน่ง 2 ถึง 2 ซึ่งมีเลขเพียง ตัวเดียวคือ 2 ดังนั้น Quick Sort จึงหยุด

รอบที่ 6

เราจะไปทำกลุ่มด้านขวาของ Pivot 3 ซึ่งก็คือตำแหน่งที่ 4 ถึง 5

หาค่า Median-of-Three ได้เป็น 4,4,5 คือ 4 เรานำ 4 ไปไว้ที่ข้างท้ายได้เป็นดังนี้

ที่ i = 4

a[4] = 5 ซึ่ง 5 > 4 เราหยุด i ไว้ที่ตรงนี้

ที่ j = 4

a[4] = 5 ซึ่ง 5 > 4 เราเลื่อน j ไปอีก 1 ตำแหน่ง

ที่จุดนี้ i กระโดดข้าม j ไปแล้ว เราหยุดการแบ่งกลุ่มและสลับค่า i กับ Pivot จะได้ดังนี้

รอบที่ 7

เราจะทำ Quick Sort ที่ตำแหน่ง 5 ถึง 5 ซึ่งมีเลขเพียงตัวเดียวคือ 5 ดังนั้นหยุด Quick Sort ได้

รอบที่ 8

เราจะทำ Quick ที่กลุ่มด้านขวาของ 6 ตั้งแต่ 7 ถึง 9 โดยหา Median-of-Three ได้เป็น 8 และนำไปวางไว้ที่ตำแหน่งท้ายสุดดังนี้

ด้านตัว i ณ ตำแหน่ง i = 7

o    a[7] = 9 ซึ่ง 9 > 8 ดังนั้นหยุด i ไว้ที่ตรงนี้

ด้านตัว j ณ ตำแหน่ง j = 8

o    a[8] = 7 ซึ่ง 7 < 8 ดังนั้นหยุด j ไว้ที่ตรงนี้

สลับค่าตำแหน่งที่ i กับ j จะได้ภาพดังนี้

เลื่อน i ไปอีก 1 ที่ i = 8

o    a[8] = 9 ซึ่ง 9 > 8 ดังนั้นหยุด i ไว้ที่ตรงนี้

ด้านตัว j เลื่อน j ไปอีก 1

o    ปรากฏว่า i กระโดดข้าม j ไปแล้ว ให้หยุดการแบ่งกลุ่มได้

สลับค่าตำแหน่งที่ i กับ Pivot จะได้ภาพดังนี้

รอบที่ 9

เราจะทำ Quick Sort ที่ตำแหน่ง 7 ถึง 7 ซึ่งมีเลขตัวเดียวคือ 7 ดังนั้นหยุด Quick Sort

รอบที่ 10

เราจะทำ Quick Sort ที่ตำแหน่ง 9 ถึง 9 ซึ่งมีเลขตัวเดียวคือ 9 ดังนั้นหยุด Quick Sort

เสร็จสิ้นกระบวนการ Quick Sort เราจะได้เลขที่เรียงลำดับกันแล้วดังนี้

โดยที่แสดงสีเข้มคือตำแหน่ง Pivot ที่เกิดขึ้นที่รอบการทำงานแต่ละรอบ