Page 1 of 1

Sorting...

Posted: Fri Dec 14, 2018 9:53 pm
by kenbrooker
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...

Re: Sorting...

Posted: Fri Dec 14, 2018 11:14 pm
by v6ph1
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.

Re: Sorting...

Posted: Sat Dec 15, 2018 12:47 am
by kenbrooker
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...)

Re: Sorting...

Posted: Sat Dec 15, 2018 5:48 am
by jaap
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.

Re: Sorting...

Posted: Sat Dec 15, 2018 6:14 am
by kenbrooker
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;
Thanks for the links and
Thanks
Again!!
Ken