Quick Sort

ตัวอย่างโจทย์

6
5
7
3
9
4
1
10
8
2

 

เริ่มต้นต้องหาค่า Pivot ก่อน เพื่อนำมาใช้เป็นค่ากลางในการเปรียบเทียบกับค่าิอื่นค่า Pivot จริงๆแล้วจะเิป็นค่าใดๆก็ได้ในตัวอย่าง แต่ในที่นี้จะใช้วิธีหาค่ากลางของจำนวน 3 ตัวแรก จาก 6 5 7 เมื่อนำมาเรียงจะได้เป็น 5 6 7 ค่ากลางคือ 6 ดังนั้น เราจะนำ 6 มาเป็นค่า Pivot

ขั้นที่ 1. นำค่า Pivot ไปไว้หลังสุด

สลับตำแหน่ง Pivot กับตำแหน่งสุดท้ายของโจทย์

 
2
5
7
3
9
4
1
10
8
6
i ->
<- j

 

ขั้นที่ 2. วิ่งหาค่า i และ j

สมมุติ ค่า i คือ จำนวนที่มีค่ามากกว่าค่า Pivot

สมมุต ค่า j คือ จำนวนที่มีค่าน้อยกว่าค่า Pivot

ให้เริ่มหาค่า i จากทางซ้ายมือ และหาค่า j จากทางขวามือ (นับจากค่า pivot) จะเห็นว่า ในโจทย์นี้ ค่าที่มากกว่า 6 (pivot) จากทางซ้ายมือคือ 7 และค่าที่น้อยกว่า 6 (pivot) จากทางขวามือคือ 1
2
5
7
3
9
4
1
10
8
6
i
j

 

ขั้นที่ 3. สลับค่าใน i และ j

สลับค่าใน i และ j ดังนั้น ค่าในตำแหน่ง i จะกลายเป็น 1 และค่าในตำแหน่ง j จะกลายเป็น 7 แทน

 
2
5
1
3
9
4
7
10
8
6
i ->
<- j

ขั้นที่ 4. วิ่งหาค่า i และ j ในตำแหน่งถัดไป

จากโจทย์จะเห็นว่า ถัดจากตำแหน่ง i มาก็จะมีเลข 9 ที่มีค่ามากกว่า pivot และที่ตำแหน่ง j เมื่อวิ่งเข้ามาก็จะเจอ 4 ซึ่งมีค่าน้อยกว่า pivot

 
2
5
1
3
9
4
7
10
8
6
i
j

ขั้นที่ 5. สลับค่าใน i และ j

สลับค่าใน i และ j ดังนั้น ค่าในตำแหน่ง i จะกลายเป็น 4 และค่าในตำแหน่ง j จะกลายเป็น 9 แทน

 
2
5
1
3
4
9
7
10
8
6
i ->
j

 

ขั้นที่ 6. เมื่อตำแหน่งของ i และ j มาเจอกัน ให้หาตำแหน่ง i ต่อไปเพียงอย่างเดียว

จากโจทย์จะเห็นว่า เมื่อ i วิ่งต่อไป จะเจอ 9 ที่มีค่ามากกว่า pivot
2
5
1
3
4
9
7
10
8
6
i

 

ขั้นที่ 7. สลับตำแหน่ง i กับ Pivot

ดังนั้น ที่ตำแหน่ง i ก็จะกลายเป็น 6 และที่ตำแหน่ง pivot จะกลายเป็น 9

 
2
5
1
3
4
6
7
10
8
9

 

ขั้นที่ 8. แบ่งครึ่ง !!

หลังจากที่ Pivot ถูกสลับมาแล้ว จะเห็นว่าโจทย์จะสามารถแบ่งออกไ้ด้เป็น 2 ส่วน คือ 2 5 1 3 4 และ 7 10 8 9 จากนี้เราจะทำการเรียงอย่างข้างต้นใหม่อีกครั้ง แต่จะเป็นการเรียงทีละข้าง โดยเริ่มจากทางด้านซ้ายก่อน ดังนี้

8.1 หาค่า Pivot

โดยเอามาจากค่ากลางของ 3 ตำแหน่งแรก 2 5 1 เมื่อนำมาเรียงจะได้เป็น 1 2 5 ดังนั้นค่ากลางคือ 2 เราจึงใช้ 2 เป็นค่า pivot

 
2
5
1
3
4
6
7
10
8
9

 

