การจัดเรียงข้อมูล (sorting)
อาจารย์สุวิชยะ รัตตะรมย์
สำนักวิชาเทคโนโลยีสารสนเทศและการสื่อสาร
หัวข้อวันนี้
2
Quick sort
3
Quick sort
4
5
6
(a[1] , a[2] , … , a[p] … , a[p-1] , a[n])
กลุ่มของข้อมูลที่มีค่าน้อยกว่า pivot
กลุ่มของข้อมูลที่มีค่ามากกว่า pivot
pivot ( a[p] )
quick sort
quick sort
quick sort
…
…
7
(4 , 10 , 2 , 6 , 5 , 8 , 7 , 3 , 9 , 1)
(4 , 2 , 3, 1)
( 10 , 6 , 8 , 7 , 9)
(1)
(4 , 3)
(6 , 7)
(10 , 9)
(5)
(2)
(3)
(4)
(-)
(8)
(-)
(6)
(7)
(9)
(10)
(-)
(1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10)
Quick sort : Choose the pivot
8
9
( ข้อมูลเริ่มต้น 10 ตัว )
(9 ตัว)
(8 ตัว)
pivot
pivot
(...)
pivot
(1 ตัว)
pivot
ทำ quick sort 9 ครั้ง
ตัวอย่างการเลือก pivot ที่ไม่ดี
เลือก pivot ที่แบ่งข้อมูลแล้วส่วนใดส่วนหนึ่งไม่มีข้อมูล – pivot เป็นข้อมูลที่มีค่ามากหรือน้อยที่สุด
10
( ข้อมูลเริ่มต้น 10 ตัว )
(4 ตัว)
(5 ตัว)
(2ตัว)
(2 ตัว)
pivot
pivot
ตัวอย่างการเลือก pivot ที่ดี
(1ตัว)
pivot
(1ตัว)
pivot
(2 ตัว)
(1ตัว)
pivot
(1ตัว)
pivot
ทำ quick sort 6 ครั้ง
เลือก pivot ที่แบ่งข้อมูลออกเป็น 2 ส่วนที่เท่ากัน, เกือบเท่ากัน
11
pseudo code ของ quick sort
function QuickSort (data A, int Lb, int Ub) {
if Lb < Ub then {
pivot = Partition (A, Lb, Ub)
QuickSort (A, Lb, pivot - 1)
QuickSort (A, pivot + 1, Ub)
}
}
function Partition (data A, int Lb, int Ub) {
select a pivot from A[Lb]...A[Ub]
reorder A[Lb]...A[Ub] such that :
all values to the left of the pivot are < pivot
all values to the right of the pivot are >= pivot
return pivot position
}
12
13
function Partition (data A, int Lb, int Ub) {
// p_pos = (Lb+Ub) / 2
// swap (a[Lb],a[p_pos])
p_pos = Lb
pivot = a[Lb]
for ( i = Lb + 1 ; i <= Ub ; i++ ) {
if (a[i] < pivot) {
p_pos++
swap (a[i] , a[p_pos])
}
}
swap (a[Lb] , a[p_pos])
return p_pos
}
14
ตัวอย่าง
ในกรณีที่เลือกค่ากึ่งกลางพาร์ทิชันเป็น pivot
การวิเคราะห์อัลกอริทึม
15