Cyclic Sort in Kotlin
Coding Interview Patterns — IV
Cyclic sort (also called cycle sort) is an in-place sorting algorithm. It is less time-efficient than other sorting algorithms (with a time complexity of O(n²)). But, it is optimized for using constant memory and the fewest number of write operations (with a space complexity of O(1)).
Cyclic sort is a pattern used to solve some of the following (and other) programming problems.
- Sort in place
- Find missing number
- Find duplicate number
- Find first K missing numbers
Preconditions
Here are some ways to identify that a problem can be solved using cyclic sort.
- We are given an array spanning a consecutive range (e.g.
[3, 2, 4],[12, 13, 14],[-22, -23, -24], etc.) - We are seeking an inconsistency in the array (e.g. a missing number from the spanned range, a duplicate, etc.)
Algorithm
The basic steps of the cyclic sort are straightforward. I have included a diagram to illustrate a simple example with a range of [1, 4].
- Keep track of the current position we are operating on. Start at the beginning of the array. Note that this is not the same as the index (which always starts from 0). The range of elements can begin at any number, and this is usually provided in the problem. For example, an array with elements in the range
[12, 19]will have a starting position of 12. - Repeat steps 3–5 until we reach the end of the array.
- Check if the value of the current element matches its position. (e.g. for the range
[1, 4],we would check if the first element equals 1). - If the element’s value matches its position, it is in the correct location, and we can move on to the next position (increment the index and position by 1).
- If the element’s value does not match its position, we swap it with the element at its correct position. For example, if we are at position 1 with value 4, we would place 4 into position 4 and place the number previously at position 4 to the current position (which is 1). This may seem confusing to read, so I urge you to refer to the example I have drawn above. Do not increment the index after a swap since we have not checked whether the new element at the current position should stay here. We’ll do that in the next iteration.
Kotlin Example — Missing Number (easy)
The missing number problem can be solved easily using cyclic sort. Here’s the blurb.
Given an array
numswithnunique numbers in the range[0, n], return the only missing number in the range.
The first thing to do is apply the cyclic sorting algorithm and sort the numbers. (You can solve this problem easily using any sorting algorithm, as it doesn’t require cyclic sort specifically. However, I’ve used it to demonstrate the cyclic sorting algorithm).
We’ll declare a variable i to keep track of our index in the array and iterate a while loop until i reaches the end of the array.
Next, we’ll check if the number at i equals the position (which also happens to be i since the range starts at 0). If it does, we move on to the next element. Otherwise, we swap the number at i with the number at the position where position = current number.
Now the array of numbers is sorted. All that’s left is to iterate through the array until we come across a position where the value != position. We can return that position as the “missing value” solution to the problem.
Lastly, I’ll return a number outside the range if there is no missing number. In this case, the array size is outside the range.
That’s all there is to it!
See more patterns here:
