I made two TI-BASIC sorters last night. A bubble sorter and a recursive sorter. I will post the code later to see if anyone has optimizations. The bubble sort program sorts a list generated by rand(1,100,50) in about 43 seconds. The recursive sorter program sorts the same list in about 24 seconds. How is that for timing? Question
Hmmm, there was a golfing competition a while back where members had to create sorting algos. Of course, the SortA() and SortD() tokens were banned. I think some people had gotten down to a few seconds for 256 element lists, so your solution is definitely not the most optimal, but it is pretty good, given the fact that there were also entries that took multiple minutes. I remember being surprised at how difficult it was to implement an efficient sorting algo. Good job! I'd love to see the code you've come up with and maybe compare it to the entries to the golfing contest!

EDIT: I had posted my solution and Lirtosiast optimized it further. Here is the solution that came out of that:

Code:
1->B
For(A,1,256
   For(B,B,sum(L1<=A
      A->L2(B
   End
End
L2->L1
Recursive Sort

Code:
prgmQSORT:

N+1->N

If L>=R
Return

L1(L->P

L->I
R->J

While I<=J
   While L1(I)<P
      I+1->I
   End
   While L1(J)>P
      J-1->J
   End
   If I<=J
   Then
      L1(I->T
      L1(J->L1(I
      T->L1(J
      I+1->I
      J-1->J
   End
End

L->L2(N
R->L3(N
I->L4(N
J->L5(N

If L<(I-1)
Then
   I-1->R
   prgmQSORT
End

If I<R
Then
   I->L
   prgmQSORT
End

N-(N!=1)->N
L2(N->L
L3(N->R
L4(N->I
L5(N->J

Bubble sort

Code:
prgmBSORT
For(C,1,dim(L1
   For(I,C+1,dim(L1
      If L1(C)>L1(I)
      Then
         L1(C)->L
         L1(I)->L1(C)
         L->L1(I)
      End
   End
End

For(C,1,dim(L1
   Disp L1(C
End


EDIT:

Wow! How does yours even work? What does For(B,B,sum(L1<=B do? It is quite the line of code!
Lol, i remember half attempting to participate in that contest, the attempts were burned in much fire (by me, because they were disgraceful) Very Happy
Switchblade wrote:
EDIT:

Wow! How does yours even work? What does For(B,B,sum(L1<=B do? It is quite the line of code!

Here, I annotated it. It isn't really any specific algo, but ressembles counting sort.

Code:
1->B //initialize B
For(A,1,256 //for each element in the list
   For(B,B,sum(L1<=A //count how many times A is in L1
      A->L2(B //add A to L2 as many times as it appears in L1
   End
End
L2->L1 //put L2 in L1, because the output had to be in L1
mr womp womp: Wow, I didn't realize you could do that! Did yours win?
mr womp womp wrote:
Switchblade wrote:
EDIT:

Wow! How does yours even work? What does For(B,B,sum(L1<=B do? It is quite the line of code!

Here, I annotated it. It isn't really any specific algo, but ressembles counting sort.

Code:
1->B //initialize B
For(A,1,256 //for each element in the list
   For(B,B,sum(L1<=A //count how many times A is in L1
      A->L2(B //add A to L2 as many times as it appears in L1
   End
End
L2->L1 //put L2 in L1, because the output had to be in L1


This assumes that the range of numbers in the array will also be between 1 and 256.
oldmud0 wrote:
mr womp womp wrote:
Switchblade wrote:
EDIT:

Wow! How does yours even work? What does For(B,B,sum(L1<=B do? It is quite the line of code!

Here, I annotated it. It isn't really any specific algo, but ressembles counting sort.

Code:
1->B //initialize B
For(A,1,256 //for each element in the list
   For(B,B,sum(L1<=A //count how many times A is in L1
      A->L2(B //add A to L2 as many times as it appears in L1
   End
End
L2->L1 //put L2 in L1, because the output had to be in L1


This assumes that the range of numbers in the array will also be between 1 and 256.

Oldmud, indeed, that was a specification of the contest. A simple Dim() would generalize that right up, at the expense of some speed. And no, mine did not win.
Could I see the code from the winner?
Sure, this is the routine from lirtosiast, the input was in both L1 and Ans:

Code:
not(Ans->L2
For([recursiven],1,dim(Ans
   1+L2(L1([recursiven]->L2(L1([recursiven]
End
1->[recursiven]
cumSum(L2->L2
For(X,1,dim(Ans
   For([recursiven],[recursiven],L2(X
      X->L1([recursiven]
   End
End


Source: https://www.cemetech.net/forum/viewtopic.php?t=12653
What is [recursiven]?
Here's my code to sort a list of 256 numbers known to be between 1 and 1000000 in 11 seconds. The range can be extended arbitrarily, but it won't be efficient if many elements are bunched up.

It's bucket sort followed by insertion sort. Still significantly slower than SortA( which takes only 3 seconds despite using the slower selection sort algorithm. That's the power of assembly—much less overhead.


Code:
//L2 is end indices for each of 256 buckets
//L3 is which bucket the corresponding number in L1 goes in
//L4 is copy of L1
42->rand
randInt(1,1000000,256->L1
L1->L5
SortA(L5      //sorted list in L5
startTmr->T
not(L1->L2    //all zeros
L2->L4    //initalize L4
1+int(L1*256/|E6->L3    //now all entries of L3 are integers between 1 and 256
Disp checkTmr(T

//bucket sort, 5 seconds:
For([recursiven],1,256
   1+L2(L3([recursiven]->L2(L3([recursiven]
End
//L2 holds the size of each bucket
cumSum(L2->L2
//now L2 holds the end index of each bucket, so we can put the numbers in the buckets:
For([recursiven],1,256
   L3([recursiven]->I%
   L1([recursiven]->L4(L2(I%
   L2(I%)-1->L2(I%
End
//the almost-sorted list is in L4
Disp checkTmr(T
L4->L1

//insertion sort, 4 seconds:
For([recursiven],2,dim(L4
   //n-1 elements have been sorted already
   //example n=4: {4 6 8 2 10 ...}
   
   [recursiven]->I%
   While L1(I%)<L1(max(1,I%-1)     //prevent error at 1. Never true with I%=1
      L1(I%)->PV                  //swap L1(I%) and L1(I%-1)
      L1(I%-1->L1(I%
      PV->L1(I%-1
      I%-1->I%
   End
End
Disp checkTmr(T
Disp min(L5=L1


By the way, [recursiven] is a variable in Seq mode that, like all system variables, is slightly faster to access than capital-letter variables, but like capital-letter variables can be used in For( loops.
Switchblade wrote:
What is [recursiven]?


The terminology [recursiven] is used by SourceCoder to differentiate between the lowercase letter 'n', and the functional n.

To get it on-calc, press the following buttons:
[2nd][0][log][enter]

It's also the token that the [x,τ,θ,n] button gives if the calculator's graphing mode is SEQ, or sequential.
To put your calculator in sequential mode, go to the catalogue and select it (for programs) by pressing these buttons (in this order):

[2nd][0][ln][↓][↓][↓][↓][↓][↓][↓][↓][↓][↓][enter] (press the down arrow 10 times)

or, to manually set it, press these buttons:
[mode][↓][↓][↓][→][→][→][enter]

The keys work on the CE, to learn more on sequential functions, click here.
  
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
Page 1 of 1
» All times are UTC - 5 Hours
 
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

 

Advertisement