Array Rotation using Reversal Algorithm in Python
In this tutorial, we are going to solve the task of rotating an array to the left in Python using the Reversal Algorithm. Firstly, we need to know what is an array in Python.
An array is one of the most common types of containers in Python. It consists of a fixed number of sequence of values and a unique thing about arrays is that the values inside the list have to be of the same data type, most commonly integer or float. In addition to this, elements in an array have unique positions or indexes and we use these to access the elements of the array.
Here, we will need an integer array.
We also come across a term here called Reversal Algorithm. Let us discuss this before we dive deeper into the task.
What is Reversal Algorithm?
Reversal algorithm is an algorithm that uses multiple in-place reversals to rotate an entire array. Let us see the algorithm first :
rot(ar,d,n) rev(ar,0,d-1) rev(ar,d,n-1) rev(ar,0,n-1)
Here, if you see carefully, we are using three reversals with different starting and ending points of the array. Let us take the whole array as AB and the portion of array till d as A and from d to end as B:
- First, we reverse the A portion: A(r)B
- Next, we reverse the B portion : A(r)B(r)
- In the third one, we reverse the entire new array : (A(r)B(r))r = BA and thus the array is rotated to the left.
Let us see an example :
ar = [2,4,6,8,10] d=2 A=[2,4] B=[6,8,10] ArB=[4,2,6,8,10] ArBr=[4,2,10,8,6] (ArBr)r=[6,8,10,2,4]
Hence, it is seen in the end that the array is fully left rotated using Reversal Algorithm.
Implementation of Reversal Algorithm in the Task
In this task, we will perform a left rotation on the given array arr of given length l by diff elements. Here, we take the diff as input from the user; you can take any value as default as well. The approach is as follows :
- Firstly, in main function, we take the array arr of length l and diff as input and pass them as arguments to function rotate().
- Next, in rotate() function, check whether diff is a non-zero value or not. If elements by which the array has to be rotated is zero, then return back to the main function.
- In case the diff is greater than l, we do diff modulus l and assigned to diff; diff remains the same if diff is less than l , else diff is brought back to a value less than l on doing modulus.
- We call the reverse() function first to reverse the first portion of the array[0:diff] and return back to rotate(). The reverse() function is using the temp variable to swap values between arr[first] and arr[last] and this is running in a loop, incrementing first and decrementing last, the condition being first<last.
- Next, call the reverse() function to reverse the portion of array after diff till last[diff: ] and return back to rotate().
- Then, call the reverse() function to reverse the entire array and return back to rotate().
- Now, print arr.
# function to reverse array portion passed def reverse(arr, first, last): while (first < last): temp= arr[first] arr[first] = arr[last] arr[last] = temp first=first+1 last = last-1 # function to rotate the array def rotate(arr, diff, l): if diff == 0: # no difference leads to no reversal return diff = diff % l # for diff greater than l reverse(arr, 0, diff-1) # to reverse first half of array reverse(arr, diff, l-1) # to reverse next half of the array reverse(arr, 0, l-1) # to reverse whole array # Main code arr= l = int(input("Enter the length of array: ")) for i in range(0,l): #taking array input element = int(input()) arr.append(element) diff = int(input("Enter the difference: ")) rotate(arr, diff, l) print(arr)
Output : Enter the length of array: 7 1 2 3 45 6 7 8 Enter the difference: 3 [45, 6, 7, 8, 1, 2, 3]
Here, we take the array arr as [1,2,3,45,6,7,8] of length 7 and the gap as 3. We get the output as [45,6,7,81,2,3]; we see here that the array has been successfully rotated left by 3 elements.
Thanks for going through this article by sparing your valuable time. I sincerely hope that the article was able to answer your doubts regarding this topic. Do check out the links given below :
- How to rotate an array in Python
- Block swap algorithm for array rotation in Python
- Reversal algorithm for array rotation in C++