Advanced Bubble Sort

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

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 [download] 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` [download]	[reply] [d/l] [select]
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 } } } } [download] 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` [download] 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	[reply] [d/l] [select]
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 [download] 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` [download] 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.	[reply] [d/l] [select]
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.	[reply]
Re^2: Advanced Bubble Sort by GotToBTru (Prior) on Oct 14, 2016 at 12:18 UTC
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)	[reply]
Re: Advanced Bubble Sort (Natural Sort) by Corion (Patriarch) on Oct 14, 2016 at 09:25 UTC
If your input data isn't immediately amenable to use with sort, the likely best approach is to extract the search criteria, transform them into strings, sort on these, and then transform the result back to the strings you want. This approach is interesting if you want `11_foo` to sort after `1_foo` but both before `2_zap`. There are many nodes on Natural Sort: [ Natural Sort ]: Sorting a string with numbers Natural sorting natural sort on array of arrays	[reply] [d/l] [select]
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. :)	[reply]
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 [download]	[reply] [d/l]
Re^2: Advanced Bubble Sort by AnomalousMonk (Archbishop) on Oct 14, 2016 at 09:24 UTC
... 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"]` [download] 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: `<%-{-{-{-<`	[reply] [d/l] [select]
Re^3: Advanced Bubble Sort by Marshall (Canon) on Oct 14, 2016 at 10:20 UTC
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.	[reply]
Re^4: Advanced Bubble Sort by AnomalousMonk (Archbishop) on Oct 14, 2016 at 17:41 UTC
Re^5: Advanced Bubble Sort by Marshall (Canon) on Oct 17, 2016 at 05:48 UTC
Some notes below your chosen depth have not been shown here
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.	[reply]


Perl: the Markov chain saw
	PerlMonks