팬케이크 정렬(pancake sort)

Microsoft의 빌 게이츠가 고안한 정렬 알고리즘. 반전 기반으로 설계되어 있고, 수행 시간이 생각보다 많이 걸린다. 효율적인 알고리즘이라 보기는 좀...


extension Array where Element : Comparable {
    mutating func flip(_ first: Self.Index, _ end: Self.Index) -> Self {
        var f = first
        var e = end
        
        while f <= e {
            (self[f], self[e]) = (self[e], self[f])
            
            formIndex(after: &f)    // f = f + 1
            formIndex(before: &e)   // e = e - 1
        }
        
        return self
    }
    
    func maxIndex(to lastIndex: Self.Index) -> Self.Index {
        var result = startIndex
        
        for i in 0 ... lastIndex {
            if self[i] > self[result] {
                result = i
            }
        }
        return result
    }

    mutating func pancakeSort() -> Self {
        var curr = self.count - 1
 
        while curr >= 0 {
            let mi = maxIndex(to: curr)
            
            flip(0, mi)
            flip(0, curr)
            
            curr -= 1
        }
        
        return self
    }   
}

//a.maxIndex(to: 4)
var a = [1, 3, 5, 7, 2, 4, 6, 8]
a.pancakeSort()