Sorting lists
Frederick R. Phelan Jr.
Suppose I have two lists which are linked at least logically,
now I sort one, how do I apply the same sort sequence to
another so that the data are still logically connected,
a la a database sort procedure?
Regards,
Fred
----------------------------------------------
Fred Phelan
Polymer Composites
National Institute of Standards and Technology
----------------------------------------------
e-mail .... fr...@poly2.nist.gov
Frederic...@nist.gov
----------------------------------------------
Fil Machi
Here are two ways to do this. There may be a more direct way within
TCL that I do not know about (I'm not a very experienced TCL user).
I used Unix files in the examples below just to show that the ideas
have wide applicability.
The first method can be described as: determine the actual permutation
that resulted when the file(list) was sorted; then apply this same
permutation to the second file(list).
The second method is: combine the two files(lists) by concatenating
corresponding lines(elements); sort the result using the component from
the first file as the sort key; finally, split the result apart.
Both methods have time complexity nlogn because of the sorts. The
specific examples below scale nicely and can be used on large files.
In terms of space, both methods use sort, so they both need at least
whatever space the sort algorithm needs. The first method also adds a
small amount to each line(list element). The second method copies both
input files. It may be possible to edit the originals instead of
copying them, and restore them at the end.
Fil Machi
f...@cea.berkeley.edu
Here is a shell script that illustrates the first method.
--------------------------------------------------------
#!/bin/sh
#PATH=your-path-here
cd /tmp
cat >names << !
jane doe
zachary jones
sam spade
michael valentine smith
anna bell
princess di
!
cat >phones << !
555-1111
555-2222
555-3333
555-4444
555-5555
555-6666
!
# Sort the names and record the resultant inverse permutation
# by noting how the original line numbers were rearranged.
#
nawk '{ print NR, $0 }' names | sort +1 >names.temp
cut -d' ' -f2- names.temp >names.sorted
nawk '{ print NR, $1 }' names.temp >invperm
# Invert the inverse permutation to determined the original permutation.
#
nawk '{ print $2, $1 }' invperm | sort +0n -1 >perm
echo; echo "invperm:"; cat invperm
echo; echo "perm:"; cat perm
# Adjoin the permutation to the phones file, then apply it.
#
paste -d' ' perm phones | sort +1n -2 | cut -d' ' -f3- >phones.sorted
# Show before and after.
#
echo; echo "original:"; paste -d' ' phones names
echo; echo "sorted:"; paste -d' ' phones.sorted names.sorted
echo; echo rm names phones names.temp names.sorted invperm perm phones.sorted
--------------------------------------------------------
Here is a shell script that illustrates the second method.
--------------------------------------------------------
#!/bin/sh
#PATH=your-path-here
cd /tmp
cat >names << !
jane doe
zachary jones
sam spade
michael valentine smith
anna bell
princess di
!
cat >phones << !
555-1111
555-2222
555-3333
555-4444
555-5555
555-6666
!
# Use a delimiter that does not appear in either file.
#
paste -d'|' phones names | sort -t'|' +1 >sorted.temp
cut -d'|' -f1 sorted.temp >phones.sorted
cut -d'|' -f2 sorted.temp >names.sorted
# Show before and after.
#
echo; echo "original:"; paste -d' ' phones names
echo; echo "sorted:"; paste -d' ' phones.sorted names.sorted
echo; echo rm names phones sorted.temp names.sorted phones.sorted
--------------------------------------------------------