It's not bubble, it's not quick, say it onion sort

I was trying to sort data in a different way and thought of this algo.
It's obviously better than bubble sort in term of efficiency. But I still need to do more R&D to compare this algo with the others available in the market. Would appreciate your comment.

/*This file demonstrates the onionsort soring algo
  It simply finds out the lowest and the biggest and move them to leftmost and rightmost elements.
  Recursivle call this function to narrow down the size.*/
#include "stdafx.h"
#include "stdio.h"

#define ARRAY_SIZE 10	//define the array size


void onionSort( int iArray[]/*the array to be sorted*/, int iFirst/*first index*/, 
			    int iLast/*last index*/);

void swapValue( int v[], int i, int j ); //swap two elements in the array

int main(int argc, char* argv[])
{
	int iLoopCnt;
	int iArray[ARRAY_SIZE] = {9,3,4,1,66,11,5,34,0,55};	//areray elements initialized

	printf("nBefort saorting in ascending order...n");	//print the array before sorting
	for(iLoopCnt=0; iLoopCnt<ARRAY_SIZE; iLoopCnt++)
		printf("%d  ", iArray[iLoopCnt]); 
	printf("n");

	onionSort(iArray, 0, ARRAY_SIZE-1); //Sort the array in ascending order

	printf("nAfter sorting in ascending order...n");	//print the array after sorting
	for(iLoopCnt=0; iLoopCnt<ARRAY_SIZE; iLoopCnt++)
		printf("%d  ", iArray[iLoopCnt]); 
	printf("n");

	return 0;
}


/*
Function name- onionSort()
Desription- this function sorts the array in ascending order

1st parameter- entire array
2nd parameter- initial index from where onwards, elements need to be sorted
3rd parameter- end index till where elements need to be sorted

Returns none
*/
void onionSort(int iArray[], int iFirst, int iLast)
{
	int iBiggest=0, iLowest=0, iCnt, n;
	n = iLast - iFirst + 1;

	if( n<=1 )
		return;

	for( iCnt=iFirst; iCnt<iLast; iCnt++)	//Find out the biggest and the lowest
	{
		if(iCnt==iFirst)	//During the 1st traversal, assume Fist element as the lowest as well as biggest
		{
			iBiggest=iFirst;
			iLowest=iFirst;
		}

		if( iArray[iCnt] < iArray[iCnt+1])
		{
			if(iArray[iLowest] > iArray[iCnt])
				iLowest = iCnt;
			if(iArray[iBiggest] < iArray[iCnt+1])
				iBiggest = iCnt+1;
		}
		else
		{
			if(iArray[iLowest] > iArray[iCnt+1])
				iLowest = iCnt+1;
			if(iArray[iBiggest] < iArray[iCnt])
				iBiggest = iCnt;
		}
	}	
	swapValue(iArray, iFirst, iLowest);	//Move the lowest value to first(leftmost) element
	//Now it's time to move the biggest into the last(rightmost) element
	if(iBiggest != iFirst)	//Biggest was not there in the first, so simply move
		swapValue(iArray, iLast, iBiggest);
	else //biggest was there in the first, but now it has already been moved. Access it from the moved location.
		swapValue(iArray, iLast, iLowest);
	
	onionSort( iArray, iFirst+1, iLast-1);	//sort recusrively, this time 2 elements(rightmost and leftmost) lesser
}

void swapValue( int v[], int i, int j )	//Swap two elements
{
	int itemp;
	itemp = v[i];
	v[i] = v[j];
	v[j] = itemp;
}

seems still O(n^2) to me ...

nice name for the sort though

What's wrong with std::sort(&iArray[0], &iArray[ARRAY_SIZE - 1]);? Or qsort from stdlib.h if you are using C.

Google for "quick sort" or "heap sort" if you want to implement a better algorithm on your own.

Natural merge sort is another good one if you have enough memory to double-buffer the array.

Or just aim for the throat and implement a distribution sort to break the n.log(n) barrier.

Radix sort has O(n), and it's dead easy to implement :-)

Sucks for strings though.

Originally Posted by tbp

Or just aim for the throat and implement a distribution sort to break the n.log(n) barrier.

Yea, sure. And in the way, you can quickly proove that there exists an algo that can sort arbitrary data in less than n.log(n)...
Or even proove P=NP. Should be easy till tomorrow

Originally Posted by bramz

seems still O(n^2) to me ...

nice name for the sort though

