Rotate Array in Swift

Question

While exploring algorithms in Swift, couldn't find algorithm for array rotation in swift without using funcs shiftLeft / shiftRight.

C has this graceful algo with time complexity of O(N):

/* 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 struggling with converting this into 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, for swift, we need to specify return types. How they should be configured without increasing space(memory) complexity? (aka, without creating new temporary arrays)

---

This question is different from others, because its about how returns work in swift compare to C.

Answer 1

Edit update:

Swift 5 or later

extension RangeReplaceableCollection {
    func rotatingLeft(positions: Int) -> SubSequence {
        let index = self.index(startIndex, offsetBy: positions, limitedBy: endIndex) ?? endIndex
        return self[index...] + self[..<index]
    }
    mutating func rotateLeft(positions: Int) {
        let index = self.index(startIndex, offsetBy: positions, limitedBy: endIndex) ?? endIndex
        let slice = self[..<index]
        removeSubrange(..<index)
        insert(contentsOf: slice, at: endIndex)
    }
}

---

extension RangeReplaceableCollection {
    func rotatingRight(positions: Int) -> SubSequence {
        let index = self.index(endIndex, offsetBy: -positions, limitedBy: startIndex) ?? startIndex
        return self[index...] + self[..<index]
    }
    mutating func rotateRight(positions: Int) {
        let index = self.index(endIndex, offsetBy: -positions, limitedBy: startIndex) ?? startIndex
        let slice = self[index...]
        removeSubrange(index...)
        insert(contentsOf: slice, at: startIndex)
    }
}

---

var test = [1,2,3,4,5,6,7,8,9,10]
test.rotateLeft(positions: 3)   // [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]

var test2 = "1234567890"
test2.rotateRight(positions: 3)   // "8901234567"

Answer 2

We can use Slice

func rotLeft(a: [Int], d: Int) -> [Int] {
    let slice1 = a[..<d]
    let slice2 = a[d...]
    return Array(slice2) + Array(slice1)
}

print(rotLeft(a:[1, 2, 3, 4, 5], d: 4))

//prints [5, 1, 2, 3, 4]

Answer 3

Why create a reverse function when we already have it in the Swift standard library? My solution (derived from Leo 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()
    }
}