Don't have an account? Register now to chat, post, use our tools, and much more.
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? 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) 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:
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:
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```
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.
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][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][ln][↓][↓][↓][↓][↓][↓][↓][↓][↓][↓][enter] (press the down arrow 10 times)

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

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.

»
» All times are GMT - 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