Welcome to my blog, hope you enjoy reading :)

Saturday, June 3, 2017

Sorting algorithms

I know it has been a while since I blogged last. I really wanted to post something on movies but I'm going to do something really crazy. This is not a post on movies or movie techniques. It is on sorting algorithms. I have been seeing so many sorting algorithms like bubble sort, quicksort, merge sort, heap sort and so on. And as you probably know the complexities of these algorithms are measured in a certain notation. It is called the big O notation. For example bubble sort is of complexity O(n^2). The complexities of other algorithms are O(n log n). Is it not possible to come up with an algorithm with complexity O(n)? I think I might have just come up with one such  algorithm. Here is it:
This works best if the array to be sorted does not have huge gaps. 
1. Put each element from the array in an hashmap (key set to the value of the array element and value set to the number of times it occurs in the input array). 
2.  While doing the above step remember the smallest value and the biggest value.
3. Once that is done loop through from the smallest value to the biggest value that you remembered and print the loop index if that index is in the hashmap. 

Now tell me, is it not an O(n) implementation? Someone please tell me that i am wrong. 

I am going to call this "Yash sort" 😇 I am super excited ...

Here is a simple implementation [Am not handling duplicate values in this implementation because that would lead you to think that it is O(n2)]:
private static int[] yashSort(int[] ip) {
        HashSet h = new HashSet();
        int min = 0, max = 0;
        for (int i = 0; i < ip.length; i++) {
            if (min > ip[i]) min = ip[i];
            if (max < ip[i]) max = ip[i];

        int tmp =0;
        for (int i = min; i <= max; i++) {
            if (h.contains(Integer.valueOf(i))) {
                    ip[tmp++] = i;


No comments: