WaveSort

WaveSort.swift

import UIKit

// MARK: - IMPLEMENTATION

extension Array where Element: Comparable & Hashable {
    // MARK: Internal

    /// Solves the problem as requested
    /// - Returns The wave sorted array
    func solve() -> [Element] {
        waveSorted()
    }

    // MARK: Private

    /// - Returns The elements of the array, sorted using a wave sort
    private func waveSorted() -> [Element] {
        var valueCounts = toValueCountDict()
        return waveSortedArray(from: &valueCounts)
    }

    /// - Returns A dictionary with the array's values as keys and the number of
    /// times they appear in the array as values
    private func toValueCountDict() -> [Element: Int] {
        var valueCounts: [Element: Int] = [:]
        forEach { valueCounts[$0] = (valueCounts[$0] ?? 0) + 1 }
        return valueCounts
    }

    /// Uses the value counts dictionary of the array to recursively wave sort
    /// the values and return the resulting array.
    /// - Parameter valueCountDict: The value count dictionary of the array.
    /// - Returns A resulting wave sorted array from the value count dictionary.
    private func waveSortedArray(from valueCountDicts: inout [Element: Int]) -> [Element] {
        valueCountDicts.keys.isEmpty ? []
            : sortedArray(from: &valueCountDicts) { $0 < $1 }
                + sortedArray(from: &valueCountDicts) { $0 > $1 }
                + waveSortedArray(from: &valueCountDicts)
    }

    /// Uses the elements provided by the value count dictionary and returns a array
    /// sorted using the given predicate as the comparison between elements.
    /// - Parameters:
    ///     - valueCounts: The value count dictionary of a array
    ///     - order: A predicate that returns true if its first argument should be ordered
    ///              before its second argument; otherwise, false.
    /// - Returns A sorted array of the elements as provided by the value count dictionary.
    private func sortedArray(
        from valueCounts: inout [Element: Int],
        order: (Element, Element) -> Bool
    ) -> [Element] {
        let sortedArray = Array(Set(valueCounts.keys)).sorted(by: order)
        valueCounts.keys.forEach {
            valueCounts[$0] = valueCounts[$0] ?? 0 > 1 ? (valueCounts[$0] ?? 0) - 1 : nil
        }
        return sortedArray
    }
    }

    // MARK: - TESTS

    enum TestSuite {
    enum TestError: Error {
        case waveSortFailed(message: String)
    }

    /// Creates a test case.
    /// - Parameters:
    ///     - arrayToSort: The array to sort.
    ///     - expectedSortedarray: The expected sorted array.
    /// - Returns A result with a message in case of success, an error code in case of failure.
    static func testCase<T: Comparable & Hashable>(
        arrayToSort: [T],
        expectedSortedArray: [T]
    )  -> Result<String, TestError> {
        let sortedArray = arrayToSort.solve()
        return sortedArray == expectedSortedArray ?
            .success(
                """
                SUCCESS!
                The sorted array is \(sortedArray) as expected.
                """
            ) :
            .failure(.waveSortFailed(message:
                """
                FAILURE!
                Expected \(expectedSortedArray),
                got \(sortedArray) instead.
                """
            ))
    }

    /// Runs a test suite.
    /// - Parameter testSuite: An array of test cases to run
    static func run(testSuite: () -> [() -> Result<String, TestSuite.TestError>]) {
        testSuite().enumerated().forEach { (index, testCase) in
            print("==== TEST CASE \(index) ====")
            let testResult = testCase()
            switch testResult {
            case .success(let message): print("✅ \(message)")
            case .failure(let message): print("❌ \(message)")
            }
            print("=====================")
        }
    }
    }

    // MARK: Test Suite

    /// Test Case 1: Wave sorting an array of integers with only 1 expected wave.
    func testCaseOne() -> Result<String, TestSuite.TestError> {
    TestSuite.testCase(
        arrayToSort: [1, 7, 1, 4, 2, 2, 3],
        expectedSortedArray: [1, 2, 3, 4, 7, 2, 1]
    )
    }

    /// Test Case 2: Wave sorting an array of integers with more than 1 expected waves.
    func testCaseTwo() -> Result<String, TestSuite.TestError> {
    TestSuite.testCase(
        arrayToSort: [1, 2, 1, 2, 3, 7, 4, 9, 11, 3, 1, 2, 3, 1, 3, 7, 4, 9],
        expectedSortedArray: [1, 2, 3, 4, 7, 9, 11, 9, 7, 4, 3, 2, 1, 1, 2, 3, 3, 1]
    )
    }

    /// Test Case 3: Wave sorting an array of strings with only 1 expected wave.
    func testCaseThree() -> Result<String, TestSuite.TestError> {
    TestSuite.testCase(
        arrayToSort: ["cat", "fish", "ant", "ant", "elephant", "platypus", "platypus", "cat"],
        expectedSortedArray: ["ant", "cat", "elephant", "fish", "platypus", "platypus", "cat", "ant"]
    )
}

TestSuite.run {[
 testCaseOne,
 testCaseTwo,
 testCaseThree
]}