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
Author Message
Gabriel

Joined: 03 Aug 2009
Posts: 960
Location: Panama

Sorting Algorithms
Posted: Wed Apr 25, 2018 9:42 am

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)

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 4.135 & CCS PCH 5.013
temtronic

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

 Posted: Wed Apr 25, 2018 9:49 am 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: 960
Location: Panama

 Posted: Wed Apr 25, 2018 9:59 am 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 4.135 & CCS PCH 5.013
temtronic

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

 Posted: Wed Apr 25, 2018 10:38 am 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: 960
Location: Panama

 Posted: Wed Apr 25, 2018 11:54 am 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 4.135 & CCS PCH 5.013
Gabriel

Joined: 03 Aug 2009
Posts: 960
Location: Panama

 Posted: Wed Apr 25, 2018 12:33 pm 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 4.135 & CCS PCH 5.013
Ttelmah

Joined: 11 Mar 2010
Posts: 13261

 Posted: Wed Apr 25, 2018 12:37 pm 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: 6153
Location: Greensville,Ontario

 Posted: Wed Apr 25, 2018 2:00 pm 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: 186
Location: Northern Indiana

 Posted: Thu Apr 26, 2018 11:37 am So YOU were the other guy that owned one of those! (TRS-80).
Ttelmah

Joined: 11 Mar 2010
Posts: 13261

 Posted: Thu Apr 26, 2018 12:13 pm 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

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

 Posted: Thu Apr 26, 2018 12:21 pm 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: 13261

 Posted: Thu Apr 26, 2018 12:30 pm 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: 186
Location: Northern Indiana

 Posted: Thu Apr 26, 2018 1:05 pm 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: 960
Location: Panama

Posted: Fri Apr 27, 2018 1:33 pm

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 4.135 & CCS PCH 5.013
Ttelmah

Joined: 11 Mar 2010
Posts: 13261

 Posted: Fri Apr 27, 2018 1:47 pm 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: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMT - 6 HoursGoto page 1, 2  Next Page 1 of 2

 Jump to: Select a forum Software----------------General CCS C DiscussionCode LibraryEZ App Lynx Hardware----------------CCS ICD / Mach X / Load-n-Go
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