0

This works without comparing.

First, it finds the largest number in the array and saves it in a variable called "max". Then it creates a temporary array with the length of max + 1. After that, each "tempArray[i]" counts how often a number equal to "i" has been counted in the input array. In the end, it converts "tempArray" and writes it into the input array. See for yourself. 

 static int[] nSort(int[] array) {
        int max = array[0];
        for(int i = 1; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }
        Integer[] tempArray = new Integer[max+1];
        for(int i = 0; i < array.length; i++) {
            if(tempArray[array[i]] == null) {
                tempArray[array[i]] = 0;
            }
            tempArray[array[i]]++;
        }
        for(int[] i = new int[2]; i[0] < max + 1; i[0]++) {
            if(tempArray[i[0]] != null) {
                while(tempArray[i[0]] > 0) {
                    array[i[1]] = i[0];
                    i[1]++;
                    tempArray[i[0]]--;
                }
            }
        }
        return array;
    }

I've charted the measured runtime in a graph below. Green being my algorithm red and red being quicksort.

I've used this quicksort GitHub implementation and measured runtime in the same way as implemented there.

Runtime graph: The Runtime Graph

EvilTak
  • 7,091
  • 27
  • 36
Nico
  • 1
  • 1
    Infinite space is a trade-off in computation time. – Gordon Linoff Jan 08 '20 at 01:42
  • 2
    **that benchmark is flawed** because [it just run through the loop once](https://github.com/arisath/Benchmarking-Sorting-Algorithms/blob/master/src/main/java/BenchmarkingSortingAlgorithms.java) when the JVM hasn't even been warmed up. Benchmarking in JIT languages is very difficult. See [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/q/504103/995714). Even in compiled languages then at least 3 times must be run and the first result should be ignored, to remove the caching effect – phuclv Jan 08 '20 at 01:43
  • 10
    This is a well-known algorithm. It's called [counting sort](https://en.wikipedia.org/wiki/Counting_sort). As the Wikipedia article says, it's fast but limited to small integer keys, so only useful in special cases. Good on you though. Re-inventing a classical algorithm is fun. – Gene Jan 08 '20 at 01:44
  • I'm a noob, correct me if I'm wrong but it's an Integer Object array. Doesn't that mean the whole array doesn't use lots of space as its mostly just Object pointers pointing to null basically? – Nico Jan 08 '20 at 01:45
  • 1
    quickSort is famous because it's one of the fastest "comparison" sorts. This code isn't comparing elements, because it's a counting sort, rather than a comparison sort. – Mooing Duck Jan 08 '20 at 01:47
  • 1
    "*Just object pointers*" also need to be stored. Usually, they are 4 or 8 bytes large, which is roughly the same size as an `int`. Plus you need space for the `Integer` objects that you allocate. – Nico Schertler Jan 08 '20 at 03:13

0 Answers0