help in sort

[uva]

hello monks, help me in that

%output_pts =(7=>"raja",2=>"ananth",3=>"guru",4=>"uvaaraj");
@ptkeys = keys %output_pts;
@sortedkeys = sort numeric_sort @ptkeys;
print "\n@ptkeys";
sub numeric_sort {
print " $a,$b ";
$a cmp $b; }

=========================================================== explai the procedure involved in this sorting...i mean what basis it is comparing with the values... actually arguments are stored in @_ inside subroutine..how does $a and $b gets the value.....is it like bubble sort....

[Corion]

I wonder if you'd care to suggest how we could improve the documentation for sort to make it more obvious how to solve your problem. Currently the docs say this:

... If the subroutine's prototype is "($$)", the elements to be compared are passed by reference in @_, as for a normal subroutine. This is slower than unprototyped subroutines, where the elements to be compared are passed into the subroutine as the package global variables $a and $b (see example below). Note that in the latter case, it is usually counter-productive to declare $a and $b as lexicals. ...

Examples:

    # sort lexically
    @articles = sort @files;

    # same thing, but with explicit sort routine
    @articles = sort {$a cmp $b} @files;

    # now case-insensitively
    @articles = sort {uc($a) cmp uc($b)} @files;

    # same thing in reversed order
    @articles = sort {$b cmp $a} @files;

    # sort numerically ascending
    @articles = sort {$a <=> $b} @files;

    # sort numerically descending
    @articles = sort {$b <=> $a} @files;

[uva]

thanks for your reply corion... in the mentioned suroutine i used print statement,,it is printing values like {4,7 4,2 3,4 2,4 7,4 7,4 2,3}....in what logic it is printing these values

[jonadab]

in the mentioned suroutine i used print statement,,it is printing values like {4,7 4,2 3,4 2,4 7,4 7,4 2,3}....in what logic it is printing these values

Oh. Unless your goal is to experiment with Perl's sort builtin, you should not print anything (or do anything with side-effects, other than _perhaps_ cache computed values). Your sorting subroutine is actually a _comparison_ subroutine, i.e., sort will call it each time it needs to compare two of the items in the list to see which should sort earlier. Each item might be compared multiple times to different other items, but it will _not_ necessarily be compared to _every_ other item (since that would be terribly inefficient). If you want to print out the list of sorted values, you should sort it first, then iterate over the list and print the values.

If you were just curious and experimenting, then like I said I think it might be a heap sort, but I could be wrong about that. The easiest way to find out would be to look in the source code for perl. No, wait, perldoc might say... Ah, yes, it does:

Perl 5.6 and earlier used a quicksort algorithm to implement sort. That algorithm was not stable, and could go quadratic. (A stable sort preserves the input order of elements that com- pare equal. Although quicksort's run time is O(NlogN) when averaged over all arrays of length N, the time can be O(N**2), quadratic behavior, for some inputs.) In 5.7, the quicksort implementation was replaced with a stable mergesort algorithm whose worst case behavior is O(NlogN). But benchmarks indi- cated that for some inputs, on some platforms, the original quicksort was faster. 5.8 has a sort pragma for limited con- trol of the sort. Its rather blunt control of the underlying algorithm may not persist into future perls, but the ability to characterize the input or output in implementation independent ways quite probably will.

So if you have a recent perl it's probably a mergesort. HTH.HAND

[jonadab]

.i mean what basis it is comparing with the values

On the basis you specify in your sort subroutine (in this case, numeric_sort).

actually arguments are stored in @_ inside subroutine

Sorting subroutines are special, for historical reasons.

how does $a and $b gets the value

Perl's sort builtin takes care of that, automatically.

is it like bubble sort

No, something rather faster. I think thought it might be a heapsort, but I could be was misremembering, or and it might have changed at some point. In any event, that's an implementation detail of the type you shouldn't worry about. The sort is one of the pieces of perl that's fairly well optimized, so unless you're doing something rather unusual, it will generally perform rather better than any sort you can code by hand. The exception is when the comparison operation itself is very expensive (e.g., because it involves a lookup over a slow network), in which case a common optimization called a Schwartzian Transform can be used to perform the expensive part of the operation only once per each item in the list.