Return to Answer

public func nthSmallest(_ n: Int) -> Element {
    precondition(count > 0, "No elements to choose from")
    precondition(1 <= n && n <= count, "n must be in the range 1...count")
    
    var low = startIndex
    var high = endIndex
    var mutableArrayCopy = self
    
    while high - low > 1 {
        let randomIndex = Int.random(in: low..<high)
        let randomElement = mutableArrayCopy[randomIndex]
        //pivot will be the index returned by partition
        let pivot = mutableArrayCopy[low..<high].partition { $0 >= randomElement }
        if n < pivot + 1 {
            high = pivot
        } else if n > pivot + 1 {
            low = pivot
            //Avoids infinite loops when an array has duplicates
            while mutableArrayCopy[low] == randomElement, k - low > 1 {
                low += 1
            }
        } else {
            return randomElement
        }
    }
    // Only single candidate left:
    return mutableArrayCopy[low]
}

public func nthSmallest(_ n: Int) -> Element {
    precondition(count > 0, "No elements to choose from")
    precondition(1 <= n && n <= count, "n must be in the range 1...count")
    
    var low = startIndex
    var high = endIndex
    var mutableArrayCopy = self
    
    while high - low > 1 {
        let randomIndex = Int.random(in: low..<high)
        let randomElement = mutableArrayCopy[randomIndex]
        //pivot will be the index returned by partition
        let pivot = mutableArrayCopy[low..<high].partition { $0 >= randomElement }
        if n < pivot + 1 {
            high = pivot
        } else if n > pivot + 1 {
            low = pivot
            //Avoids infinite loops when an array has duplicates
            while mutableArrayCopy[low] == randomElement, n - low > 1 {
                low += 1
            }
        } else {
            return randomElement
        }
    }
    // Only single candidate left:
    return mutableArrayCopy[low]
}

1. pivotIndex is confusing, one would expect it t be the index of pivotElement, but it's not.

2. a isn't very descriptive. Its name neither conveys its mutability nor that it is a copy of the initial array.

3. Such an algorithm, née FIND, is commonly known as quickSelect (more names could be found here). Personally, I would personally prefer nthSmallest(_ n: Int), for the following reasons:

1. pivotIndex is confusing, one would expect it t be the index of pivotElement, but it's not.

2. a isn't very descriptive. Its name neither conveys its mutability nor that it is a copy of the initial array.

3. Such an algorithm, née FIND, is commonly known as quickSelect (more names could be found here). Personally, I would prefer nthSmallest(_ n: Int), for the following reasons:

1. pivotIndex is confusing, one would expect it t be the index of pivotElement, but it's not.

2. a isn't very descriptive. Its name neither conveys its mutability nor that it is a copy of the initial array.

3. Such an algorithm, née FIND, is commonly known as quickSelect (more names could be found here). Conversely, I would personally prefer nthSmallest(_ n: Int), for the following reasons:

1. pivotIndex is confusing, one would expect it t be the index of pivotElement, but it's not.

2. a isn't very descriptive. Its name neither conveys its mutability nor that it is a copy of the initial array.

3. Such an algorithm, née FIND, is commonly known as quickSelect (more names could be found here). Personally, I would personally prefer nthSmallest(_ n: Int), for the following reasons: