Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hey monks, Can you tell me how to improve this sort? We thought about Perl's sort function but a bubble sort seemed to be correct for this. We needed to address nesting of string values as well as regular ordering. What do you think? 
#! /usr/bin/perl -w
use strict;


my @v;
$v[0]=via_format(1,2);
$v[1]=via_format(1,12);
$v[2]=via_format(1,4);
$v[3]=via_format(6,12);
$v[4]=via_format(1,5);
&printV;

for (my $swapping = 1; $swapping >= 0; $swapping--) {
    for (my $j=0; $j < $#v; $j++ ) {
        if ( (index($v[$j],$v[$j+1]) >= 0)       || 
             (length($v[$j+1]) < length($v[$j])) ||
             ($v[$j+1] lt $v[$j] && length($v[$j+1]) <= length($v[$j])
+) ) {
              @v[$j,$j+1] = @v[$j+1,$j];
              $swapping   = 1;
        } 
    }
}


&printV;

sub printV {
   my $i;
   print "----------------------\n";
   for ($i=0; $i <= $#v; $i++) {
      print $v[$i] . "\n";
   }
}


sub via_format {
   my $a = shift;
   my $b = shift;
   return join('+', map{sprintf("%02d", $_)} ($a..$b) );

}

[download]
Thanks.

Replies are listed 'Best First'.
Re: Funky sorting
by Fletch (Bishop) on Nov 10, 2001 at 04:59 UTC

    . . . a bubble sort seemed to be correct for this.

    I have nothing constructive to offer, I just wanted to thank you for the best laugh I've had today.

    Update: It's been brought to my attention that my remark may need some explanation. Basically, nobody with any formal computer science training would ever just use a bubble sort for generic sorting. BS is O(n^2) (CS talk that it performs on the order of the square of the number of elements to be sorted) with a terrible average performance. Perl's builtin sort uses quicksort which is O(n log n) for instance. There are cases where a bubble sort can work (e.g. you know your initial ordering is almost sorted), but for the most part you want to steer clear of it.

    For more information, see a text such as Volume Three of Knuth's Art of Computer Programming or Mastering Algorithms with Perl (ISBN 1565923987).

[reply]
      Never fear, fletch, I chuckled as well, though it was a rueful one.

      General Plea - Please, please, please read Mastering Algorithms, or any algorithms book that discusses sorting (and a good one will).

      General Rant - I don't know how many times a week I point out logical faults, sorting faux pas, etc. to those that wouldn't have made the errors if they would simply RTFM (I suppose that this rant has more deep seated roots...). I even suggest and offer examples from my ample at work library, but they just don't care. It blemishes the good name of legitimate programmers everywhere. I'm not suggesting that this is a case of that, but it just touches a nerve.

      C-.

[reply]
Re: Funky sorting
by blakem (Monsignor) on Nov 10, 2001 at 04:34 UTC
    We needed to address nesting of string values as well as regular ordering
    I don't understand what you mean by this. It looks like you're just sorting on the length of the string. Replacing your big for loop with the following line produces the same output. 
    @v = sort {length($a) <=> length($b)} @v;

    [download]
[reply]
[d/l]

      Yeah, that index threw me for quite a while. I think a more accurate replacement is: 

      @v= sort {
    length($a) <=> length($b)  ||  $a cmp $b
} @v;

      [download]
      however (sort first by length and sort strings of the same length lexigraphically).

      Basically, the use of index doesn't end up changing anything since $a can only be a substring of $b if it is either shorter than $b or it is exactly equal to $b.

              - tye (but my friends call me "Tye")
[reply]
[d/l]
        Ah, you're right. For some reason I thought the data being sorted would never tie, but that is obviously wrong. (The first "elements" got magically sorted in my head.... meaning length was the only defining characteristic. i.e. two strings starting with same two digits and having the same length are equal by construction.)

        -Blake

[reply]
        So basically I've been sitting here overcomplicating things. Damn.

        Thanks

[reply]
Re: Funky sorting
by mitd (Curate) on Nov 10, 2001 at 09:32 UTC
    One can get terribly religious about sorts :) So here are few little extracted quotes. They all attributed to Tom Horsley and can be found in perl 5.6.1 source code (pp_ctl.c comments to qsort functions)
    "This is the most wonderfulest possible qsort I can come up with (and still be mostly portable) My (limited) tests indicate it consistently does about 20% fewer calls to compare than does the qsort in the Visual C++ library, other vendors may vary."

    and one of my favourites

    ...they shuffled back towards the rear of the line. 'No, not at the rear!' the slave-driver shouted. 'Three files up. And stay there...


    mitd
    Interactive!, Paper tape is interactive.
    If don't believe me I can show you my paper cut scars.
[reply]
Re: Funky sorting
by Anonymous Monk on Nov 11, 2001 at 02:42 UTC
    for sorting on a small list, say 10 elements or so, wouldn't bubble sort have a lot smaller overhead than a quck sort?

    I would run some tests, but I care more about typing less in my programs than a small speed improvement :)

[reply]
      As a general response to this question, here's the time reference table for the different sorts:

      Sort Worst Case Average Case
      Selection Sort N2 N2
      Bubble Sort N2 N2
      Insertion Sort N2 N2
      Mergesort N*Log2N N*Log2N
      Quicksort N2 N*Log2N
      Radix Sort N N
      Tree Sort N2 N*Log2N
      Heap Sort N*Log2N N*Log2N

      It really depends on how well the data is presorted.

      If it is sorted, bubble sort can be as efficient as O(N), but it is usually O(N2).

      The worst case for a quick sort is just the opposite. If the data is already sorted and the smallest item is chosen as the pivot, time can be O(N2), but for most data sets it's (NlogN).

      C-.

[reply]

Back to Seekers of Perl Wisdom