8.2 สลับค่า Pivot กับตำแหน่งสุดท้าย

ตำแหน่งสุดท้ายในที่นี้คือ 4

 
4
5
1
3
2
6
7
10
8
9

 

8.3. วิ่งหาค่า i และ j

สมมุติ ค่า i คือ จำนวนที่มีค่ามากกว่าค่า Pivot

สมมุต ค่า j คือ จำนวนที่มีค่าน้อยกว่าค่า Pivot

ให้เริ่มหาค่า i จากทางซ้ายมือ และหาค่า j จากทางขวามือ (นับจากค่า pivot) จะเห็นว่า ในโจทย์นี้ ค่าที่มากกว่า 2 (pivot) จากทางซ้ายมือคือ 4 และค่าที่น้อยกว่า 2 (pivot) จากทางขวามือคือ 1

 
4
5
1
3
2
6
7
10
8
9
i
j

 

8.4.สลับค่าใน i และ j

สลับค่าใน i และ j ดังนั้น ค่าในตำแหน่ง i จะกลายเป็น 1 และค่าในตำแหน่ง j จะกลายเป็น 4 แทน

 
1
5
4
3
2
6
7
10
8
9
i ->
<- j

 

8.5 เมื่อ i และ j วิ่งต่อไปตำแหน่งของ i และ j จะมาเจอกัน ให้หาตำแหน่ง i เพียงอย่างเดียว

จากโจทย์จะเห็นว่า เมื่อ i วิ่งต่อไป i จะไปอยู่ที่ตำแหน่งเลข 5 แต่ j เมื่อวิ่งต่อไปจะเลยตำแหน่งของ i ไปตกอยู่ที่ตำแหน่งเลข 1 ดังนั้นเราจึงใช้เฉพาะ i ที่มีค่ามากกว่า pivot

 
1
5
4
3
2
6
7
10
8
9
i

 

8.6. สลับตำแหน่ง i กับ Pivot

ดังนั้น ที่ตำแหน่ง i ก็จะกลายเป็น 2และที่ตำแหน่ง pivot จะกลายเป็น 5

 

1
2
4
3
5
6
7
10
8
9

 

8.7 แบ่งครึ่ง !!

หลังจากที่ Pivot ถูกสลับมาแล้ว จะเห็นว่าโจทย์จะสามารถแบ่งออกไ้ด้เป็น 2 ส่วน คือ 1 และ 4 3 5 จากนี้เราจะทำการเรียงอย่างข้างต้นใหม่อีกครั้ง แต่จะเป็นการเรียงทีละข้าง โดยจะทำที่ด้านขวาเพราะทางซ้ายจะเห็นได้ว่าเรียงถูกต้องแล้วจึงขอข้ามไป

8.7.1 หาค่า Pivot

โดยเอามาจากค่ากลางของ 3 ตำแหน่งแรก 4 3 5 เมื่อนำมาเรียงจะได้เป็น 3 4 5 ดังนั้นค่ากลางคือ 4 เราจึงใช้ 4 เป็นค่า pivot

 
1
2
4
3
5
6
7
10
8
9

 

8.7.2 สลับค่า Pivot กับตำแหน่งสุดท้าย

ตำแหน่งสุดท้ายในที่นี้คือ 5

 
1
2
5
3
4
6
7
10
8
9

 

8.7.3. วิ่งหาค่า i และ j

สมมุติ ค่า i คือ จำนวนที่มีค่ามากกว่าค่า Pivot

สมมุต ค่า j คือ จำนวนที่มีค่าน้อยกว่าค่า Pivot

ให้เริ่มหาค่า i จากทางซ้ายมือ และหาค่า j จากทางขวามือ (นับจากค่า pivot) จะเห็นว่า ในโจทย์นี้ ค่าที่มากกว่า 4(pivot) จากทางซ้ายมือคือ 5 และค่าที่น้อยกว่า 4 (pivot) จากทางขวามือคือ 3

 
1
2
5
3
4
6
7
10
8
9
i
j

 

8.7.4.สลับค่าใน i และ j

สลับค่าใน i และ j ดังนั้น ค่าในตำแหน่ง i จะกลายเป็น 3 และค่าในตำแหน่ง j จะกลายเป็น 5 แทน

 
1
2
3
5
4
6
7
10
8
9
i ->
<- j

 

