Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #49142 > unrolled thread

Tricky sorting

Back to article view | Back to comp.lang.forth

Contents

  Tricky sorting "WJ" <w_a_x_man@yahoo.com> - 2016-07-14 06:13 +0000
    Re: Tricky sorting "WJ" <w_a_x_man@yahoo.com> - 2016-07-14 06:25 +0000
    Re: Tricky sorting "WJ" <w_a_x_man@yahoo.com> - 2016-07-14 06:44 +0000
      Re: Tricky sorting Richard Todd <richard.wesley.todd@gmail.com> - 2016-07-14 14:56 -0700

#49142 — Tricky sorting

You have a list of pairs.  After sorting, if you look only
at the first element of each pair, it should seem that
nothing has changed.

Example.  (Since we're temporarily ignoring the second
elements, they're represented by underscores.)

Before:
[(5,_); (5,_); (2,_); (2,_)]

After:
[(5,_); (5,_); (2,_); (2,_)]

However, the list should be ordered by the second elements,
in so far as that can be done without changing the order of
the first elements.

Before:
[(5,8); (5,0); (2,6); (2,3)]

After:
[(5,0); (5,8); (2,3); (2,6)]



OCaml:

List.sort
  (fun (a,b) (c,d) -> if a=c then compare b d else 0)
  [3,5; 3,1; 3,3; 1,2; 1,7; 1,1; 888,9; 3,42; 3,0] ;;5

 ===>
[(3, 1); (3, 3); (3, 5); (1, 1); (1, 2); (1, 7); (888, 9); (3, 0); (3, 42)]


For this task, or any task not trivially simple, why would one
want to use ANS Forth, a language lacking sorting, lists, arrays,
tuples, and just about everything else?


-- 
Amazon bans book.  After nearly a month on the site, all traces of the book and
its 80 reviews have been removed.
http://jamesfetzer.blogspot.com/2015/11/debunking-sandy-hook-debunkers-5.html
https://www.youtube.com/watch?v=EEl_1HWFRfo

[toc] | [next] | [standalone]

#49144

WJ wrote:

>   [3,5; 3,1; 3,3; 1,2; 1,7; 1,1; 888,9; 3,42; 3,0] ;;5

Remove the 5 at the end.

[toc] | [prev] | [next] | [standalone]

#49146

WJ wrote:

> For this task, or any task not trivially simple, why would one
> want to use ANS Forth, a language lacking sorting, lists, arrays,
> tuples, and just about everything else?

Also lacking structures (records), hash-tables (associative arrays),
string-handling functions, a regular-expression engine, integers
of unlimited size, closures, etc.

However, the simple souls who use it are mightily impressed by
the way it can actually add two integers together:

2 2 + . 4 ok

Wow! It's even better than an abacus!

-- 
The report card by the American Society of Civil Engineers showed the national
infrastructure a single grade above failure, a step from declining to the point
where everyday things simply stop working the way people expect them to. ---
washingtonpost.com/local/trafficandcommuting/us-infrastructure-gets-d-in-annual-report/2013/03/19/c48cb010-900b-11e2-9cfd-36d6c9b5d7ad_story.html

[toc] | [prev] | [next] | [standalone]

#49166

The first group of words are helpers for tuples.  The second group is the sorting
algorithm I chose.  The third is the criteria given in the problem (equivalent of the
lambda func you used)


: (,) swap , , ;
: tuples 2 cells * ;
: .(,)  ." ( " dup @ . ." , " cell+ @ . ." ) " ;
: @2nd cell+ @ ;
: !2nd cell+ ! ;
: .tuples  dup @ tuples swap cell+ swap bounds ?DO I .(,)  1 tuples +LOOP cr ;

: grab2 ( addr -- t1@ t0@ ) dup @2nd swap 1 tuples - @2nd ;
: swap-adjacent ( addr1 -- addr0 ) dup dup grab2 rot !2nd swap 1 tuples - tuck !2nd ;
: in-bounds? ( lst cur -- t/f )  2dup < ;
: sort ( cmp lst -- lst )   
   dup dup @ 1- tuples swap cell+ 1 tuples + swap bounds    
   ?DO  ( cmp lst )
      I BEGIN in-bounds? WHILE dup 1 tuples - over 
      4 pick execute WHILE swap-adjacent REPEAT THEN drop
   1 tuples +LOOP 
   nip ;

: criteria ( a b -- a<b? ) 
   over @ over @ = IF @2nd swap @2nd < ELSE 2drop 0 THEN  ;


Example use:

VARIABLE lst 9 lst !
   3 5 (,)  3  1 (,)  3 3 (,)
   1 2 (,)  1  7 (,)  1 1 (,)
 888 9 (,)  3 42 (,)  3 0 (,)
 
' criteria lst sort  .tuples 
( 3 , 1 ) ( 3 , 3 ) ( 3 , 5 ) ( 1 , 1 ) ( 1 , 2 ) ( 1 , 7 ) ( 888 , 9 ) ( 3 , 0 ) ( 3 , 42 )

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web