Rotate an array in Swift
While studying algorithms in Swift, I could not find an algorithm for rotating an array in swift without using funcs shiftLeft
/ shiftRight
.
C has this nifty algorithm with O (N) time complexity:
/* Function to left rotate arr[] of size n by d */
void leftRotate(int arr[], int d, int n)
{
rvereseArray(arr, 0, d-1);
rvereseArray(arr, d, n-1);
rvereseArray(arr, 0, n-1);
}
/*Function to reverse arr[] from index start to end*/
void rvereseArray(int arr[], int start, int end)
{
int temp;
while (start < end)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
I'm trying to convert this to swift:
func rotate(array:[Int], positions:Int, arSize:Int) {
var a = array
var p = positions
var s = arSize
reverseArray(array: a, start: 0, end: p-1)
reverseArray(array: a, start: p, end: s-1)
reverseArray(array: a, start: 0, end: s-1)
}
func reverseArray(array: [Int], start:Int, end:Int) {
var a = array
var s = start
var e = end
var temp = 0
while s < e {
temp = a[s]
a[s] = a[e]
a[e] = temp
s += 1
e -= 1
}
}
As I understand it, for the sake of speed, we have to specify the return types. How should they be configured without increasing the complexity of the space (memory)? (otherwise, without creating new temporary arrays)
This question is different from the others because the way it returns
works in a quick comparison to C.
source to share
You can extend Array and you need to make your method mutable. BTW no need to use temporary object, you can use Swift swap method. Another opinion is that you have to make sure that the indices passed in the parameters are in the valid range for the array adding the Guard statement to the methods. Try it like this:
extension Array {
mutating func rotate(positions: Int, size: Int? = nil) {
guard positions < count && (size ?? 0) <= count else {
print("invalid input1")
return
}
reversed(start: 0, end: positions - 1)
reversed(start: positions, end: (size ?? count) - 1)
reversed(start: 0, end: (size ?? count) - 1)
}
mutating func reversed(start: Int, end: Int) {
guard start >= 0 && end < count && start < end else {
return
}
var start = start
var end = end
while start < end, start != end {
swap(&self[start], &self[end])
start += 1
end -= 1
}
}
}
var test = [1,2,3,4,5,6,7,8,9,10]
test.rotate(positions: 3) // [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]
source to share
Why create an inverse function when it's already in the Swift standard library? My solution (derived from Lev Dabus):
extension Array {
mutating func rotate(positions: Int, size: Int? = nil) {
let size = size ?? count
guard positions < count && size <= count else { return }
self[0..<positions].reverse()
self[positions..<size].reverse()
self[0..<size].reverse()
}
}
source to share
To be complete, the rotation function must support negative (right) rotations and rotate more than the size of the array
extension Array
{
mutating func rotateLeft(by rotations:Int)
{
// rotation irrelevant when less than 2 elements
if count < 2 { return }
// effective left rotation for negative and > count
let rotations = (rotations%count + count) % count
// no use rotating by zero
if rotations == 0 { return }
// rotate
(1..<count).reduce(0)
{ let i = ($0.0+rotations)%count; swap(&self[$0.0],&self[i]); return i }
}
mutating func reverse()
{
(0..<count/2).forEach{ swap(&self[$0],&self[count-$0-1]) }
}
}
source to share
This solution rotates the O (n) time complexity element
func rotLeft(a: [Int], d: Int) -> [Int] {
var arr = a
var size = arr.count - 1
for i in 0...size {
let newloc = (i + (arr.count - d)) % arr.count
arr[newloc] = a[i]
}
return arr
}
you shouldn't use .append(x)
as it could be O (n) in the worst case and you shouldn't use .remove(at: x)
as O (n) when you can avoid using these methods. As with using them, you basically get n + n + n, which is not that good
source to share