CCS C Software and Maintenance Offers
FAQFAQ   FAQForum Help   FAQOfficial CCS Support   SearchSearch  RegisterRegister 

ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

CCS does not monitor this forum on a regular basis.

Please do not post bug reports on this forum. Send them to support@ccsinfo.com

Sorting Algorithms
Goto page 1, 2  Next
 
Post new topic   Reply to topic    CCS Forum Index -> General CCS C Discussion
View previous topic :: View next topic  
Author Message
Gabriel



Joined: 03 Aug 2009
Posts: 1067
Location: Panama

View user's profile Send private message

Sorting Algorithms
PostPosted: Wed Apr 25, 2018 9:42 am     Reply with quote

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)

Code:

Items   Swaps   Comparisons
40           40           800
35           34           612
30           30           450
25           24           312
20           20           200
15           14           112
10           10           50
5           4           12


Pleas note I am considering 1 Swap = 1 Array Write
(Thus my initial question)

If my Big O notation is correct and not too rusty, my Algorithm comes out to:

Swaps= O(n)
Comparisons= O(1/2*(n^2)) <--- Errr.. not to sure about this.

I'm fairly certain when considering Swap counts, what it really means is write counts.
Otherwise I have just created the first O(n/2) Sorting algorithm.
I will press X for Doubt on that last claim hahahahaha

G.
_________________
CCS PCM 5.078 & CCS PCH 5.093
temtronic



Joined: 01 Jul 2010
Posts: 9081
Location: Greensville,Ontario

View user's profile Send private message

PostPosted: Wed Apr 25, 2018 9:49 am     Reply with quote

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



Joined: 03 Aug 2009
Posts: 1067
Location: Panama

View user's profile Send private message

PostPosted: Wed Apr 25, 2018 9:59 am     Reply with quote

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



Joined: 01 Jul 2010
Posts: 9081
Location: Greensville,Ontario

View user's profile Send private message

PostPosted: Wed Apr 25, 2018 10:38 am     Reply with quote

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



Joined: 03 Aug 2009
Posts: 1067
Location: Panama

View user's profile Send private message

PostPosted: Wed Apr 25, 2018 11:54 am     Reply with quote

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



Joined: 03 Aug 2009
Posts: 1067
Location: Panama

View user's profile Send private message

PostPosted: Wed Apr 25, 2018 12:33 pm     Reply with quote

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



Joined: 11 Mar 2010
Posts: 19195

View user's profile Send private message

PostPosted: Wed Apr 25, 2018 12:37 pm     Reply with quote

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



Joined: 01 Jul 2010
Posts: 9081
Location: Greensville,Ontario

View user's profile Send private message

PostPosted: Wed Apr 25, 2018 2:00 pm     Reply with quote

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



Joined: 26 Sep 2003
Posts: 216
Location: Northern Indiana

View user's profile Send private message

PostPosted: Thu Apr 26, 2018 11:37 am     Reply with quote

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



Joined: 11 Mar 2010
Posts: 19195

View user's profile Send private message

PostPosted: Thu Apr 26, 2018 12:13 pm     Reply with quote

He is not alone... Smile

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



Joined: 01 Jul 2010
Posts: 9081
Location: Greensville,Ontario

View user's profile Send private message

PostPosted: Thu Apr 26, 2018 12:21 pm     Reply with quote

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



Joined: 11 Mar 2010
Posts: 19195

View user's profile Send private message

PostPosted: Thu Apr 26, 2018 12:30 pm     Reply with quote

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



Joined: 26 Sep 2003
Posts: 216
Location: Northern Indiana

View user's profile Send private message

PostPosted: Thu Apr 26, 2018 1:05 pm     Reply with quote

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



Joined: 03 Aug 2009
Posts: 1067
Location: Panama

View user's profile Send private message

PostPosted: Fri Apr 27, 2018 1:33 pm     Reply with quote

Jay,

Quote:
I find it 'interesting' that 'they' don't consider the time to put/get data from a temp variable to be important.


I believe "they" dont, not because they are not aware of it, but because all "in-place" sorting algo's which use Swaps must do this extra temp. holding move.

Now, by the same logic, 1 swap would consists of 2 array writes and 1 temp hold write.

In which case then, I am sorting a 40 element array in 20 swaps.
Which would mean I have O(n/2) swaps? errr... right?

I'm trying to figure out if i protect this with my life or simply dump it out into the library for the world and forget about it.
_________________
CCS PCM 5.078 & CCS PCH 5.093
Ttelmah



Joined: 11 Mar 2010
Posts: 19195

View user's profile Send private message

PostPosted: Fri Apr 27, 2018 1:47 pm     Reply with quote

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.
Display posts from previous:   
Post new topic   Reply to topic    CCS Forum Index -> General CCS C Discussion All times are GMT - 6 Hours
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group