8.7.5 เมื่อ i และ j วิ่งต่อไปตำแหน่งของ i และ j จะมาเจอกัน ให้หาตำแหน่ง i เพียงอย่างเดียว

จากโจทย์จะเห็นว่า เมื่อ i วิ่งต่อไป i จะไปอยู่ที่ตำแหน่งเลข 5 แต่ j เมื่อวิ่งต่อไปจะเลยตำแหน่งของ i ไปตกอยู่ที่ตำแหน่งเลข 3 ดังนั้นเราจึงใช้เฉพาะ i ที่มีค่ามากกว่า pivot

 
1
2
3
5
4
6
7
10
8
9
i
8.7.6. สลับตำแหน่ง i กับ Pivot

ดังนั้น ที่ตำแหน่ง i ก็จะกลายเป็น 4 และที่ตำแหน่ง pivot จะกลายเป็น 5

 
1
2
3
4
5
6
7
10
8
9

 

8.7.7 แบ่งครึ่ง !!

หลังจากที่ Pivot ถูกสลับมาแล้ว จะเห็นว่าโจทย์จะสามารถแบ่งออกไ้ด้เป็น 2 ส่วน คือ 3 และ 5 จะเห็นว่าทั้ง 2 ข้างเรียงถูกต้องแล้ว เราจะกลับไปดูที่หัวข้อที่ 8 ใหม่ ถ้ายังจำได้ ด้านขวาของ pivot 6 คือ 7 10 8 9 ยังไม่ถูกสลับ คราวนี้เราจะมาทำที่ข้างนี้บ้าง

9. หาค่า Pivot

โดยเอามาจากค่ากลางของ 3 ตำแหน่งแรก 7 10 8 เมื่อนำมาเรียงจะได้เป็น 7 8 10 ดังนั้นค่ากลางคือ 8 เราจึงใช้ 8เป็นค่า pivot

 
1
2
3
4
5
6
7
10
8
9

 

10 สลับค่า Pivot กับตำแหน่งสุดท้าย

ตำแหน่งสุดท้ายในที่นี้คือ 9

 
1
2
3
4
5
6
7
10
9
8

 

11. วิ่งหาค่า i และ j

สมมุติ ค่า i คือ จำนวนที่มีค่ามากกว่าค่า Pivot

สมมุต ค่า j คือ จำนวนที่มีค่าน้อยกว่าค่า Pivot

ให้เริ่มหาค่า i จากทางซ้ายมือ และหาค่า j จากทางขวามือ (นับจากค่า pivot) จะเห็นว่า ในโจทย์นี้ ค่าที่มากกว่า 8 (pivot) จากทางซ้ายมือคือ 10 และค่าที่น้อยกว่า 8 (pivot) จากทางขวามือคือ 7

12 เมื่อตำแหน่งของ i และ j จะมาเจอกัน ให้หาตำแหน่ง i เพียงอย่างเดียว

จากโจทย์จะเห็นว่า i และ j ชนกัน(สลับกัน) i อยู่ที่ตำแหน่งเลข 10 แต่ j เมื่อวิ่งจะเลยตำแหน่งของ i ไปตกอยู่ที่ตำแหน่งเลข 7 ดังนั้นเราจึงใช้เฉพาะ i ที่มีค่ามากกว่า pivot

 
1
2
3
4
5
6
7
10
9
8
i

 

13. สลับตำแหน่ง i กับ Pivot

ดังนั้น ที่ตำแหน่ง i ก็จะกลายเป็น 8 และที่ตำแหน่ง pivot จะกลายเป็น 10

 
1
2
3
4
5
6
7
8
9
10

14. แบ่งครึ่ง !!

จะเห็นได้ว่าเมื่อแบ่งครึ่งแล้วทั้งสองด้านของ pivot 8 นั้นเรียงถูกต้องแล้ว จึงเป็นอันเสร็จการเรียง QuickSort

ถ้าสังเกตให้ดี จะจับจุดได้ว่า ค่า pivot เอาไว้สำหรับสลับให้ค่าน้อยอยู่ทางซ้าย ค่ามากอยู่ทางขวา ถ้าเข้าใจประเด็นก็จะเข้าใจไ้้ด้ไม่ยากค่ะ

 

Sign GuestBook