การจัดเรียงข้อมูลแบบคอมพ์ (Comb Sort)

Comb sort  เป็นการประยุกต์การจัดเรียงข้อมูลแบบบับเบิ้ลเพื่อเพิ่มประสิทธิภาพในการทำงาน    ถูกออกแบบเป็นครั้งแรกในปี คศ 1980 โดยคุณ Wlodzimierz Dobosiewicz  หลังจากนั้นได้ถูกปรับปรุงโดยคุณ Stephen lacey และ Richard Box และตีพิมพ์บทความลงในนิตยสาร Byte Magazine ฉบับเดือนเมษายนในปี คศ. 1991 ชุดข้อมูลที่จะเรียงหากมีลักษณะที่ค่าของตัวเลขน้อยๆ  อยู่ในลำดับท้ายๆของชุดข้อมูล ดังตัวอย่าง

10           15           30           90           70           2              1              3              80           100

การทำงานของบับเบิ้ลจะมีประสิทธิภาพในการทำงานได้ช้าเพราะต้องมีการสลับตำแหน่งข้อมูลอยู่บ่อยครั้ง (จะเรียกข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งหลังๆ ของชุดข้อมูลว่า Turtle)   ดังนั้นการจัดเรียงข้อมูลแบบ comb ใช้หลักการขจัดตัว Turtle โดยมีการกำหนด Gap ขึ้นมาแล้วทำการเปรียบเทียบค่าในช่วงของ Gap จะไม่ใช้วิธีการเปรียบเทียบค่าที่อยู่ใกล้กันเหมือนกับวิธีการจัดเรียงแบบบับเบิ้ล ขั้นตอนการทำงานการจัดเรียงแบบ comb มีหลักการดังนี้
1.คำนวนหาค่า Gap จะคำนวนหา Gap จาก Shink factor โดยคุณ Stephen lacey และ Richard Box แนะนำควรเป็น  1.3 มีที่มาจากสูตรดังนี้

2.ทำการวนลูปเพื่อเทียบค่าและสลับตำแหน่งของข้อมูล การทำงานในส่วนนี้จะคล้ายกับการจัดเรียงแบบบับเบิ้ลแต่ส่วนที่ต่างกันก็คือตำแหน่งการเปรียบเทียบค่า    การเทียบค่าการจัดเรียงข้อมูลแบบบับเบิ้ลจะเทียบค่าตำแหน่งที่ i กับ i+1 ซึ่งวิธีการแบบ comb จะเทียบตำแหน่งที i กับ i+gap โดยจะทำการเทียบค่าและสลับตำแหน่งข้อมูลที่ต้องการตามจำนวนสมาชิกในชุดข้อมูล  หลังจากนั้นจะคำนวนค่า gap ใหม่อีกครั้งและเช็คว่าค่า gap เป็นหนึ่งหรือไม่มีการการสลับตำแหน่งข้อมูลแล้ว จึงจะยุติการทำงาน ทำให้ได้ชุดข้อมูลที่มีการเรียงลำดับเรียบร้อย  จะขอยกตัวอย่างการทำงานจากชุดข้อมูลดังนี้

33           98          74          13          55          20          77          45          64          83

การทำงานครั้งที่ 1 คำนวนค่า shrink factor ได้ค่า gap เป็น 7

เปรียบเทียบค่าในตำแหน่ง i[0]=33 >i[7]=45

33,98,74,13,55,20,77,45,64,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[1]=98 >i[8]=64

33,98,74,13,55,20,77,45,64,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 33,64,74,13,55,20,77,45,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[2]=74 >i[9]=83

33,64,74,13,55,20,77,45,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล

สิ้นสุดการเปรียบเทีบบในการทำงานรอบที่  1 ชุดข้อมูลที่ได้จากการทำงานรอบนี้คือ 33,64,74,13,55,20,77,45,98,83

การทำงานครั้งที่ 2 คำนวนค่า shrink factor ได้ค่า gap เป็น 5

เปรียบเทียบค่าในตำแหน่ง i[0]=33 >i[5]=20

33,64,74,13,55,20,77,45,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 20,64,74,13,55,33,77,45,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[1]=64 >i[6]=77

20,64,74,13,55,33,77,45,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[2]=74 >i[7]=45

20,64,74,13,55,33,77,45,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 20,64,45,13,55,33,77,74,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[3]=13 >i[8]=98

20,64,45,13,55,33,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[4]=55 >i[9]=83

20,64,45,13,55,33,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล

สิ้นสุดการเปรียบเทีบบในการทำงานรอบที่  2 ชุดข้อมูลที่ได้จากการทำงานรอบนี้คือ 20,64,45,13,55,33,77,74,98,83

การทำงานครั้งที่ 3 คำนวนค่า shrink factor ได้ค่า gap เป็น 3

