Sorting Algorithms

[Gabriel]

Gentlemen,

When considering Sorting Algorithm "Efficiency", from what I've read, the key points are: Number of Swaps, and Number of Comparisons.
(Limited to In Place sorting of Number arrays)

Now, Consider for clarity's sake _Bubble Sort_.
When it makes a 1 Swap, it makes 2 Writes to the Array.

When reading articles online about this, should I consider each write as 1 Swap?. or 2 writes as 1 Swap.... (I hope im making sense here)

I've developed a sorting algorithm which i believe to be "new" or "unique" with low overhead, and high efficiency.

My preliminary results using a completely reversed arrays are as follow:
(only test I've had time to run so far)

[temtronic]

hmm.. something to consider is that in any 'swap', you can't just swap A for B, you need to store one of the values into a temporary variable, which is another operation, so has to be counted as that takes time...
food for thought...
Jay

[Gabriel]

Hi Jay, Thanks for your reply.

I have not seen any explanation on efficiency that counts the Temporary holding as a Write/Swap.

However the amount of "extra" Space needed to operate can vary from a whole parallel array to dump the sorted values to 1 single space to perform swaps.
And this IS also one of the factors considered when evaluating Sorting Algorithms.

as per the explanation above:
Merge Sort: O(n) Needs a Parallel Array of Size n
Bubble Sort: O(1) Needs 1 Extra Space

My Algorithm falls into the O(1) Category, which is the Ideal Case.

G.
_________________
CCS PCM 5.078 & CCS PCH 5.093

[temtronic]

I brought up the 'temporary space' since the PIC needs to 'stuff something somewhere' and that takes time. How much time depends on size of the array and speed of the PIC.
Efficency should include execution times and that of course depends on # of operations.

[Gabriel]

I apologize if I gave you the impression of disagreeing with you.
To be clear, I completely agree with you... yes it does impact execution time obviously.

In everything I'm commenting I MAY BE COMPLETELY WRONG.
I'm hoping to be corrected if so...

The point I'm trying to make is that when counting the swaps, the temporary hold is not taken into account as a "Swap / Write".
Its does add to the run time but not included explicitly as a "Swap/Write".
From what I've understood, when analyzing the algorithms the temporary hold falls more into the "overhead" Category.

Many Sort algorithms use swaps, which require 2 array writes and a temporary hold write.
This would imply that an algorithm that has O(n) Writes in reality has O(n+(1/2n)) writes.... the (1/2n) being the temporary hold write.
But nobody counts this write... which is why i wasn't either.
I may be wrong... please explain.

The part I'm trying to understand is if when counting Swap operations, should i count each individual Array Write as a swap or 1 swap is assumed to be 2 writes....

its a terminology/notation question i guess.
_________________
CCS PCM 5.078 & CCS PCH 5.093

[Gabriel]

Sanity check:

I am sure my method has been done before... probably a hybrid I've never heard of.
I don't think I have invented the wheel... although i feel like it.
I don't discard the remote possibility of this being an actual new fantastic algorithm, however i realize its unlikely.

I would like to better understand the things I'm asking here, so that i can stop telling myself I've created something new and move on with my life.
_________________
CCS PCM 5.078 & CCS PCH 5.093

[Ttelmah]

It's worth also realising that if you have an array of pointers to the data, then you can 'sort' by just swapping the pointers not the data itself. For any reasonably large data, this reduces the amount of movements needed enormously.

[temtronic]

re:
I dont think I have invented the wheel... although i feel like it.

Man I just got run over doing personal taxes, due end of the week....sigh Wife's PC don't have a CD drive..hmmmm....

I find it 'interesting' that 'they' don't consider the time to put/get data from a temp variable to be important. Wonder if 'they' will give me their coin change from every transaction they make?? Nickels and dimes do add up !!

Decades ago I do remember doing the 'sort the array of indexes,not the array of data' on a TRS80, which was a Z-80 based machine. Sigh, I miss the food old dayze...
Jay

[pmuldoon]

So YOU were the other guy that owned one of those! (TRS-80).

[Ttelmah]

He is not alone...

However I had a BBC as well, and a couple of my first designs were disk systems for the BBC and the TRS. They sold well. At one time I got an award from Rodime, for having shipped more drives in a month than anyone else in the UK.

[temtronic]

I still have mine as well as the homebrewed 15Meg HD system AND 3 pcs of Model III Version ONE BASIC ROMs.
Kinda 'sad' that a $1 PC can replace 99% of a TRS80, sniff,sniff.

[Ttelmah]

15Meg!....
That was late. It was a couple of years before HD's grew beyond 5Meg. I still remember a newspaper article being published when the 5Meg HD's launched saying that they held so much that you could store your entire life's data on one!..... (worrying isn't it). It's also terrifying when a 5Meg HD cost about 5* what a complete PC now costs.

[pmuldoon]

Yes, I spent many many hours studying the schematic of the TRS80 and reading the datasheet of a Z80. It was a great way to learn microprocessors. Everything was so simple and straightforward.

[Gabriel]

Jay,

[Ttelmah]

Comparisons involve just as much work as a swap. You have to access every byte in the values to do a comparison.
The most efficient sort is normally believed to be merge sort, but this involves extra storage.
Honestly why not just use the Quicksort implementation supplied with the compiler?. You are not likely to do much better and it is already written for you. You just have to supply the comparison routine.