Nah, it's constant O(n log n). I would probably preffer quicksort since with a few quircks it seems to be almost always linear (and my quicksort is faster than std::sort() ).

Originally Posted by pater

Yea, sure. And in the way, you can quickly proove that there exists an algo that can sort arbitrary data in less than n.log(n)...

void onionSort(int iArray[], int iFirst, int iLast)

Those are integers, not arbitrary data, and can be sorted in linear time.
Thanks for playing.

Originally Posted by SigKILL

Nah, it's constant O(n log n).

Care to explain how you come to that? Seems to me he's traversing only two elements less per recursion step ... n + n-2 + n-4 + n-6 + ... = n*(n+1)/4 (for even n)

oh, and constant doesn't really match with O(n log n). Constant = O(1)

Originally Posted by bramz

Care to explain how you come to that? Seems to me he's traversing only two elements less per recursion step ... n + n-2 + n-4 + n-6 + ... = n*(n+1)/4 (for even n)

oh, and constant doesn't really match with O(n log n). Constant = O(1)

Well, O(n^2) was what I meant (I'm slightly stupid today).
By constant I reallly meant that the best-case has the same complexity as worst case.

Ditto.

It also sucks when used on small arrays in general.
Otherwise it's lightning fast.

Originally Posted by tbp

void onionSort(int iArray[], int iFirst, int iLast)

Those are integers, not arbitrary data, and can be sorted in linear time.
Thanks for playing.

I know, but you said he was to break the n.log(n) barrier, which only exists on arbitrary data. I know that radix sort works in linear time.

Originally Posted by pater

I know, but you said he was to break the n.log(n) barrier, which only exists on arbitrary data.

No. There's a n.log(n) - on average - barrier because they are based on comparisons.

Originally Posted by tbp

No. There's a n.log(n) - on average - barrier because they are based on comparisons.

Ok, you're right. I was thinking a bit differently: Arbitrary data (i.e data structures) can only be sorted using a comparison operation.

If you will, but it's not that arbitrary if you have to equip it with a predicate. So the distinction isn't that clear.

Try looking for RADIX SORT... According to an old text book I dug up this is
the only known O(n) algorithm... if the radix used is 2 then you can sort an
array of 'k' unsigned integers, maximum value 'm' in ceil(log2(m)) * n
data moves, ie. O(n)... here's a quick (and nasty) implementation I knocked up...
it needs a buffer as a temporary store at least as big as the unsorted array,
but the code is so simple as to not need much explanation. Also it is ideally
suited to a fast assembler implementation....




struct CSortEntry
{
unsigned int key;

// append other data here...
};

void CGeneric::Sort( CSortEntry * pArray, int iCount, unsigned int iMaxKey)
{

unsigned int iMaxMask = 1;
while( iMaxMask <= iMaxKey )
iMaxMask += iMaxMask;

unsigned int iMask = 1;
while( iMask < iMaxMask )
{

unsigned int Count1 = 0;
CSortEntry * inPtr = pArray;
CSortEntry * outPtr0 = inPtr;
CSortEntry * outPtr1 = CSortArrayTemp;
for( int i = 0; i < iCount; i++ )
{
if( (inPtr->key & iMask)==0)
{
*outPtr0++ = *inPtr++;
}
else
{
*outPtr1++ = *inPtr++;
Count1++;
}
};

// Weld the two parts together

memcpy( outPtr0, CSortArrayTemp, (Count1)*sizeof(CSortEntry) );

// Advance mask, to next bit

iMask += iMask;
};
};

Distribution sorts are what we've been discussing for a couple of posts already. Doing 1 bit per pass is truely horrible.
Empirically i've found that on current x86, radix sorting 32bits in 3 pass is generally optimal. You can save some memory by doing only 2 passes, but then you can't keep histograms in cache and they have more chances to be larger than the data you're sorting

I personally like doing radix sorts in 2 or 4 passes for two reasons:

1) If you know the endianness of the platform, you can just cast the memory pointer of the key value to a byte pointer and use the pass index (or 3-pass) to get the right value to sort by. (shifting & masking doesn't cost much either and is platform safe, but I like to be difficult)

2) Doing an even number of passes means that your last pass can transfer the sorted data back into your source array without requiring an extra copy. This assumes you want to sort 'in place', which I usually do.


As for the onion sort, it really is just a variant of a bubble sort. And, since the code is tail recursive you could implement it in a while loop instead of using all the extra stack space.