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

การหมุนอาร์เรย์ (อังกฤษ: 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 ทำให้ออกจากลูป

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 ทำให้ออกจากลูป

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 arraydef 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)