ผู้ใช้:Bas Mathawat
การจัดเรียงแบบหวี (Comb sort)[แก้]
การจัดเรียงข้อมูลแบบหวี (อังกฤษ: Comb sort) คือ การประยุกต์การจัดเรียงข้อมูลแบบ bubble sort เพื่อเพิ่มประสิทธิภาพในการทำงานได้เร็วขึ้นจะเป็นการการจัดเรียงข้อมูลเป็นคู่ใช้เปรียบเทียบโดยการหดตัวเข้าหากันเพื่อเปรียบเทียบค่าซึ่งจะมีความไวกว่า bubble sort และระยะในการหดตัวเข้าหากันเพื่อเปรียบเทียบนี้จะต้องนำจำนวนทั้งหมดของข้อมูลมาหารด้วย 1.3 ตลอดในการวนลูปจบแต่ละรอบเพื่อที่จะได้ระยะในการหดตัวเปรียบเทียบค่าใหม่ในรอบนั้น ๆ ถูกออกแบบเป็นครั้งแรกในปี คศ 1980 โดยคุณ Wlodzimierz Dobosiewicz หลังจากนั้นได้ถูกปรับปรุงโดยคุณ Stephen lacey และ Richard Box
หลักการทำงาน[แก้]
การทำงานของบับเบิ้ลจะมีประสิทธิภาพในการทำงานได้ช้าเพราะต้องมีการสลับตำแหน่งข้อมูลอยู่บ่อยครั้ง (จะเรียกข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งหลังๆ ของชุดข้อมูลว่า Turtle) ดังนั้นการจัดเรียงข้อมูลแบบ comb ใช้หลักการขจัดตัว Turtle โดยมีการกำหนด Gap ขึ้นมาแล้วทำการเปรียบเทียบค่าในช่วงของ Gap จะไม่ใช้วิธีการเปรียบเทียบค่าที่อยู่ใกล้กันเหมือนกับวิธีการจัดเรียงแบบบับเบิ้ล ขั้นตอนการทำงานการจัดเรียงแบบ comb sort มีหลักการดังนี้
• ให้ value เป็นการนับจำนวนข้อมูลทั้งหมดใน array ว่ามีกี่ตัวและเก็บค่าไว้
• ทำการหาระยะในการเปรียบเทียบค่าโดยการนำจำนวน value มาหารด้วย 1.3
• วนลูปจนกว่าค่าของ value ที่ทำการหารมาในแต่ละรอบจะเป็น 1
• ให้ count ทำการวน loop for อีกครั้งเพื่อเปรียบเทียบค่าของข้อมูลตำแหน่งที่ 0 ถึง array_len - value เพื่อไม่ให้การเทียบข้อมูลอยู่ที่ตัวสุดท้ายของการเทียบพอดีไม่หลุดออกจากข้อมูล
• เช็คว่าตำแหน่ง index ที่วนลูปแต่ละครั้งมากกว่าตำแหน่งของ index บวกกับ value ที่หารมาในรอบนั้นไหมถ้ามากกว่าจะสลับกัน ทำจนกว่าค่า value ที่หารออกมาจะเท่ากับ 1 ก็จบการทำงานได้
ขั้นตอนการทำ[แก้]
1.คำนวนหาค่า Gap ระหว่างช่องที่จะเปรียบเทียบค่าโดยจะคำนวนหา Gap จาก Shink factor โดยคุณ Stephen lacey และ Richard Box แนะนำควรเป็น 1.3 มีที่มาจากสูตรดังนี้
2.ทำการวนลูปเพื่อเทียบค่าและสลับตำแหน่งของข้อมูล การทำงานในส่วนนี้จะคล้ายกับการจัดเรียงแบบบับเบิ้ลแต่ส่วนที่ต่างกันก็คือตำแหน่งการเปรียบเทียบค่า การเทียบค่าการจัดเรียงข้อมูลแบบบับเบิ้ลจะเทียบค่าตำแหน่งที่ i กับ i+1 ซึ่งวิธีการแบบ comb จะเทียบตำแหน่งที i กับ i+gap โดยจะทำการเทียบค่าและสลับตำแหน่งข้อมูลที่ต้องการตามจำนวนสมาชิกในชุดข้อมูล หลังจากนั้นจะคำนวนค่า gap ใหม่อีกครั้งและเช็คว่าค่า gap เป็นหนึ่งหรือไม่มีการการสลับตำแหน่งข้อมูลแล้ว จึงจะยุติการทำงาน ทำให้ได้ชุดข้อมูลที่มีการเรียงลำดับเรียบร้อย
ตัวอย่างการทำงาน[แก้]
- กำหนดให้
- count คือ ตำแหน่ง loop การเทียบค่าของ 0 ถึง array_len – value
- array_len คือ ความยาวทั้งหมดของ array
- value คือ ค่าที่ถูกหารด้วย 1.3
- index คือ ตำแหน่งเปรียบเทียบของ count + value ที่การวนลูปแต่ล่ะรอบ
จะยกตัวอย่างจากข้อมูลง่ายๆ โดยให้ข้อมูลมีความยาวเท่ากับ 7 โดยเริ่มต้นจะให้
รอบที่ 0[แก้]
array_len = 7
value = 7
[ 9 , 18 , 15 , 20 , 0 , 3 , 7 ]
รอบที่ 1[แก้]
value = 7 // 1.3 => 5
count = 0 , 1
Index = 5 , 6
[ 9 , 18 , 15 , 20 , 0 , 3 , 7 ]
[ 3 , 18 , 15 , 20 , 0 , 9 , 7 ]
[ 3 , 7 , 15 , 20 , 0 , 9 , 18 ]
รอบที่ 2[แก้]
value = 5 // 1.3 => 3
count = 0 , 1 , 2 , 3
Index = 3 , 4 , 5 , 6
[ 3 , 7 , 15 , 20 , 0 , 9 , 18 ]
[ 3 , 7 , 15 , 20 , 0 , 9 , 18 ]
[ 3 , 0 , 15 , 20 , 7 , 9 , 18 ]
[ 3 , 0 , 9 , 20 , 7 , 15 , 18 ]
[ 3 , 0 , 9 , 18 , 7 , 15 , 20 ]
รอบที่ 3[แก้]
value = 3 // 1.3 => 2
count = 0 , 1 , 2 , 3 , 4
Index = 2 , 3 , 4 , 5 , 6
[ 3 , 0 , 9 , 18 , 7 , 15 , 20 ]
[ 3 , 0 , 9 , 18 , 7 , 15 , 20 ]
[ 3 , 0 , 9 , 18 , 7 , 15 , 20 ]
[ 3 , 0 , 7 , 18 , 9 , 15 , 20 ]
[ 3 , 0 , 7 , 15 , 9 , 18 , 20 ]
[ 3 , 0 , 7 , 15 , 9 , 18 , 20 ]
รอบที่ 4[แก้]
value = 2 // 1.3 => 1
count = 0 , 1 , 2 , 3 , 4 , 5
Index = 1 , 2 , 3 , 4 , 5 , 6
[ 3 , 0 , 7 , 15 , 9 , 18 , 20 ]
[ 0 , 3 , 7 , 15 , 9 , 18 , 20 ]
[ 0 , 3 , 7 , 15 , 9 , 18 , 20 ]
[ 0 , 3 , 7 , 15 , 9 , 18 , 20 ]
[ 0 , 3 , 7 , 9 , 15 , 18 , 20 ]
[ 0 , 3 , 7 , 9 , 15 , 18 , 20 ]
[ 0 , 3 , 7 , 9 , 15 , 18 , 20 ]
Code[แก้]
ตัวอย่างการเขียนโปรแกรมด้วย ภาษาไพทอน (Python)
def CombSort(array):
array_len = len(array)
value = len(array)
while value != 1 :
value = int(value // 1.3)
for count in range(0,array_len -value):
if array[count] >= array[count + value]:
array[count],array[count + value] = array[count + value], array[count]
return array
array = [9,18,15,20,0,3,7]
print(CombSort(array))
Big O[แก้]
จาก Code ด้านบนจะมีการทำงานวนลูปจำนวน 2 ลูปคือลูป while และ for โดยในแต่ละลูปจะมีค่า Big O ดังนี้
while value != 1 : จะได้ => O(n)
for index in range(0,array_len - value): จะได้ => O(n)
ลูป for อยู่ในลูป while จะนำมาคูณกันได้สมการคำตอบคือ
>>> O(n) * O(n) = O(n2)
อ้างอิง[แก้]
https://en.wikipedia.org/wiki/Comb_sort
https://www.geeksforgeeks.org/comb-sort/