Sorted Index

SortedIndex.md

Sorted Index

สมมติว่าเรามีอาร์เรย์อยู่ เราสามารถแทรกข้อมูลที่ตำแหน่งใดก็ได้ใน Array โดยใช้เมธอด Array#insert แบบนี้

arr = [6, 7, 2, 3]
arr.insert(0, "first")
 #=> ["first", 6, 7, 2, 3]
arr.insert(3, "second")
 #=> ["first", 6, 7, "second", 2, 3]
arr.insert(6, "third")
 #=> ["first", 6, 7, "second", 2, 3, "third"]

sorted_index

สมมติว่าเรามีอาร์เรย์ที่เรียงอยู่แล้ว

my_array = [3, 5, 8, 13, 21, 34, 55, 89]

ให้เขียนฟังก์ชั่น sorted_index(a, value) ที่จะรีเทิร์นว่าถ้าเกิดอยากใส่ค่า value เข้าไปในอาร์เรย์ a ควรจะใส่ที่ตรงไหนดี ที่ทำให้อาร์เรย์นั้นยังคงสภาพเรียงอยู่ โดยที่ฟังก์ชั่นนี้ ใช้เวลาการทำงาน (O(\log n))

p sorted_index(my_array, 0)   #=> 0
p sorted_index(my_array, 2)   #=> 0
p sorted_index(my_array, 20)  #=> 4
p sorted_index(my_array, 200) #=> 8
p sorted_index(my_array, 21)  #=> 4 or 5 (both are correct)

Application

สมมติว่าเรามีฟังก์ชั่น sorted_index แล้ว... หมายความว่าเราสามารถใช้ Array#insert แทรกค่าเข้าไปในอาร์เรย์ โดยที่ให้อาร์เรย์นั้นมีการเรียงลำดับที่ถูกต้องตลอดเวลาอยู่แล้วได้

a = []
b = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9]
b.each do |c|
  index = sorted_index(a, c)
  a.insert(index, c)
  p a
end

[3]
[1, 3]
[1, 3, 4]
[1, 1, 3, 4]
[1, 1, 3, 4, 5]
[1, 1, 3, 4, 5, 9]
[1, 1, 2, 3, 4, 5, 9]
[1, 1, 2, 3, 4, 5, 6, 9]
[1, 1, 2, 3, 4, 5, 5, 6, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 8, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 8, 9, 9]

Running Time

สมมติว่าการเรียก Array#insert ใช้เวลา (O(n)) เพราะว่าเวลาแทรก มันต้องเลื่อนข้อมูลที่อยู่ด้านหลังตัวที่เราแทรกไปด้านขวาด้วยหนึ่งตัว

สมมติว่าเราต้องการใส่เลขหลายๆ ตัวเข้าไปในอาร์เรย์ โดยให้อาร์เรย์มันมีการเรียงลำดับที่ถูกต้องตลอดเวลา พร้อมกับแสดงค่า Array ในทุกๆ รอบการทำงาน (เหมือน Output ด้านบน)

ถามว่าโค้ดแต่ละแบบ ใช้เวลาการทำงานเป็น (O\left(\right.)เท่าไหร่(\left.\right)) แบบไหนเร็วกว่ากัน ระหว่าง:

แบบแรก ใช้ sorted_index (เหมือนตัวอย่างข้างบน)

b.each do |c|
  index = sorted_index(a, c)
  a.insert(index, c)
  p a
end

แบบที่สอง คือใส่ไปตรงท้ายอาร์เรย์แล้ว sort! (สมมติว่าการเรียก Array#sort! ใช้เวลา (O(n \log n)) และการใส่ค่าท้ายอาร์เรย์ใช้เวลา (O(1)))

b.each do |c|
  a << c
  a.sort!
  p a
end