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
fadelc99 