Shuffle struct by Int

Question

How I can shuffle my struct by variable priority and display in TableView?

So now I have 20 documents in my struct, but later I will have 100+ documents in my struct.

5 or 7 or 10 documents will have priority from 10 to 1, other documents have priority 0. Me need display 5 or 7 or 10 documents on top position in tableView. Other documents which have priority 0 must be located after firsts 5 or 7 or 10 documents in random order.

I. e. the firsts 5 or 7 or 10 documents should be placed depending on the priority, if a document has priority 10, it should be the first one, the next one which has priority 9 should be behind the document with priority 10 and so on to the document with priority 1. Other documents due be randomly in order.

This code which help me get documents from firestore:

fileprivate func observeQuery() {
    MBProgressHUD.showAdded(to: self.view, animated: true)
    guard let query = query else { return }
    let time = DispatchTime.now() + 0.5
    listener = query.addSnapshotListener { [unowned self] (snapshot, error) in
        if let snapshot = snapshot {
            DispatchQueue.main.asyncAfter(deadline: time) {
                var photoModels = snapshot.documents.map { (document) -> Photographer in
                    if let photoModel = Photographer(dictionary: document.data(), id: document.documentID) {
                        return photoModel
                    } else {
                        fatalError("Fatal error")
                    }
                }
                self.photographers = photoModels
                // this need use shuffle
                self.document = snapshot.documents
                self.tableView.reloadData()
                MBProgressHUD.hide(for: self.view, animated: true)
            }
        }
    }
}

Answer 1

What you could do is

• Sort the documents by decreasing priority first.
• Then shuffle the part of the array with documents with zero priority.

Example:

var sorted = documents.sorted(by: { $0.priority > $1.priority } )
if let idx = sorted.firstIndex(where: { $0.priority == 0 }) {
    sorted[idx...].shuffle()
}

An alternative is to shuffle the complete array and then do a “stable sort” by decreasing priority, using the ideas from How to stable sort an array in swift?:

let sorted = documents.shuffled().enumerated()
    .sorted(by: { ($0.element.priority, $0.offset) > ($1.element.priority, $1.offset) })
    .map { $0.element }

This would sort the entries by decreasing order, and randomly shuffle all entries with identical priority, not only the entries with zero priority.

Remark: The sort methods from the Swift standard library happens to be stable in Swift 5, so that the last approach could be simplified to

let sorted = documents.shuffled()
    .sorted(by: { $0.priority > $1.priority } )

However, that is not guaranteed, compare Is sort() stable in Swift 5? in the Swift forum.

Answer 2

You could put the documents into buckets:

var buckets = Array(repeating: [Document](), count: 11)

for i in documents.indices {
    buckets[10 - documents[i].priority].append(documents[i])
}

This is an O(n) algorithm worst case unlike TimSort's O(nlog(n)).

and then shuffle the last bucket :

buckets[10].shuffle()

last but not least, flatMap the buckets array:

let sorted = buckets.flatMap { $0 }

---

Speed Shuffle

If you'd like to an even faster shuffle, you could use this modified Fisher-Yates Algorithm (Faster than Array.shuffled()):

extension Array where Element: Comparable {
    mutating func fisherYatesShuffle()  {
        if count < 2 {
            return
        }
        for i in 1..<count {
            let ix = abs(x.next()) % (i+1)
            swapAt(i,ix)
        }
    }
}

Or more generally for MutableCollection (which would include ArraySlice):

extension MutableCollection where Index == Int, Element: Comparable {
    mutating func fisherYatesShuffle()  {
        if count < 2 {
            return
        }

        let start = self.index(after: startIndex)

        for i in start..<endIndex {
            let ix = abs(x.next()) % (i + 1 - startIndex) + startIndex
            swapAt(i, ix)
        }
    }
}

This extension uses a Xoshiro random number generator (Faster than Int.random(in:), but less random/uniform):

struct Xoshiro: RandomNumberGenerator {
    public typealias StateType = (UInt32, UInt32, UInt32, UInt32)

    private var state: StateType

    public init(seed: StateType) {
        self.state = seed
    }

    public mutating func next() -> Int {
        let x = state.1 &* 5
        let result = ((x &<< 7) | (x &>> 25)) &* 9
        let t = state.1 &<< 9
        state.2 ^= state.0
        state.3 ^= state.1
        state.1 ^= state.2
        state.0 ^= state.3
        state.2 ^= t
        state.3 = (state.3 &<< 21) | (state.3 &>> 11)
        return Int(result)
    }
}

var x = Xoshiro(seed: (UInt32.random(in: 0..<10),  //Other upper limits could be used to increase randomness
                       UInt32.random(in: 0..<10),
                       UInt32.random(in: 0..<10),
                       UInt32.random(in: 0..<10)))

To use it, Document should be Comparable :

struct Document: Comparable {
    let priority: Int
    static func < (lhs: Document, rhs: Document) -> Bool {
        return lhs.priority < rhs.priority
    }
}

and call our shuffle like so:

buckets[10].fisherYatesShuffle()

---

Partition, Sort, Shuffle

As per Josh Homann's suggestion, you could also partition the documents array putting the documents with zero priority after a pivot index. Then sort the first partition, and shuffle the second one :

var result = documents
let pivot = result.partition { $0.priority == 0 }
result[..<pivot].sort(by: > )
result[pivot...].shuffle()

---

Benchmarks

Here are some benchmarks :

Joakim Danielson's : 1643µs
MartinR's          :  169µs 
Josh Homann's      :  152µs
Orig. Fisher-Yates :   38µs
This               :   15µs

(Even though TIO uses Swift 4, relatively comparable results were got using the same code on my local machine with Swift 5, run in the terminal with optimizations)

Answer 3

Here is a solution where all elements in the array gets sorted at once

array.sort(by: {
    let first = $0.priority == 0 ? Double.random(in: 0..<1) : Double($0.priority)
    let second = $1.priority == 0 ? Double.random(in: 0..<1) : Double($1.priority)
    return first > second
})

If you want to avoid the cast to Double you can define a negative range for the random numbers, I just hardcoded a value here but one option could be to base the min value (-1000) on the size of array

array.sort(by: {
    let first = $0.priority == 0 ? Int.random(in: -1000..<1) : $0.priority
    let second = $1.priority == 0 ? Int.random(in: -1000..<1) : $1.priority
    return first > second
})