การหมุนแถวลำดับ

การหมุนอาร์เรย์ (อังกฤษ: 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)

อ้างอิง

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