Use generics in sorting algorithms
meetvalani opened this issue · 19 comments
Description
IMO algorithm should be working on data type float64 instead of int.
For enhancement:
- All the algorithms should be converted to use
float64as an arguments. Followings are the possible enhancements.- User must handle the type conversion of
inttofloat64. - Should provide both type where
intinternally usesfloat64related function.
- User must handle the type conversion of
Why should it be float instead of int? The only thing we need from the type is a linear order, so both of them should be perfectly fine.
I believe they think then the functions can be used in more cases, like where the numbers to be sorted are decimals.
To make sorting algorithms more usable it should be able to sort fractional numbers too. By using int we're limiting the scope of use to some use cases only.
A simple type change should work, and it may reduce the number of type conversions we have to do for using float64 functions, and, as mentioned, more use cases.
Wouldn't we need to convert integers to float if we want to sort them? If so, where's the benefit? In any case, we need to do some conversion.
We should provide support for the data type that has highest precision, float64 in golang. That way we can guarantee support for all the data types with less precision such as int, float32 etc, of course with additional conversation. But using only int won't allow us to use fractional numbers.
Go devs are also following same practices of using float64. ex: https://pkg.go.dev/math#Max
Honestly, the implementation of the sorting algorithms should not be changed right now because generics are coming to GO 🔥 next year.
But if you want to make the algorithms more general, I don't think the approach is to use float. The general idea I use in my personal projects is something along the lines of this:
package sort
import (
"fmt"
"reflect"
)
...
func Bubble(data interface{}, swap func(i, j int), less func(i, j int) bool) error {
s := reflect.ValueOf(data)
if s.Kind() != reflect.Slice {
// in this case it is actually valid to panic as well but I'm just returning an error
return fmt.Errorf("Given data is not of Slice type.")
}
for i := 0; i < s.Len(); i++ {
for j := 0; j < s.Len(); j++ {
if less(i, j) {
swap(i, j)
}
}
}
return nil
}working example is here: Go playground
Here you can pass in whatever type you want (yes even custom types would work - I use this approach in my personal projects a lot) and it would work as expected. In fact, you don't even need to write a swapper function, there is one that reflect package provides. But this is going too much into the territory of generics and I personally think that this repository needs to be as simple as possible because its mainly for learners. Personally I think since this is for learning purposes only, having sorting algorithms (as simple as possible and) only work for ints is perfectly acceptable.
EDIT: Here's the working example without explicitly defined swapper - uses reflect package: Go Playground
We should provide support for the data type that has highest precision,
float64in golang. That way we can guarantee support for all the data types with less precision such asint,float32etc, of course with additional conversation. But using onlyintwon't allow us to use fractional numbers.
Go devs are also following same practices of usingfloat64. ex: https://pkg.go.dev/math#Max
The problem with this is that if I have a slice of type int the whole slice would need to be converted before I even begin to sort the slices, this is more computationally expensive and also take memory that should not be taken for converting to and from float64. converting a slice of float64 to slice of int takes O(n) time which adds to the cost of computation.
We should wait for the generics to be implemented and then revamp all the sorts.
In case someone wants to experiment with generics here is the link to the GoTip playground to test out new features 😄 Here's my example of bubble sort
UPDATE: Syntax for generics changed. Bubble sort using new syntax
closed in #483
Closed by mistake, we still have three sorting algorithms that need to be modified to use the generic. Heap sort, radix sort and pigeonhole sort all require some refactoring for us to be able to convert them to generic sorting algorithms.
@tjgurwara99 can you assign this to me
You don't need an assignment of issues. Feel free to open a PR and we would review it 😄
I researched radix sort can apply for string: https://www.quora.com/How-can-I-sort-strings-using-Radix-Sort. But our radix sort is only for Integer. Should we implement another radix sort can apply both??
But our radix sort is only for Integer.
Yes, therefore we have this issue to convert it to a generic one.
Should we implement another radix sort can apply both??
Radix sort is Radix sort, therefore there is really no difference in them unless you take a radically novel approach to writing this algorithm. Therefore, my suggestion is to modify the existing one, unless your implementation is resulting in a difference in complexity (either space or time)
But our radix sort is only for Integer.
Yes, therefore we have this issue to convert it to a generic one.
I'd like to collaborate more on this. By converting integer to generic, do you mean we want to apply radix sort that can accept other data type beside integer?
Yes. As it was already mentioned, it can be applied to strings. Integers are numbers base 10 and this sort can apply to numbers with any base, but representing them is problematic. We could use strings for that though like we use strings to represent hex numbers.
I have been thinking, since it can sort string and integer or any base number type, can we try to sort them by their binary representation? If we sort them by keeping the native data type I think the implementation wouldn't be generic. I am planning to dig deep on this and may be trying some implementation too by this weekend.