SPUG: Sort an array question

[William Julien]

>From owner-spug-list at mail.pm.org  Thu Dec 26 13:06:42 2002
>X-Authentication-Warning: mail.pm.org: majordomo set sender to owner-spug-list at pm.org using -f
>Date: Thu, 26 Dec 2002 12:53:17 -0800 (PST)
>From: Andrew Reid <blueovalfun at yahoo.com>
>Subject: SPUG: Sort an array question
>To: spug-list at pm.org
>MIME-Version: 1.0
>Content-Type: text/plain; charset=us-ascii
>Sender: owner-spug-list at pm.org
>Precedence: bulk
>X-UIDL: Ja8"!Xi_!!J+X!!Ee_"!
>
>Greetings, 
>
>While attempting to gain more meaninful employment, I
>happened upon this question from a prospective
>provider of opportunity.  "Sort an array
>alphabetically without using the Perl sort command." 
>This was provided by someone not familiar with Perl
>but other languages and all work was shown on a white
>board.  I think I did OK, there were a few holes in
>the code, and I decided to really give it a shot. 
>This works and is very close to what I provided on the
>spot.
>
>If any of you have some free time and thoughts, I'd
>appreciate them!  Tell me what you think.
>
>Here is my program.
>
<zap>

Although basic, this is actually a very interesting problem. There is
more than one way to sort an array. Consider, for example a mixed array
of numbers and characters. The standard perl sort puts a "12" before a
"2". Mixed alpha and numeric elements require special handling. What is
"correct", depends on the expectation of the user (programmer).

I wish you luck in finding new opportunities. To help, I offer a few humble
suggestions and sample code. These are issues of style, religion, and art;
not science.

    White space is "good". It enhances the readability of the code.

    Divide your code into logical segments. The code below starts with a
    comment block with provides "who, what, when, where".  This is good
    in a corporation when the reader needs to "kill the author". :-)
    What follows are a module, variable and initialization sections.
    Each major functional unit has a comment.

    I comment sections for "what is does", not "how I do it". If
    particular lines require explaination, I place them on the right
    of the line. I never comment control structures ("end for while").
    If the person reading the code can't figure that out, they need to
    get a job in the service industry.

    I use the "my" scoping block to document the purpose and use of
    each variable. Again, this is just my style. There is no wrong way.

    Finally, think about ways to simplify and reduce the number of variables.
    The line "foreach (@array1) {$arrayCnt++;}"  is not necessary since
    "$#array1;" provides the same answer (but zero based). General rule of
    thumb: When you find your "my" block filling with control variables,
    it's time to think if a better way. This is really important when the
    program starts getting large. 

William Julien
(vi bill)

Sample run:

-->bubble.pl   
Original array: e 42 c g h z Man 2 t a 5 i 6 Cat j l 33 12 p b r q x v a
Perl Sort:      12 2 33 42 5 6 Cat Man a a b c e g h i j l p q r t v x z
alt Perl sort:  2 5 6 12 33 42 Cat Man a a b c e g h i j l p q r t v x z
Bubble sorted:  2 5 6 12 33 42 Cat Man a a b c e g h i j l p q r t v x z
    
Here is the code:

#!/usr/bin/perl -w
#
# Spug sort example
#
# William Julien 
# catmanor.com
# 12/26/2002
###

#
# modules
#
use strict;

#
# variable declarations
#
my (@array,	# an unsorted array
    @sorted,	# a sorted array
    $i,		# loop index
    $j,		# loop index
    $tmp,	# a temporary place
    );

#
# initialization
#
@array = qw(e 42 c g h z Man 2 t a 5 i 6 Cat j l 33 12 p b r q x v a);

#
# print original, perl sort, and alpha/numeric sort
#
print "Original array:\t at array\n";
@sorted = sort @array;
print "Perl Sort:\t at sorted\n";
@sorted = sort { $tmp = $a . $b;
		 ( $tmp =~ /\D+/ ) ?  $a cmp $b : $a <=> $b 
	       } @array ;
print "alt Perl sort:\t at sorted\n";

#
# sort array using a bubble sort
#
for( $i = 0; $i <= $#array; $i++ ) {
    for( $j = $i+1; $j <= $#array; $j++ ) {
	$tmp = $array[$j] . $array[$i];		# join compare elements
	if ( ( $tmp =~ /\D+/ ) ?		# use alpha if not numeric
		$array[$j] lt $array[$i] :	# alpha
	    	$array[$j] < $array[$i]  	# numeric
	   ) {
		$tmp = $array[$j];		# save element
		$array[$j] = $array[$i];	# swap
		$array[$i] = $tmp;		# restore element
	   }
    }
}

#
# print bubble sorted array
#
print "Bubble sorted:\t at array\n";

#
# fin
###

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
     POST TO: spug-list at pm.org       PROBLEMS: owner-spug-list at pm.org
      Subscriptions; Email to majordomo at pm.org:  ACTION  LIST  EMAIL
  Replace ACTION by subscribe or unsubscribe, EMAIL by your Email-address
 For daily traffic, use spug-list for LIST ;  for weekly, spug-list-digest
     Seattle Perl Users Group (SPUG) Home Page: http://seattleperl.org