search

sentenza / scala-algorithms

Algorithms and Data Structures in Scala
GNU General Public License v3.0
28 stars 19 forks source link

Abstract the CommonSorting trait in order to support mutable and immutable collections #12

Closed sentenza closed 6 years ago

sentenza commented 6 years ago

We should aim at refactoring the current CommonSortings object in order to create two different implementations: the first one will use scala.collection.immutable, while the second one will keep the current implementation provided by the CommonSorting object.

The trait that has to be refactored is:

https://github.com/sentenza/hacktoberfest-scala-algorithms/blob/1e541a09eb9d7eb0dbec7feebb3d1d13d7f4c06a/src/main/scala/io/github/sentenza/hacktoberfest18/sort/CommonSortings.scala#L25

We could have something like a GeneralSorting trait, and two implementations:

ivanopagano commented 6 years ago

some people claims that the known sorting algorithms would not actually be the same if implemented without loops and mut-vars

As in "it's not quick-sort if you don't do mutation in-place"

The reasoning is that you usually lose the ability keep the same time-space analysis results.

ivanopagano commented 6 years ago

In general I'd rename the GeneralSorting to Sorting, anyway

sentenza commented 6 years ago

some people claims that the known sorting algorithms would not actually be the same if implemented without loops and mut-vars

As in "it's not quick-sort if you don't do mutation in-place"

The reasoning is that you usually lose the ability keep the same time-space analysis results.

This change would be more like an exercise than anything else. What is more, we will be able to show the differences between the two approaches and the time/space complexity. We can stress on this educational aspect in the scaladoc.

In general I'd rename the GeneralSorting to Sorting, anyway

It makes sense. I agree with you. ;)