การหมุนอาร์เรย์ (อังกฤษ: 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.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
karhmunxarery xngkvs Array Rotation khux karhmunepliynslbkhxmulphayin array ihhmunslbkhxmulkhxngtaaehnngaerkthungtaaehnngthieluxkipiwthdcakkhxmulkhanghlngthiimideluxk echn ihkhathieluxkepn 3 1 2 3 4 5 gt 4 5 1 2 3 enuxha 1 hlkkarthangan 2 karthangan 2 1 twxyangkarthangan 2 1 1 khrngthi 1 2 1 1 1 Round 1 2 1 2 khrngthi 2 2 1 2 1 Round 1 2 1 3 khrngthi 3 2 1 3 1 Round 1 2 1 3 2 Round 2 3 Code 3 1 Big O 3 1 1 Best Case 3 1 2 Worst Case 4 xangxinghlkkarthanganaek1 echkhwnlupkhxngtaaehnng start lt end ihm ephuxthicaekhalupthakarhmunslbtaaehnngaelathukkhrngthiekhalupkxnxxktxngihkha start 1 end 1 ephuxechkhinkarwnlupkhrngtxip 2 erimthanganodykarekhafngkchnslbkhxmulaelaechkhkarwnlupcakkhx 1 ephuxkarhmunslbkhxmultaaehnngaerkthungtaaehnngthieluxkkhux 0 thung count 1 kxn odycaslbcaktaaehnngthaysudmaiwtaaehnngaerkaelataaehnngaerkipiwthayeriyngiptamladbcnxxkcaklup 3 ekhafngkchntxipodykarhmunslbkhxmulaelaechkhkarwnlupcakkhx 1 ephuxthakarhmunslbkhxmulkhxngtaaehnngthixyuhlngtaaehnngthieluxkintxnaerkkhux count thung len array 1 odycaehmuxnkarhmunephuxepliyntaaehnngkhxmul 4 ekhafngkchnsudthayodykarhmunslbkhxmulaelaechkhkarwnlupcakkhx 1 ephuxthakarhmunslbkhxmultaaehnngaerkthungtaaehnngsudthaykhxngkhxmulin array khux 0 thung len array 1 caepnkarhmunslbkhxmulthnghmdihkhxmulhlngtaaehnngthieluxkmaxyuhnaaelakhxmultaaehnngthieluxkiptxthaykhxmulnnkarthanganaekkahndih start khux taaehnngerimtnkhxngkhakarhmun end khux taaehnngthicbkhxngkhakarhmun len array khux canwnkhwamyawkhxng array array khux khxmulthitxngkarnamahmun count khux khataaehnngthieluxkephuxthakarhmun temp khux twwangeplathiexaiwslbthikhxmul twxyangkarthanganaek khrngthi 1aek ih array 1 2 3 4 5 len array 5 count 3 erimcakkarekhafngkchnaerkinkarhmun swap array 0 count 1 start 0 end 2 Round 1 aek while 0 lt 2 temp array 0 array 0 array 2 array 2 temp start 1 end 1 karslbcaepn 1 2 3 4 5 3 2 1 4 5 start 1 end 1 start end thaihxxkcaklup khrngthi 2aek Round 1 aek thaih array 3 2 1 4 5 len array 5 count 3 erimcakkarekhafngkchnthisxnginkarhmun swap array count len array 1 start 3 end 4while 3 lt 4 temp array 3 array 3 array 4 array 4 temp start 1 end 1 karslbcaepn 3 2 1 4 5 3 2 1 5 4 start 4 end 3 start gt end thaihxxkcaklup khrngthi 3aek Round 1 aek thaih array 3 2 1 5 4 len array 5 count 3 erimcakkarekhafngkchnsudthayinkarhmun swap array 0 len array 1 start 0 end 4while 0 lt 4 temp array 0 array 0 array 4 array 4 temp start 1 end 1 karslbcaepn 3 2 1 5 4 4 2 1 5 3 start 1 end 3 start lt end thaihekhaluptxipid Round 2 aek thaih array 4 2 1 5 3 len array 5 count 3 erimcakkarekhafngkchnaerkinkarhmun swap array 0 len array 1 start 1 end 3while 1 lt 4 temp array 1 array 1 array 3 array 3 temp start 1 end 1 karslbcaepn 4 2 1 5 3 4 5 1 2 3 start 2 end 2 start end thaihxxkcaklup ekhahmdthukfngkchnaelw caidkhxmulsudthaythihmunxxkma return array gt 4 5 1 2 3 Codeaektwxyangkarekhiynopraekrmdwy phasaiphthxn 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 lt end temp array start array start array end array end temp start 1 end 1 Big Oaek enuxngcakkarnafngkchnipthakarwnlup 3 rxb thaihidsmkarepn O n O n O n O n 3 sungthaih Big O khxng Code niepn O n 3 Best Caseaek epnkrnithidithisudinkarthangan khux mikhxmulkhxng array ephiyngaekh 1 khxmulhruximmielycathaihimmikarepriybethiybkhaephuxhmunslbaelaimtxngthanganmakthakarthanganmikhwamrwderw caid Big O niepn O 1 Worst Caseaek epnkrnithiaeythisudinkarthangan khux mikhxmulkhxng array micanwnmakthaihtxngthanganhlaykhrngaelaekhathukfngkchnephuxthakahmunslbkhxmulcanwneyxathaihkarthanganekidkhwamlachacungthaihid Big O niepn O n xangxingaekgeeksforgeeks Reversal algorithm for array rotation Retrieved 30 April 2018 ekhathungcak https th wikipedia org w index php title karhmunaethwladb amp oldid 7604371