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 Previous  1, 2
 
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

PostPosted: Fri Apr 27, 2018 2:14 pm     Reply with quote

Quote:
Honestly why not just use the Quick sort implementation supplied with the compiler?


I wasn't trying to make new a sorting algorithm.

"Lets not, invent, create, or try anything else. lets just use what we are fed"
Thats your conclusion?
_________________
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: Fri Apr 27, 2018 2:16 pm     Reply with quote

Quote:
Comparisons involve just as much work as a swap. You have to access every byte in the values to do a comparison.


I agree.

Thats why most of the stuff I've seen give you both swap and comparison performance values.

EDIT:Cool site with visuals i found while researching.
https://www.toptal.com/developers/sorting-algorithms

g.
_________________
CCS PCM 5.078 & CCS PCH 5.093
Ttelmah



Joined: 11 Mar 2010
Posts: 19195

View user's profile Send private message

'improving'
PostPosted: Fri Apr 27, 2018 11:17 pm     Reply with quote

Gabriel wrote:
Quote:
Honestly why not just use the Quick sort implementation supplied with the compiler?


I wasn't trying to make new a sorting algorithm.

"Lets not, invent, create, or try anything else. lets just use what we are fed"
Thats your conclusion?


No. But it is always worth looking at the mathematics of how code works. Qsort is a well documented, and has quite poor worst case performance. If you want to improve it, then write a dual pivot implementation (published in 2009), or try a mergesort implementation. Where Qsort takes a lot of time, is when the pivot point is badly selected. Median selection of this is a way that Qsort can be massively improved. All things well worth trying. However the number of elements you describe seems to be small, and the actual sorting time should be quite small. Spending a lot of time 'improving' algorithms when the existing ones work well enough, does seem rather pointless....
RF_Developer



Joined: 07 Feb 2011
Posts: 839

View user's profile Send private message

PostPosted: Thu May 03, 2018 4:45 am     Reply with quote

Quote:
Thats why most of the stuff I've seen give you both swap and comparison performance values.


An important point is that "swaps" and "comparisons" are very implementation dependant, while all sorting algorithms use them. Therefore, they are useful as a metric for comparing algorithm performance independantly of implementation performance. Also some algorithms suit some processor implementations and instruction sets so the relative comparisons of speed may well be different.

Also, the nature of the data affects which algorithm is "best" for a particular application. In general, the effort in implementing and testing all such algorithms generally far outweighs any benefit for tens of points. Only when the number of data points get up higher is there really that much difference. Put another way, if you're sorting only a few tens of points, its not worth spending much time, if any, worrying about which algorithm to use.

A great amount of time and brainpower has been expended on sorting computational algorithms over the decades, possibly more so than any other class of algorithms. For example the Donald Knuth devoted an entire volume of his "The Art of Computer Programming" - the "bible" of computational algorithms, to sorting and the closely related searching. The ultimate sorting algorithm is something of a holy grail for computing. That means its incredibly unlikely that anyone will stumble across anything better than today's best. Instead it probably requires a lot of detailed, dedicated research.

It is, however, quite possible to find one that appears better that works faster one or a few limited sets of data, and to assume that it will be better for most data sets. As can be seen from that infographic, the simple, naive insertion sort works faster than all others with nearly sorted data, but is way slower for more random data, but then, not all datasets are random.
Gabriel



Joined: 03 Aug 2009
Posts: 1067
Location: Panama

View user's profile Send private message

PostPosted: Thu May 03, 2018 6:46 am     Reply with quote

@RF_Developer:

Thank you for your well put thoughts.

Quote:
That means its incredibly unlikely that anyone will stumble across anything better than today's best. Instead it probably requires a lot of detailed, dedicated research


I've kept searching, testing, and looking for a similar algorithm since I've agreed with your point above since day1, but hey, there was always a chance for it to be unique. Everyone has the right to a moment of clarity from time to time.

By now I think i can conclude that my algorithm is a variation/improvement? of shell sort or comb sort (not heard of comb sort until yesterday).... somewhere in between, not quite either of them.

I've decided to clean up a small test program and post it up for others to try or shred to pieces. Surely someone will show up with "pfft.. thats just xxxx Sort, but with more steps".

G.
_________________
CCS PCM 5.078 & CCS PCH 5.093
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 Previous  1, 2
Page 2 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