Selection Sort using TypeScript!
Seems strange? Of course, folks.
I’ve recently learned that TypeScript can do more than just declare interfaces, enums, and the like. I am grateful to Matt Pocock for creating the TypeScript YouTube tutorials and series. I was able to easily understand the advanced TypeScript ideas, thanks to this tutorial.
Gist: Developing Selection sort is made feasible with the right use of TypeScript generics, infer, extends, and many more additional assets.
While creating this selection sort, I made an effort to compare it to or make it resemble a straightforward [O(n²)] JS Selection sort algorithm.
Following is a code snippet of Selection Sort algorithm with O(n²) complexity.
With the exception of the element swapping, I was able to translate this into TypeScript. Once the smaller of two is identified, I did slice my array rather than swap.
Eg. const array = [2,1,5,0],
is array > array, if yes, push the smallest one in a different so called sorted array. And for the next iteration revamp the comparing array.
Therefore, after first iteration in this case, the resultant array left to sort is, [2,5,0] and the sorted array for next iteration(after iterating this for array.length times) would be [1,2,0,5].
I also made a comparator that will subtract both numbers and work appropriately for comparing two indexes (first and second).
Below is the type interface of the Comparator which uses the Subtract type.
The Selection sort interface consumes the following arguments,
T — Input array which is extends/typeof number
C — Current iteration state of elements, to check if the iteration is done for all array elements
A — Total iterations state, should be equal to the length of input array to output the sorted array.
B — In current iteration, stores the elements remaining to be compared
M — In current iteration, stores the small elements accordingly.
Recursive type, DAMN!! 🤯
TypeScript playground — link