Very Computer

by DS » Fri, 21 May 1999 04:00:00

Hello. In ksh sort, how can u specify a stable sort?

Thanks.

DS

by **Kurt J. Lanz** » Fri, 21 May 1999 04:00:00

> Hello. In ksh sort, how can u specify a stable sort?

I am curious:

(1) What is a "stable sort"?
(2) Why do you not think the man page answers your question?

by **Ken Pizzi** » Fri, 21 May 1999 04:00:00

>Hello. In ksh sort, how can u specify a stable sort?

Most implementations of sort do not offer such an option;
if yours does, the mechanism should be documented in the
man page.

A crude way of simulating a stable sort is:
nl -ba file | sort -k2 | cut -d' ' -f2-
where the character between the 's is a TAB, and the
"-k2" option should be whatever sort criteria you need,
with adjustment for the added leading line number.

N.B.: since the question was asked by another --- a sort
is said to be "stable" if two records whose keys are equal
maintain the same relative ordering after the sort as they
possessed before the sort. Like the above simulation shows,
this is equivalent to augmenting the key with the original
record number (as the lowest-priority comparison).

--Ken Pizzini

by **Juergen Hein** » Fri, 21 May 1999 04:00:00

>> Hello. In ksh sort, how can u specify a stable sort?

I guess you mean the sort command, then use the -s option.

Quote:
>I am curious:

Nosey, eh ...

Quote:>(1) What is a "stable sort"?

key1 value1
key1 value2
key1 value3
key2 value4

... a stable sort gurantees the first three lines stay in that order
if sorted by key# (all key1's assumed to be the same). Bubble sort
is stable IIRC, qsort() is not.

Quote:>(2) Why do you not think the man page answers your question?

Cannot answer this one. Used man sort to look the -s option up too,
tricks of the trade, but don't tell 8)

Cheers,
Juergen

--
\ Real name : Jrgen Heinzl \ no flames /

by **Kurt J. Lanz** » Fri, 21 May 1999 04:00:00

[ snip ]

> ... a stable sort gurantees the first three lines stay in that order
> if sorted by key# (all key1's assumed to be the same). Bubble sort
> is stable IIRC, qsort() is not.

> >(2) Why do you not think the man page answers your question?
> Cannot answer this one. Used man sort to look the -s option up too,
> tricks of the trade, but don't tell 8)

Hmm... My sort (Solaris) (1) doesn't have a -s option and (2) explicitly
states that stability is not guaranteed -- so maybe the original
poster's question isn't so dumb after all. Although, as I recall, one
can force stability by using 'cat -n' to number the input lines,
changing the key definition to include the line number as the last field
in the key, and cut to remove the line number from the output.

by **Juergen Hein** » Fri, 21 May 1999 04:00:00

>[ snip ]

>> ... a stable sort gurantees the first three lines stay in that order
>> if sorted by key# (all key1's assumed to be the same). Bubble sort
>> is stable IIRC, qsort() is not.

>> >(2) Why do you not think the man page answers your question?
>> Cannot answer this one. Used man sort to look the -s option up too,
>> tricks of the trade, but don't tell 8)

>Hmm... My sort (Solaris) (1) doesn't have a -s option and (2) explicitly
>states that stability is not guaranteed -- so maybe the original
>poster's question isn't so dumb after all. Although, as I recall, one
>can force stability by using 'cat -n' to number the input lines,
>changing the key definition to include the line number as the last field
>in the key, and cut to remove the line number from the output.

Oh I did not say it was dumb, but you are right with the rest of course ...
I know where the corner is ...

Cheers,
Juergen

--
\ Real name : Jrgen Heinzl \ no flames /