Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Advanced Bubble Sort

by Anonymous Monk
on Oct 13, 2016 at 21:01 UTC ( [id://1173958] : perlquestion . print w/replies, xml ) Need Help??

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

I'm in need of a bubble sort but one that is a bit more complicated. When running the example below, I am looking to print ONLY the following:
samba-common-libs-4.2.12-7.el7_2.x86_64
xyz-libs-4.2.13-7.el7_2.x86_64
abc-4.2.11-8.el7_2.x86_64

In other words, I only want to return the update package with the highest revision number for each respective package. Any help would be much appreciated.
#!/usr/bin/perl @lines = <DATA>; foreach (@lines) { print("$_"); } __DATA__ samba-common-libs-4.2.10-6.2.el7_2.x86_64 samba-common-libs-4.2.10-8.el7_2.x86_64 samba-common-libs-4.2.12-7.el7_2.x86_64 samba-common-libs-4.2.10-6.el7_2.x86_64 samba-common-libs-4.2.10-3.el7_2.x86_64 xyz-libs-4.2.10-7.el7_2.x86_64 xyz-libs-4.2.12-7.el7_2.x86_64 xyz-libs-4.2.13-7.el7_2.x86_64 xyz-libs-4.2.11-7.el7_2.x86_64 abc-4.2.11-7.el7_2.x86_64 abc-4.2.11-8.el7_2.x86_64 abc-4.2.11-6.el7_2.x86_64

Replies are listed 'Best First'.
Re: Advanced Bubble Sort
by tybalt89 (Monsignor) on Oct 13, 2016 at 21:30 UTC
    #!/usr/bin/perl -l # http://perlmonks.org/?node_id=1173958 use strict; use warnings; my @data = <DATA>; my $numbers = ''; $numbers |= $_ for "@data" =~ /\d+/g; my $length = length $numbers; my %packages; @packages{ /^([\w-]+)/ } = $_ for map $_->[0], sort { $a->[1] cmp $b->[1] } map [ $_, s/\d+/ sprintf "%0${length}d", $& /ger ], @data; print sort values %packages; __DATA__ samba-common-libs-4.2.10-6.2.el7_2.x86_64 samba-common-libs-4.2.10-8.el7_2.x86_64 samba-common-libs-4.2.12-7.el7_2.x86_64 samba-common-libs-4.2.10-6.el7_2.x86_64 samba-common-libs-4.2.10-3.el7_2.x86_64 xyz-libs-4.2.10-7.el7_2.x86_64 xyz-libs-4.2.12-7.el7_2.x86_64 xyz-libs-4.2.13-7.el7_2.x86_64 xyz-libs-4.2.11-7.el7_2.x86_64 abc-4.2.11-7.el7_2.x86_64 abc-4.2.11-8.el7_2.x86_64 abc-4.2.11-6.el7_2.x86_64

    prints:

    abc-4.2.11-8.el7_2.x86_64 samba-common-libs-4.2.12-7.el7_2.x86_64 xyz-libs-4.2.13-7.el7_2.x86_64
Re: Advanced Bubble Sort
by johngg (Canon) on Oct 13, 2016 at 22:08 UTC

    Another way scaling the major, minor etc version numbers then using List::Util's max to choose the highest version.

    use strict; use warnings; use feature qw{ say }; use List::Util qw{ max }; open my $pkgsFH, q{<}, \ <<__EOF__ or die qq{open: < HEREDOC: $!\n}; samba-common-libs-4.2.10-6.2.el7_2.x86_64 samba-common-libs-4.2.10-8.el7_2.x86_64 samba-common-libs-4.2.12-7.el7_2.x86_64 samba-common-libs-4.2.10-6.el7_2.x86_64 samba-common-libs-4.2.10-3.el7_2.x86_64 xyz-libs-4.2.10-7.el7_2.x86_64 xyz-libs-4.2.12-7.el7_2.x86_64 xyz-libs-4.2.13-7.el7_2.x86_64 xyz-libs-4.2.11-7.el7_2.x86_64 abc-4.2.11-7.el7_2.x86_64 abc-4.2.11-8.el7_2.x86_64 abc-4.2.11-6.el7_2.x86_64 __EOF__ my %pkgs; while ( <$pkgsFH> ) { chomp; my( $pkg, $ver ) = split m{-(?=\d)}, $_, 2; $ver =~ s{\.el7.*}{}; my @values = split m{[-.]}, $ver, 4; my $key = $values[ 0 ] * 1000000 + $values[ 1 ] * 10000 + $values[ 2 ] * 100 + $values[ 3 ]; $pkgs{ $pkg }->{ $key } = $_; } close $pkgsFH or die qq{close: < HEREDOC: $!\n}; foreach my $pkg ( sort keys %pkgs ) { say $pkgs{ $pkg }->{ max keys %{ $pkgs{ $pkg } } } }

    The output.

    abc-4.2.11-8.el7_2.x86_64 samba-common-libs-4.2.12-7.el7_2.x86_64 xyz-libs-4.2.13-7.el7_2.x86_64

    This solution is somewhat simplistic because the packages the OP lists here are nicely behaved in that the version numbers all fall into a similar pattern. The packages look like they come from a RHEL7 server and if the OP is trying to get the highest revision packages from the full output of rpm -qa the solution will fall apart because package versions are whimsical and follow no consistent pattern.

    Cheers,

    JohnGG

Re: Advanced Bubble Sort
by BrowserUk (Patriarch) on Oct 13, 2016 at 21:49 UTC

    This?

    #! perl -slw use strict; chomp( my @lines = <DATA> ); my $lastLine = shift @lines; my( $lastRoot, $lastVer ) = $lastLine =~ m[(^[^0-9]+)([0-9.-]+)]; $lastVer = pack 'C*', $lastVer =~ m[(\d+)+]g; for my $line ( @lines ) { my( $root, $ver ) = $line =~ m[(^[^0-9]+)([0-9\.-]+)]; $ver = pack 'C*', $ver =~ m[(\d+)+]g; if( $root eq $lastRoot ) { if( $ver gt $lastVer ) { $lastVer = $ver; $lastLine = $line; } } else { print $lastLine; $lastRoot = $root; $lastVer = $ver; $lastLine = $line } } print $lastLine; __DATA__ samba-common-libs-4.2.10-6.2.el7_2.x86_64 samba-common-libs-4.2.10-8.el7_2.x86_64 samba-common-libs-4.2.12-7.el7_2.x86_64 samba-common-libs-4.2.10-6.el7_2.x86_64 samba-common-libs-4.2.10-3.el7_2.x86_64 xyz-libs-4.2.10-7.el7_2.x86_64 xyz-libs-4.2.12-7.el7_2.x86_64 xyz-libs-4.2.13-7.el7_2.x86_64 xyz-libs-4.2.11-7.el7_2.x86_64 abc-4.2.11-7.el7_2.x86_64 abc-4.2.11-8.el7_2.x86_64 abc-4.2.11-6.el7_2.x86_64

    Output:

    C:\test>1173958 samba-common-libs-4.2.12-7.el7_2.x86_64 xyz-libs-4.2.13-7.el7_2.x86_64 abc-4.2.11-8.el7_2.x86_64

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Advanced Bubble Sort
by runrig (Abbot) on Oct 13, 2016 at 21:29 UTC
    Why do you need a bubble sort? What's wrong with built-in sort (once you figure out your versioning issue)?
    As for the version issue, you might want to convert the version part of the string into something that can be alphanumerically compared with the other versions, then it'll be easy to keep only the last one.

      It's part of the homework assignment to use bubble sort.

      But God demonstrates His own love toward us, in that while we were yet sinners, Christ died for us. Romans 5:8 (NASB)

Re: Advanced Bubble Sort (Natural Sort)
by Corion (Patriarch) on Oct 14, 2016 at 09:25 UTC
Re: Advanced Bubble Sort
by eyepopslikeamosquito (Archbishop) on Oct 14, 2016 at 09:19 UTC

    Donald Knuth, in his famous book The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems"

    -- from Bubble sort (wikipedia)

    ... as opposed to bubble sort, which is merely the generic bad algorithm

    -- from bogo sort (Jargon file)

    The title of your question "Advanced Bubble Sort" is right up there with other classic oxymorons, such as "Microsoft Works" and "Advanced BASIC". Thanks for making me smile. :)

Re: Advanced Bubble Sort
by Marshall (Canon) on Oct 14, 2016 at 08:59 UTC
    It looks to me like a standard alpha-numeric sort produces the correct order. What is needed is to select the last line in each "section". This is perhaps one way:
    #!/usr/bin/perl use warnings; use strict; my @data = <DATA>; @data = sort @data; #print @data; #uncomment to see sort order my $last_line = shift @data; foreach my $line (@data) { my ($last_prefix,$last_suffix) = $last_line =~ /^([a-zA-z-]+)\d.+(\.[^\.]+)$/; my ($cur_prefix,$cur_suffix) = $line =~ /^([a-zA-z-]+)\d.+(\.[^\.]+)$/; if ( $last_prefix eq $cur_prefix and $last_suffix eq $cur_suffix) { $last_line = $line; } else { print "$last_line"; $last_line = $line; } } print "$last_line"; =Prints: abc-4.2.11-8.el7_2.x86_64 samba-common-libs-4.2.12-7.el7_2.x86_64 xyz-libs-4.2.13-7.el7_2.x86_64 =cut __DATA__ samba-common-libs-4.2.10-6.2.el7_2.x86_64 samba-common-libs-4.2.10-8.el7_2.x86_64 samba-common-libs-4.2.12-7.el7_2.x86_64 samba-common-libs-4.2.10-6.el7_2.x86_64 samba-common-libs-4.2.10-3.el7_2.x86_64 xyz-libs-4.2.10-7.el7_2.x86_64 xyz-libs-4.2.12-7.el7_2.x86_64 xyz-libs-4.2.13-7.el7_2.x86_64 xyz-libs-4.2.11-7.el7_2.x86_64 abc-4.2.11-7.el7_2.x86_64 abc-4.2.11-8.el7_2.x86_64 abc-4.2.11-6.el7_2.x86_64
      ... a standard alpha-numeric sort produces the correct order.

      If by "standard alpha-numeric sort" you mean a lexicographic or "asciibetic" sort (the default sort of sort), this is unfortunately not the case:

      c:\@Work\Perl\monks>perl -wMstrict -MData::Dump -le "my @ra = qw(1.2.1 1.2.2 1.2.3 1.2.10 1.2.11 1.2.20 1.2.21); my @sorted = sort @ra; dd \@sorted; " ["1.2.1", "1.2.10", "1.2.11", "1.2.2", "1.2.20", "1.2.21", "1.2.3"]
      The digit sub-fields need to be "normalized" in some way, e.g., by being zero-padded for a lexical sort comparison ('01.02.02', '01.02.20'), or by being converted to a standard number for numeric comparison (1.002_002, 1.002_020).

      Sadly, the example data of the OP does not make this problem evident.

      Update: I posted this reply before I saw Corion's post, which addresses the same problem and has a number of informative links.


      Give a man a fish:  <%-{-{-{-<

        I hear what you are saying, and this can be an issue. But in the OP's case, the default sort order does work. Yes, "12" will sort to less than "2". You are completely correct on that point.

        In this case we have a very small data example to work from. I did put in a print so the OP can see the default sort order and determine whether or not this applies more generally to his/her problem or not. Version numbers often, but not always have leading zero's or a fixed number of digits.

Re: Advanced Bubble Sort (General comment on thread)
by BrowserUk (Patriarch) on Oct 17, 2016 at 10:48 UTC

    It seems to me that most everyone in this thread has completely misunderstood your title: the required "bubble sort" is "advanced" because it only requires a single, linear pass.

    Thus O(n) rather than O(n+nlogn); or O(nlogn+nlogn); or O(nlogn)(with a very large constant); or O(MG).

    Essentially you were describing a "find the biggest in each subgroup" algorithm; which doesn't involve any actual sorting whatsoever; and doesn't require every line to be compared to every other line, only with those lines with the same prefix; and only once each.

    Of course, for the size of the sample data the difference is miniscule; but ...


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
    In the absence of evidence, opinion is indistinguishable from prejudice.