Skip to main content

A small comparison between 3 essential algorithms in Kotlin



There is no doubt that sorting is still one of the most essential and important part in computer science. Everyone who knows a little about algorithms has already proven today's data to  be true, but I would give a hand to everyone who hasn't tried the results by themselves yet.

There are different sorting algorithms, but there are many factors to differentiate them from one another. And the focus today will be in the execution time, which comes as a result of each algorithms time complexity.

Let's jump to the algorithms first, starting with Insertion Sort:

This is the code for Merge Sort:


And this is the code for Quick Sort:

The only thing that will be changing here is the size of the elements that Utils.someArrayOfInts() will return.

In the first case, let's try our algorithms  with just an array of 7 integers:



Insertion sort is pretty quick comparing to other algorithms in this case. Now let's run the same algorithms, with one thousand (1000) integers. Check out my result:


 When having to sort 1000 items, looks like merge sort wins. And this is because insertions sort time complexity is O(n^2) (n square) while the others have an O(log(n)) time complexity (Quick sort has O(n^2) in worst case), which respectively means: For insertion sort, if the number of input items increases, so does the execution time, while the other 2 algorithms execute in lower time while the input increases. Mathematically the logn graph is quite the opposite of exponential graph which is the exact case illustrated here.

And now let's check the same algorithms, with 1 million elements to sort:


Conclusion

 Looks like you should avoid using Insertion sort for a large input array and stick to Merge Sort or Quick Sort. Even though Merge Sort or Quick Sort run recursively (and recursion does slow down the program), the best algorithm for less than 30 inputs should be Insertion sort.


Some things to note:

The array elements are not guaranteed that will be the same for each time an algorithm executes. They are generated randomly and placed in a position by a for loop. So we cannot tell exactly in this case which from Merge sort or Quick sort is better. We are focusing only in execution time, but the way the elements are at first state in the array, does matter also.

Another thing to keep in mind is to forget using sorting algorithms to real life projects. Keep in mind that Java/Kotlin has already implemented the best solution for sorting arrays which is called DualPivotQuicksort that is an improvement of the basic Quick sort above. 

I also have more algorithms in Kotlin. You can check them here

Popular posts from this blog

Modularizing your Android app, breaking the monolith (Part 1)

Inspired by a Martin Fowlers post about Micro Frontends, I decided to break my monolithic app into a modular app. I tried to read a little more about breaking monolithic apps in Android, and as far as I got, I felt confident to share my experience with you. This will be some series of blog posts where we actually try to break a simple app into a modularized Android app.

Note: You should know that I am no expert in this, so if there are false statements or mistakes please feel free to criticize, for the sake of a better development. 

What do you benefit from this approach:
Well, people are moving pretty fast nowadays and delivery is required faster and faster. So, in order to achieve this, modularising Android apps is really necessary.You can share features across different apps. Independent teams and less problems per each.Conditional features update.Quicker debugging and fixing.A feature delay doesn't delay the whole app. As per writing tests, there is not too much difference about…

What I learned from Kotlin Flow API

I used to check the docs and just read a lot about flows but didn't implement anything until yesterday. However, the API tasted really cool (even though some operations are still in Experimental state).Prerequisites: If you don't know RxJava it's fine. But a RxJava recognizer would read this faster.Cold vs Hot streamsWell, I really struggled with this concept because it is a little bit tricky. The main difference between cold and hot happened to be pretty simple: Hot streams produce when you don't care while in cold streams, if you don't collect() (or RxJava-s equivalent subscribe()) the stream won't be activated at all. So, Flows are what we call cold streams. Removing the subscriber will not produce data at all, making the Flows one of the most sophisticated asynchronous stream API ever (in the JVM world). I tried to make a illustration of hot and cold streams: Since I mentioned the word asynchronous this implies that they do support coroutines also. Flows vs…

From Gson to Moshi, what I learned

There is no doubt that people are getting away from GSON and I agree with those reasons too. The only advantage GSON has over other parsing libraries is that it takes a really short amount of time to set up. Furthermore, the most important thing is that Moshi is embracing Kotlin support.

First let's implement the dependency:
implementation("com.squareup.moshi:moshi:1.8.0") It's not a struggle to migrate to Moshi. It's really Gson look-a-like. The only thing to do is annotate the object with @field:Json instead of @SerializedName (which is Gsons way for JS representation):

data class User( //GSON way @SerializedName("name") val name: String, @SerializedName("user_name") val userName: String, @SerializedName("last_name") val lastName: String, @SerializedName("email") val email: String ) data class User( //Moshi way @field:Json(name = "name") val name: String, @field:Json(name = "user_name…