Python Program for Reversal Algorithm for Array Rotation
In this tutorial, you will learn about Reversal Algorithm to rotate an array in Python. The user will give an input d by which the elements of the array will be rotated. Let's understand it.
Let a[ ] be an array with the following elements:
If the user gives an input that the array should be rotated by 2 places then the resultant array is,
For achieving this task, we can use the Reversal Algorithm, the main logic behind this algorithm is to reverse the array in parts to get the desired output.
Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7
A[] and B[] are parts of the array arr[] where
1) A[] has elements in the index range 0 to d
A[] = [1, 2]
2) B[] has elements in the index range d to n
B[] = [3, 4, 5, 6, 7]
3) Reverse array A[]
Ar[] = [2, 1]
then array ArB=[2, 1, 3, 4, 5, 6, 7]
4) Reverse array B[]
Br[] = [7, 6, 5, 4, 3]
then array ArBr = [2, 1, 7, 6, 5, 4, 3]
5) Reverse array ArBr[]
(ArBr)r[] = [3, 4, 5, 6, 7, 1, 2]
6) arr[] = [3, 4, 5, 6, 7, 1, 2]
Algorithm
Step 1- Define a function to reverse an array
Step 2- Define a function to rotate the array
Step 3- Call the reverseArray function to reverse parts of the array as discussed above
Step 4- Define a function that will print the shifted array
Step 5- Declare an array with values
Step 6- Give the number of places by which the array will be rotated
Step 7- Find the length of the array using len()
Step 8- Call Rotate() and ReverseArray() function
Python Program
Look at the program to understand the implementation of the above-mentioned approach.
def reverseArray(arr, start, end):
while (start < end):
temp=arr[start]
arr[start]=arr[end]
arr[end]=temp
start=start+1
end=end-1
def Rotate(a, d):
if d == 0:
return
n = len(a)
d = d % n
reverseArray(a, 0, d-1)
reverseArray(a, d, n-1)
reverseArray(a, 0, n-1)
def printArray(arr):
for i in range(0, len(arr)):
print(arr[i],end=" ")
a= [10, 20, 13, 24, 53, 6, 17]
n = len(a)
d = 2
printArray(a)
Rotate(a, d)
print("\nShifted array: ")
printArray(a)
2 29 30 24 9 16 11
Shifted array:
30 24 9 16 11 2 29
Conclusion
In this tutorial, we discussed the working and implementation of reversal algorithm for rotate elements of an array by d places, where d was already given. In reversal algorithm, we reverse the parts of the array first and combine them to shift the elements.