เปรียบเทียบค่าในตำแหน่ง i[0]=20 >i[3]=13

20,64,45,13,55,33,77,74,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 13,64,45,20,55,33,77,74,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[1]=64 >i[4]=55

13,64,45,20,55,33,77,74,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 13,55,45,20,64,33,77,74,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[2]=45 >i[5]=33

13,55,45,20,64,33,77,74,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 13,55,33,20,64,45,77,74,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[3]=20 >i[6]=77

13,55,33,20,64,45,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[4]=64 >i[7]=74

13,55,33,20,64,45,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[5]=45 >i[8]=98

13,55,33,20,64,45,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[6]=77 >i[9]=83

13,55,33,20,64,45,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล

สิ้นสุดการเปรียบเทีบบในการทำงานรอบที่  3 ชุดข้อมูลที่ได้จากการทำงานรอบนี้คือ 13,55,33,20,64,45,77,74,98,83

การทำงานครั้งที่ 4 คำนวนค่า shrink factor ได้ค่า gap เป็น 2
เปรียบเทียบค่าในตำแหน่ง i[0]=13 >i[2]=33

13,55,33,20,64,45,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[1]=55 >i[3]=20

13,55,33,20,64,45,77,74,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 13,20,33,55,64,45,77,74,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[2]=33 >i[4]=64

13,20,33,55,64,45,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[3]=55 >i[5]=45

13,20,33,55,64,45,77,74,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 13,20,33,45,64,55,77,74,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[4]=64 >i[6]=77

13,20,33,45,64,55,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[5]=55 >i[7]=74

13,20,33,45,64,55,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[6]=77 >i[8]=98

13,20,33,45,64,55,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[7]=74 >i[9]=83

13,20,33,45,64,55,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล

สิ้นสุดการเปรียบเทีบบในการทำงานรอบที่  4 ชุดข้อมูลที่ได้จากการทำงานรอบนี้คือ 13,20,33,45,64,55,77,74,98,83

การทำงานครั้งที่ 5 คำนวนค่า shrink factor ได้ค่า gap เป็น 1

เปรียบเทียบค่าในตำแหน่ง i[0]=13 >i[1]=20

13,20,33,45,64,55,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[1]=20 >i[2]=33

13,20,33,45,64,55,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[2]=33 >i[3]=45

13,20,33,45,64,55,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[3]=45 >i[4]=64

13,20,33,45,64,55,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[4]=64 >i[5]=55

13,20,33,45,64,55,77,74,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 13,20,33,45,55,64,77,74,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[5]=64 >i[6]=77

13,20,33,45,55,64,77,74,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[6]=77 >i[7]=74

13,20,33,45,55,64,77,74,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 13,20,33,45,55,64,74,77,98,83 ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[7]=77 >i[8]=98
13,20,33,45,55,64,74,77,98,83 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[8]=98 >i[9]=83

13,20,33,45,55,64,74,77,98,83 มีค่ามากกว่า ทำให้ต้องสลับข้อมูลในตำแหน่งผลที่ได้คือ 13,20,33,45,55,64,74,77,83,98

สิ้นสุดการเปรียบเทีบบในการทำงานรอบที่  5 ชุดข้อมูลที่ได้จากการทำงานรอบนี้คือ 13,20,33,45,55,64,74,77,83,98

การทำงานครั้งที่ 6 คำนวนค่า shrink factor ได้ค่า gap เป็น 1

เปรียบเทียบค่าในตำแหน่ง i[0]=13 >i[1]=20

13,20,33,45,55,64,74,77,83,98 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[1]=20 >i[2]=33

13,20,33,45,55,64,74,77,83,98 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[2]=33 >i[3]=45

13,20,33,45,55,64,74,77,83,98 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[3]=45 >i[4]=55

13,20,33,45,55,64,74,77,83,98 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[4]=55 >i[5]=64

13,20,33,45,55,64,74,77,83,98 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[5]=64 >i[6]=74

13,20,33,45,55,64,74,77,83,98 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[6]=74 >i[7]=77

13,20,33,45,55,64,74,77,83,98 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[7]=77 >i[8]=83

13,20,33,45,55,64,74,77,83,98 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล ดำเนินการเปรียบเทียบตำแหน่งถัดไป

เปรียบเทียบค่าในตำแหน่ง i[8]=83 >i[9]=98

13,20,33,45,55,64,74,77,83,98 มีค่าน้อยกว่าไม่ต้องสลับข้อมูล

สิ้นสุดการเปรียบเทีบบในการทำงานรอบที่  6 และสิ้นสุดการทำงานขอการเรียงลำดับแบบ comb sort ข้อมูลที่ได้จากการทำงานเรียงเป็นดังนี้ 13,20,33,45,55,64,74,77,83,98

Advertisements
Posted in Uncategorized | Leave a comment