## Sorting...

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
kenbrooker
Posts: 124
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

### Sorting...

At one time or another most of us have entered values into an array, at the index equal to the value,
for whatever reasons. It occurred to me that this accomplishes a very simple sorting and
yet I don't think it is a recognized sorting "algorithm," like Quicksort, Mergesort,
Timsort, Bubble Sort, Insertion Sort, Selection Sort, etc, etc...

The couldn't-be-simpler Java code and example output look like this:

Code: Select all

/*
Sorts an Array via O(2n) Complexity = O(n) Complexity and at Best, Average and Worst...
*/

import java.util.Arrays;

class ArraySort
{
public static void main(String args [ ])
{
int InRay[] = {19,6,14,2,13,5,17,0,11};

int max = 0;

for(int i = 0; i < InRay.length; i++)
if(InRay[i] > max) max = InRay[i];

int OutRay[] = new int[max+1];

for(int i = 0; i < InRay.length; i++)
OutRay[InRay[i]] = InRay[i];

System.out.println(Arrays.toString(InRay));
System.out.println(Arrays.toString(OutRay));
}
}

Output:
[19, 6, 14, 2, 13, 5, 17, 0, 11]
[0, 0, 2, 0, 0, 5, 6, 0, 0, 0, 0, 11, 0, 13, 14, 0, 0, 17, 0, 19]



This pending algorithm won't handle negative numbers and raises the easily resolvable question of
whether the first 0 is a value or not but, otherwise, I don't see why what I call
ArraySort could not be a recognized, legitimate algorithm?
(In the spirit of TreeSort and HeapSort...)

To say -- Then why not just use java's Arrays.sort utility(?) overlooks that
that utility relies on some array sorting algorithm...
Last edited by kenbrooker on Sat Dec 15, 2018 1:00 am, edited 1 time in total.
"Good Judgment comes from Experience;
..."

v6ph1
Posts: 115
Joined: Mon Aug 25, 2014 6:14 pm

### Re: Sorting...

There is the problem of the handling of entries with equal values.
So your "ArraySort" is not an algorithm for sorting, but for the mathematical union-sort operation.

The algorithm of Array.sort() is not specified by the language it self:
It can differ by the implementation
- for primitive types, they used Quicksort
- for Objects, Mergesort was the favorite
Now it seams to be Timsort.

kenbrooker
Posts: 124
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

### Re: Sorting...

Thanks! v6ph1...

I totally agree and I wanted to ease into the topic of "sorting" one hurdle at a time...
The following code, still far simpler than the famous sorting algorithms,
handles entries with equal values, as is
hopefully clear in the output:

Code: Select all

/*
Sorts an Array via O(n+n+MAXn) Complexity = O(n) Complexity at Best i.e. when No duplicates...
*/

import java.util.Arrays;

class ArraySort3
{
public static void main(String args [ ])
{
int InputRay[] = {13,19,6,14,2,13,5,17,0,11,13};

int max = 0;

for(int i = 0; i < InputRay.length; i++)
if(InputRay[i] > max) max = InputRay[i];

int OutRay[] = new int[max+1];
int DupesRay[] = new int[max+1];
OutRay[0] = -1;					//to cover no Zero in InputRay

for(int i = 0; i < InputRay.length; i++)
{
OutRay[InputRay[i]] = InputRay[i];
DupesRay[InputRay[i]] += 1;
}

int OutputRay[] = new int[InputRay.length];
int index = 0;

for(int i = 0; i < max+1; i++)
{
if(OutRay[i] == i)
{
OutputRay[index] = i;
index += 1;
}

int dupes = DupesRay[i];

while(dupes > 1)
{
OutputRay[index] = i;
index += 1;
dupes -= 1;
}
}

System.out.println("InputRay  = " +Arrays.toString(InputRay));
System.out.println("OutRay    = " +Arrays.toString(OutRay));
System.out.println("DupesRay  = " +Arrays.toString(DupesRay));
System.out.println("OutputRay = " +Arrays.toString(OutputRay));
}
}

Output:
InputRay  = [13, 19, 6, 14, 2, 13, 5, 17, 0, 11, 13]
OutRay    = [0, 0, 2, 0, 0, 5, 6, 0, 0, 0, 0, 11, 0, 13, 14, 0, 0, 17, 0, 19]
DupesRay  = [1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 3, 1, 0, 0, 1, 0, 1]
OutputRay = [0, 2, 5, 6, 11, 13, 13, 13, 14, 17, 19]


What I am stressing is the relative simplicity of the code compared to the famous algorithms BUT
I am not good at the distinction between Best, Average and Worst Complexities...
The above algorithm is Best without duplicate entries, yielding Big O(n).
I don't know how to formalize the Average and/or Worst Big Os...

(There could also be applications where duplicate entries are not desired to be duplicated and
in that case I believe my earlier code is Big O(n)
Best, Average and Worst...)
"Good Judgment comes from Experience;
..."

jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Sorting...

You have re-invented the Pigeonhole sort.

The wiki page on sorting algorithms has a separate section for non-comparison integer sorts like this. Its main disadvantage is that its running time and its memory requirements depend on max, not just on n.

kenbrooker
Posts: 124
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

### Re: Sorting...

Much Obliged jaap...

You have literally... Pigeonholed my algorithm precisely and
I should have known that the odds of me coming up with
a new approach to sorting are about as high as for a
PE Problem solved by thousands being "Wrong"!

You've helped me out before;