Closet pairs and merge sort

ข้อสังเกต1:ถ้ามีคู่ของจุด $P_{L},P_{R}\,$ คู่ที่อยู่ใกล้กันกว่าระยะทาง $d'=min\{d_{L},d_{R}\}\,$ หมายความว่า จุดทั้งสองจะต้องอยู่ในแถบ $[x'-d',x'+d']\,$ เท่านั้น ดังภาพ

ข้อสังเกต 2: ถ้าสมมติดว่าแบ่งแถบ $[x'-d',x'+d']\,$ ออกเป็นช่อง ๆ แต่ละช่องมีความกว้างและความยาวเป็น $d'/2\,$ ดังภาพ

ข้อสังเกต 3: ถ้ามีจุด $P_{L},P_{R}\,$ ที่อยู่ใกล้กัน เป็นระยะห่างน้อยกว่า $d'\,$ และจะมีตารางขนาด 4 x 4 ที่แต่ละช่องมีความกว้าง $d'/2\,$ ที่ $P_{L},P_{R}\,$ อยู่ในตารางนั้นเสมอ ดังภาพ

ข้อสังเกต 4: ถ้านำเซต $L\,$ และเซต $R\,$ มารวมกัน แล้วคัดเฉพาะจุดที่อยู่ในแถบ $[x'-d',x'+d']\,$ จากนั้นเรียงจุดที่คัดมาจากน้อยไปมากใส่ใน array ชื่อ P ตามแนวแกน y แล้ว ถ้า $P[i]\,$ และ $P[j]\,$ เป็นคู่ที่อยู่ใกล้กันเป็นระยะห่างน้อยกว่า $d\,$ และ $i<j\,$ แล้ว $j\leq i+15\,$

ดังนั้นถ้า สมมติว่าเรียงจุดตามที่กำหนดไว้ข้างต้น หาจุดที่อยู่ใกล้กันเป็นระยะห่างน้อยกว่า $d'\,$ ได้ในเวลา $15n\,$

Closet_Pairs(p,n)

if n <= 1

return d= \infinity

else if n = 2

return d(P[0],P[1]) // ระยะทางระหว่างสองจุดนั้น

else

k <-- n/2 // เวลาการทำงานส่วนนี้คือ O(1)

L<--(P[0], P[1], P[2], ..., P[k-1]) // เวลาการทำงานส่วนนี้คือ O(n)

R<--(P[k], P[k+1], P[k+2], ..., P[n-1]) // เวลาการทำงานส่วนนี้คือ O(n)

d_L, P_L[0], P_L[1] <-- Closet_Pair(L, k) // เวลาการทำงานส่วนนี้คือ T(n/2)

d_R, P_R[0], P_R[1] <-- Closet_Pair(R, n-k) // เวลาการทำงานส่วนนี้คือ T(n/2)

P' <-- Merge(L', R') // ตามแนวแกน y , เวลาการทำงานส่วนนี้คือ O(n)

d' <-- min (d_R, d_L) // เวลาการทำงานส่วนนี้คือ O(n)

P <- จุดใน P' ที่อยู่ในช่วง [x'-d',x'+d'] // เวลาการทำงานส่วนนี้คือ O(n)

for i = o to n-16 // loop for นี้มีเวลาการทำงาน O(n)

for j = i to i+15

if d(P[i],P[j]) < d' // ถ้าระยะห่างระหว่าง P[i] กับ P[j] น้อยกว่า d'

d'<-- d[P[i],P[j])

return d', คู่ของจุดที่อยู่ใกล้กันที่สุด, P'

Partition (a, l, r, x)

k <-- l

for i=l to r

if a[i] <= x

swap(a[i],a[k])

k <-- k +1

return k

Quicksort (a, l, r)

if r-l+1 <= 1

ไม่ต้องทำอะไร

else

x <-- choose pivot (a, l, r)

l <-- partition (a, l, r, x)

Quicksort (a, l, k-1)

Quicksort (a, k, r)

วิธีการเลือก pivot

1. เลือกตัวแรก x<-- a[l]

2. เลือกตัวสุดท้าย x<-- a[r]

3. tri-median ค่าตัวกลางของ a[l], a[r], a[(l+r)/2]

4. สุ่ม p<-- random (l, r)

x <-- a[p]

ให้ $T(n)\,$ เวลาการทำงานของ Quicksort เมื่อ $r-l+1=n\,$

$T(n)=O(1)\,$ เมื่อ $n=1\,$

$T(n)=T(k)+T(n-k)+O(n)\,$ เมื่อ $n>1\,$

พิจารณาเวลาการทำงานกรณีแย่ที่สุด คือแบ่งแล้วได้ด้านหนึ่งมีสมาชิกอยู่หนึ่งตัว แล้วอีกด้านเป็นตัวที่เหลือ ($k=1\,$ หรือ $k=n-1\,$) ดังนั้นเวลาการทำงานจะเป็นดังนี้

$T(n)=O(1)\,$ เมื่อ $n=1\,$

$T(n)=T(1)+T(n-1)+O(n)=T(n-1)+O(n)\,$เมื่อ $n>1\,$

ซึ่งกรณีนี้ท้ายที่สุดแล้ว $T(n)=\Theta (n^{2})\,$

พิจารณาเวลาการทำงานกรณีดีที่สุด คือแบ่งแล้วได้ครึ่ง ๆ พอดี ($k=n/2\,$ ดังนั้นเวลาการทำงานจะเป็นดังนี้

$T(n)=O(1)\,$ เมื่อ $n=1\,$

$T(n)=2T(n/2)+O(n)\,$เมื่อ $n>1\,$

ซึ่งกรณีนี้ท้ายที่สุดแล้ว $T(n)=\Theta (nlogn)\,$

แต่ถ้าเป็นกรณีสุ่มค่า pivot x แล้ว $T(n)\,$ จะเป็น random variable ดังนั้นเวลาการทำงานจะคิดเป็นกรณีเฉลี่ย คือ $E(T(n))=\Theta (nlogn)\,$