ElementarySort.swift

// 1. QuickSort
public extension Array {
    
    mutating func quickSort(_ compare: ((Element, Element) -> Bool)) {
        
        for index in 0..<count {
            var min = index
            for subsequent in (index + 1)..<count {
                if (!compare(self[min], self[subsequent])) {
                    min = subsequent
                }
            }
            exchange(index, min)
        }

    }
    
    mutating func exchange(_ index: Int, _ min: Int) {
        let temp = self[index]
        self[index] = self[min]
        self[min] = temp
    }
    
}

// 2. Insertion Sort

public extension Array {
    mutating func insertionSort(_ compare: ((Element, Element) -> Bool)) {
        
        for index in 1..<count {
            for subIndex in (1...index).reversed() {
                if (!compare(self[subIndex - 1], self[subIndex])) {
                    exchange(subIndex - 1, subIndex)
                } else {
                    break
                }
            }
        }
    }
}

// 3. Shell sort

public extension Array {
    mutating func shellSort(_ compare: ((Element, Element) -> Bool)) {
        
        // Get the perfect H
        var shell = 1
        while( shell < count/3) { shell = 3 * shell + 1 }
        
        while(shell >= 1) {
            for index in shell..<count {
                for subIndex in stride(from: index, through: shell, by: -shell) {
                    if(!compare(self[subIndex - shell], self[subIndex])) {
                        exchange(subIndex - shell, subIndex)
                    }
                }
            }
            shell = shell / 3
        }
        
    }
}