Sorting...

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

Sorting...

Post by kenbrooker » Fri Dec 14, 2018 9:53 pm

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;
Experience comes from Bad Judgment
..."
Image

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

Re: Sorting...

Post by v6ph1 » Fri Dec 14, 2018 11:14 pm

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.
Image

User avatar
kenbrooker
Posts: 115
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Sorting...

Post by kenbrooker » Sat Dec 15, 2018 12:47 am

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;
Experience comes from Bad Judgment
..."
Image

User avatar
jaap
Posts: 535
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Sorting...

Post by jaap » Sat Dec 15, 2018 5:48 am

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.

User avatar
kenbrooker
Posts: 115
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Sorting...

Post by kenbrooker » Sat Dec 15, 2018 6:14 am

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
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

Post Reply