Cyclic Partition

Partitioning with nearly one assignment per moved value, instead of Hoare's one and a half By Tigran Hayrapetyan Project page: https://towardsdatascience.com/cyclic-partition/ ShipAI is a Towards Data Science project. Watch all the videos here: https://towardsdatascience.com/videos/ Key takeaways. 1. Hoare's scheme swaps misplaced values in pairs, costing three assignments per two, or 1.5 per value. 2. Cyclic partition chains the moves through emptied slots: L displaced values take only L+1 assignments. 3. On integers both run about the same; on large objects the cyclic version pulls ahead as more values move. Chapters: 0:00 What partitioning does 0:45 Hoare's three-assignment swap 2:20 A chain of assignments 3:12 The cyclic partition code 4:11 Why benchmark large objects 5:49 Running the demo 7:20 The benchmark chart 8:28 From multipartition to cyclic