การจัดเรียงแบบหวี

**การจัดเรียงข้อมูลแบบหวี** (อังกฤษ: 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 มีที่มาจากสูตรดังนี้
link=https://th.wikipedia.org/wiki/%E0%B9%84%E0%B8%9F%E0%B8%A5%E0%B9%8C:%E0%B8%99%E0%B9%88%E0%B8%B2%E0%B8%A3%E0%B8%B1%E0%B8%81%E0%B8%88%E0%B8%B1%E0%B8%87.png|center|thumb|251x251px|สูตรการคำนวณ <big>Comb sort</big>
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)
```python3
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(n<sup>2</sup>)**

##### Best Case
 เป็นกรณีที่จะทำงานแค่ 1 รอบหรือจำนวนของ array มีแค่ 1 ตัวทำให้ไม่ต้องเข้าลูป while จากนั้นจะ return ค่าของ array ออกมาได้เลย

Bio O จะเป็น  **Big O => O(1)**

##### Worst Case
 เป็นกรณีที่ array มีจำนวนข้อมูลมากทำให้ต้องเข้าลูป while หลายครั้งจึงทำให้เวลาในการทำงานนานขึ้น ถ้าทำเสร็จแล้วให้ return ค่าออกมาและค่าที่ได้จะเรียงจากน้อยไปมากแล้ว 

Big O จะเป็น  **Big O => O(n^2)**

## อ้างอิง
fadelc99. (2 สิงหาคม 2013) การจัดเรียงข้อมูลแบบคอมพ์ (Comb Sort). Retrieved 1 May 2018.

geeksforgeeks.  Comb Sort. Retrieved 28 April 2018.

Alban Maxhuni. (24 ธ.ค. 2013) comb sort example. Retrieved 28 April 2018.

หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