การจัดเรียงข้อมูลแบบหวี (อังกฤษ: 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 มีที่มาจากสูตรดังนี้

สูตรการคำนวณ Comb sort

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 , 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 , 7 , 18 , 9 , 15 , 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 , 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(n²)

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.

การหมุนอาร์เรย์[แก้]

จากวิกิพีเดีย สารานุกรมเสรี

การหมุนอาร์เรย์ (อังกฤษ: Array Rotation) คือ การหมุนเปลี่ยนสลับข้อมูลภายใน array ให้หมุนสลับข้อมูลของตำแหน่งแรกถึงตำแหน่งที่เลือกไปไว้ถัดจากข้อมูลข้างหลังที่ไม่ได้เลือก เช่น

- ให้ค่าที่เลือกเป็น 3

[1, 2, 3, 4, 5] => [4, 5, 1, 2, 3]

หลักการทำงาน[แก้][แก้]

1. เช็ควนลูปของตำแหน่ง start < end ไหม เพื่อที่จะเข้าลูปทำการหมุนสลับตำแหน่งและทุกครั้งที่เข้าลูปก่อนออกต้องให้ค่า start +1 , end -1 เพื่อเช็คในการวนลูปครั้งต่อไป

2. เริ่มทำงานโดยการเข้าฟังก์ชันสลับข้อมูลและเช็คการวนลูปจากข้อ 1 เพื่อการหมุนสลับข้อมูลตำแหน่งแรกถึงตำแหน่งที่เลือกคือ 0 ถึง count-1 ก่อน โดยจะสลับจากตำแหน่งท้ายสุดมาไว้ตำแหน่งแรกและตำแหน่งแรกไปไว้ท้ายเรียงไปตามลำดับจนออกจากลูป

3. เข้าฟังก์ชันต่อไปโดยการหมุนสลับข้อมูลและเช็คการวนลูปจากข้อ 1 เพื่อทำการหมุนสลับข้อมูลของตำแหน่งที่อยู่หลังตำแหน่งที่เลือกในตอนแรกคือ count ถึง len_array-1 โดยจะเหมือนการหมุนเพื่อเปลี่ยนตำแหน่งข้อมูล

4. เข้าฟังก์ชันสุดท้ายโดยการหมุนสลับข้อมูลและเช็คการวนลูปจากข้อ 1 เพื่อทำการหมุนสลับข้อมูลตำแหน่งแรกถึงตำแหน่งสุดท้ายของข้อมูลใน array คือ 0 ถึง len_array–1 จะเป็นการหมุนสลับข้อมูลทั้งหมดให้ข้อมูลหลังตำแหน่งที่เลือกมาอยู่หน้าและข้อมูลตำแหน่งที่เลือกไปต่อท้ายข้อมูลนั้น

การทำงาน[แก้][แก้]

กำหนดให้

start คือ ตำแหน่งเริ่มต้นของค่าการหมุน

end คือ ตำแหน่งที่จบของค่าการหมุน

len_array คือ จำนวนความยาวของ array

array คือ ข้อมูลที่ต้องการนำมาหมุน

count คือ ค่าตำแหน่งที่เลือกเพื่อทำการหมุน

temp คือ ตัวว่างเปล่าที่เอาไว้สลับที่ข้อมูล

ตัวอย่างการทำงาน[แก้][แก้]

ครั้งที่ 1[แก้][แก้]

ให้ array = [1, 2, 3, 4, 5]

len_array = 5

count = 3

เริ่มจากการเข้าฟังก์ชันแรกในการหมุน swap(array, 0, count-1)

start = 0

end = 2

Round 1 :[แก้][แก้]

while  0 < 2 :
	temp = array[0]
	array[0] = array[2]
	array[2] = temp
	start += 1
	end -= 1

การสลับจะเป็น

[1, 2, 3, 4, 5]

[3, 2, 1, 4, 5]

start = 1

end = 1

start = end ทำให้ออกจากลูป

ครั้งที่ 2[แก้][แก้]

Round 1 :[แก้][แก้]

ทำให้ array = [3, 2, 1, 4, 5]

len_array = 5

count = 3

เริ่มจากการเข้าฟังก์ชันที่สองในการหมุน swap(array, count, len_array-1)

start = 3

end = 4

while  3 < 4 :
	temp = array[3]
	array[3] = array[4]
	array[4] = temp
	start += 1
	end -= 1

การสลับจะเป็น

[3, 2, 1, 4, 5]

[3, 2, 1, 5, 4]

start = 4

end = 3

start > end ทำให้ออกจากลูป

ครั้งที่ 3[แก้][แก้]

Round 1 :[แก้][แก้]

ทำให้ array = [3, 2, 1, 5, 4]

len_array = 5

count = 3

เริ่มจากการเข้าฟังก์ชันสุดท้ายในการหมุน swap(array, 0, len_array - 1)

start = 0

end = 4

while  0 < 4 :
	temp = array[0]
	array[0] = array[4]
	array[4] = temp
	start += 1
	end -= 1

การสลับจะเป็น

[3, 2, 1, 5, 4]

[4, 2, 1, 5, 3]

start = 1

end = 3

start < end ทำให้เข้าลูปต่อไปได้

Round 2 :[แก้][แก้]

ทำให้ array = [4, 2, 1, 5, 3]

len_array = 5

count = 3

เริ่มจากการเข้าฟังก์ชันแรกในการหมุน swap(array, 0, len_array - 1)

start = 1

end = 3

while  1 < 4 :
	temp = array[1]
	array[1] = array[3]
	array[3] = temp
	start += 1
	end -= 1

การสลับจะเป็น

[4, 2, 1, 5, 3]

[4, 5, 1, 2, 3]

start = 2

end = 2

start = end ทำให้ออกจากลูป

เข้าหมดทุกฟังก์ชันแล้ว จะได้ข้อมูลสุดท้ายที่หมุนออกมา return array => [4, 5, 1, 2, 3]

Code[แก้][แก้]

ตัวอย่างการเขียนโปรแกรมด้วย ภาษาไพทอน (Python)

def ArrayRotation(array,  count):
	len_array = len(array)
	swap(array, 0, count-1)
	swap(array,  count,  len_array-1)
	swap(array,  0,  len_array - 1)
	return array
def swap( array, start, end ):
	while start < end:
        	temp = array[start]
        	array[start] = array[end]
        	array[end] = temp
	  	start += 1
	   	end -= 1

Big O[แก้][แก้]

เนื่องจากการนำฟังก์ชันไปทำการวนลูป 3 รอบ ทำให้ได้สมการเป็น

O(n) * O(n) * O(n) = O(n^3)

ซึ่งทำให้ Big O ของ Code นี้เป็น O(n^3)

Best Case[แก้][แก้]

เป็นกรณีที่ดีที่สุดในการทำงาน คือ มีข้อมูลของ array เพียงแค่ 1 ข้อมูลหรือไม่มีเลยจะทำให้ไม่มีการเปรียบเทียบค่าเพื่อหมุนสลับและไม่ต้องทำงานมากทำการทำงานมีความรวดเร็ว จะได้ Big O นี้เป็น O(1)

Worst Case[แก้][แก้]

เป็นกรณีที่แย่ที่สุดในการทำงาน คือ มีข้อมูลของ array มีจำนวนมากทำให้ต้องทำงานหลายครั้งและเข้าทุกฟังก์ชันเพื่อทำกาหมุนสลับข้อมูลจำนวนเยอะทำให้การทำงานเกิดความล่าช้าจึงทำให้ได้ Big O นี้เป็น O(n^3)

อ้างอิง[แก้][แก้]

https://www.geeksforgeeks.org/array-data-structure/

https://www.geeksforgeeks.org/?p=2838

https://www.youtube.com/watch?v=viaha1SnpT4

https://www.youtube.com/watch?v=AP_g9j611wg

###########################################################################################################

การหมุนอาร์เรย์ (อังกฤษ: Array Rotation) คือ การหมุนเปลี่ยนสลับข้อมูลภายใน array ให้หมุนสลับข้อมูลของตำแหน่งแรกถึงตำแหน่งที่เลือกไปไว้ถัดจากข้อมูลข้างหลังที่ไม่ได้เลือก เช่น

- ให้ค่าที่เลือกเป็น 3

[1, 2, 3, 4, 5] => [4, 5, 1, 2, 3]

หลักการทำงาน[แก้]

1. เช็ควนลูปของตำแหน่ง start < end ไหม เพื่อที่จะเข้าลูปทำการหมุนสลับตำแหน่งและทุกครั้งที่เข้าลูปก่อนออกต้องให้ค่า start +1 , end -1 เพื่อเช็คในการวนลูปครั้งต่อไป

2. เริ่มทำงานโดยการเข้าฟังก์ชันสลับข้อมูลและเช็คการวนลูปจากข้อ 1 เพื่อการหมุนสลับข้อมูลตำแหน่งแรกถึงตำแหน่งที่เลือกคือ 0 ถึง count-1 ก่อน โดยจะสลับจากตำแหน่งท้ายสุดมาไว้ตำแหน่งแรกและตำแหน่งแรกไปไว้ท้ายเรียงไปตามลำดับจนออกจากลูป

3. เข้าฟังก์ชันต่อไปโดยการหมุนสลับข้อมูลและเช็คการวนลูปจากข้อ 1 เพื่อทำการหมุนสลับข้อมูลของตำแหน่งที่อยู่หลังตำแหน่งที่เลือกในตอนแรกคือ count ถึง len_array-1 โดยจะเหมือนการหมุนเพื่อเปลี่ยนตำแหน่งข้อมูล

4. เข้าฟังก์ชันสุดท้ายโดยการหมุนสลับข้อมูลและเช็คการวนลูปจากข้อ 1 เพื่อทำการหมุนสลับข้อมูลตำแหน่งแรกถึงตำแหน่งสุดท้ายของข้อมูลใน array คือ 0 ถึง len_array–1 จะเป็นการหมุนสลับข้อมูลทั้งหมดให้ข้อมูลหลังตำแหน่งที่เลือกมาอยู่หน้าและข้อมูลตำแหน่งที่เลือกไปต่อท้ายข้อมูลนั้น

การทำงาน[แก้]

กำหนดให้

start คือ ตำแหน่งเริ่มต้นของค่าการหมุน

end คือ ตำแหน่งที่จบของค่าการหมุน

len_array คือ จำนวนความยาวของ array

array คือ ข้อมูลที่ต้องการนำมาหมุน

count คือ ค่าตำแหน่งที่เลือกเพื่อทำการหมุน

temp คือ ตัวว่างเปล่าที่เอาไว้สลับที่ข้อมูล

ตัวอย่างการทำงาน[แก้]

ครั้งที่ 1[แก้]

ให้ array = [1, 2, 3, 4, 5]

len_array = 5

count = 3

เริ่มจากการเข้าฟังก์ชันแรกในการหมุน swap(array, 0, count-1)

start = 0

end = 2

Round 1 :[แก้]

while  0 < 2 :
	temp = array[0]
	array[0] = array[2]
	array[2] = temp
	start += 1
	end -= 1

การสลับจะเป็น

[1, 2, 3, 4, 5]

[3, 2, 1, 4, 5]

start = 1

end = 1

start = end ทำให้ออกจากลูป

ครั้งที่ 2[แก้]

Round 1 :[แก้]

ทำให้ array = [3, 2, 1, 4, 5]

len_array = 5

count = 3

เริ่มจากการเข้าฟังก์ชันที่สองในการหมุน swap(array, count, len_array-1)

start = 3

end = 4

while  3 < 4 :
	temp = array[3]
	array[3] = array[4]
	array[4] = temp
	start += 1
	end -= 1

การสลับจะเป็น

[3, 2, 1, 4, 5]

[3, 2, 1, 5, 4]

start = 4

end = 3

start > end ทำให้ออกจากลูป

ครั้งที่ 3[แก้]

Round 1 :[แก้]

ทำให้ array = [3, 2, 1, 5, 4]

len_array = 5

count = 3

เริ่มจากการเข้าฟังก์ชันสุดท้ายในการหมุน swap(array, 0, len_array - 1)

start = 0

end = 4

while  0 < 4 :
	temp = array[0]
	array[0] = array[4]
	array[4] = temp
	start += 1
	end -= 1

การสลับจะเป็น

[3, 2, 1, 5, 4]

[4, 2, 1, 5, 3]

start = 1

end = 3

start < end ทำให้เข้าลูปต่อไปได้

Round 2 :[แก้]

ทำให้ array = [4, 2, 1, 5, 3]

len_array = 5

count = 3

เริ่มจากการเข้าฟังก์ชันแรกในการหมุน swap(array, 0, len_array - 1)

start = 1

end = 3

while  1 < 4 :
	temp = array[1]
	array[1] = array[3]
	array[3] = temp
	start += 1
	end -= 1

การสลับจะเป็น

[4, 2, 1, 5, 3]

[4, 5, 1, 2, 3]

start = 2

end = 2

start = end ทำให้ออกจากลูป

เข้าหมดทุกฟังก์ชันแล้ว จะได้ข้อมูลสุดท้ายที่หมุนออกมา return array => [4, 5, 1, 2, 3]

Code[แก้]

ตัวอย่างการเขียนโปรแกรมด้วย ภาษาไพทอน (Python)

def ArrayRotation(array,  count):
	len_array = len(array)
	swap(array, 0, count-1)
	swap(array,  count,  len_array-1)
	swap(array,  0,  len_array - 1)
	return array
def swap( array, start, end ):
	while start < end:
        	temp = array[start]
        	array[start] = array[end]
        	array[end] = temp
	  	start += 1
	   	end -= 1

Big O[แก้]

เนื่องจากการนำฟังก์ชันไปทำการวนลูป 3 รอบ ทำให้ได้สมการเป็น

O(n) * O(n) * O(n) = O(n^3)

ซึ่งทำให้ Big O ของ Code นี้เป็น O(n^3)

Best Case[แก้]

เป็นกรณีที่ดีที่สุดในการทำงาน คือ มีข้อมูลของ array เพียงแค่ 1 ข้อมูลหรือไม่มีเลยจะทำให้ไม่มีการเปรียบเทียบค่าเพื่อหมุนสลับและไม่ต้องทำงานมากทำการทำงานมีความรวดเร็ว จะได้ Big O นี้เป็น O(1)

Worst Case[แก้]

เป็นกรณีที่แย่ที่สุดในการทำงาน คือ มีข้อมูลของ array มีจำนวนมากทำให้ต้องทำงานหลายครั้งและเข้าทุกฟังก์ชันเพื่อทำกาหมุนสลับข้อมูลจำนวนเยอะทำให้การทำงานเกิดความล่าช้าจึงทำให้ได้ Big O นี้เป็น O(n^3)

อ้างอิง[แก้]

geeksforgeeks. Reversal algorithm for array rotation. Retrieved 30 April 2018.

นี่คือหน้าทดลองเขียนของ Bas Mathawat หน้าทดลองเขียนเป็นหน้าย่อยของหน้าผู้ใช้ ซึ่งผู้ใช้มีไว้ทดลองเขียนหรือไว้พัฒนาหน้าต่าง ๆ แต่นี่ไม่ใช่หน้าบทความสารานุกรม ทดลองเขียนได้ที่นี่

หน้าทดลองเขียนอื่น ๆ: หน้าทดลองเขียนหลัก