This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's
Technology & Calculator Open Topic subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.
Math and Science =>
Technology & Calculator Open Topic
| Author |
Message |
|
simonzack
Advanced Newbie
Joined: 25 Dec 2007
Posts: 71
|
 Posted: 08 Jan 2008 04:03:17 am Post subject: |
|
|
Well, I'm currently using a shell sort for my project, and by the gap sequence n^2, as shifting might be faster than divu
Should I change it to a quick sort because of bad gap sequence, or should I stick to what's already done?
Well, mostly the array size would be about 50, maybe 70 |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 08 Jan 2008 07:13:51 am Post subject: |
|
|
Have you tried using Sedgewick's sequence for your Shellsort implementation? Quicksort's O(n log n) operation count doesn't pay off until you have about a thousand or so elements.
thornahawk
Last edited by Guest on 08 Jan 2008 07:15:33 am; edited 1 time in total |
|
| Back to top |
|
|
simonzack
Advanced Newbie
Joined: 25 Dec 2007
Posts: 71
|
| Posted: 08 Jan 2008 08:53:30 am Post subject: |
|
|
| Well, I'd sure want to try them, but the prob is, i need to devide the numbers by the total amount of indexes which cause a lot of calculation process... and it's frustrating. Though I'd try it and compare it to the original 1,2,4,8,.... Would that sequence still be faster? |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 08 Jan 2008 10:50:03 am Post subject: |
|
|
| Why would you ever need to divide for shell sort? When doing insertion sort on every kth element, you just increment an index by k, and stop if it goes over the total size of the array. In fact, none of the shell sort implementations on Wikipedia divide anything except to calculate the gap sequence. Which you could just store in an array. |
|
| Back to top |
|
|
simonzack
Advanced Newbie
Joined: 25 Dec 2007
Posts: 71
|
| Posted: 09 Jan 2008 10:59:46 pm Post subject: |
|
|
I thought for a moment calculting how many steps itll take to go over will get a faster loop,  well, seemed just testing when itll go over is faster, thanks  |
|
| Back to top |
|
|
|
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.
»
Go to Registration page
